Browse Prior Art Database

Generalized Undo Algorithm for Concurrent Edits on a Shared Object

IP.com Disclosure Number: IPCOM000109102D
Original Publication Date: 1992-Jul-01
Included in the Prior Art Database: 2005-Mar-23
Document File: 2 page(s) / 89K

Publishing Venue

IBM

Related People

Conner, MH: AUTHOR [+2]

Abstract

With the advent of distributed systems it becomes feasible to achieve higher availability of shared data by providing replicas of data objects (e.g., a file). One of the problems with this technique is maintaining mutual consistency among the replicas. A simple scheme to achieve mutual consistency is to have a master copy and treat the rest as shadows (or slave copies). When the end users concurrently edit the shadows, the updates are applied to the actual object (master copy) in some global consistency-preserving order. In this kind of environment, when a user wants to undo his recent updates, it becomes tricky. Unlike the case of a single user editing, now there is no stack of user's updates that can be undone one by one.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Generalized Undo Algorithm for Concurrent Edits on a Shared Object

       With the advent of distributed systems it becomes
feasible to achieve higher availability of shared data by providing
replicas of data objects (e.g., a file).  One of the problems with
this technique is maintaining mutual consistency among the replicas.
A simple scheme to achieve mutual consistency is to have a master
copy and treat the rest as shadows (or slave copies).  When the end
users concurrently edit the shadows, the updates are  applied to the
actual object (master copy) in some global consistency-preserving
order.  In this kind of environment, when a user wants to undo his
recent updates, it becomes tricky.  Unlike the case of a single user
editing, now there is no stack of user's updates that can be undone
one by one. Instead, we have to look for the user's specific
operation in the global stack of operations performed on the actual
object and then undo it.  We provide an algorithm to do this
correctly and mechanically so that it works for any kind of object
and for any undoable operation.
Proposed Solution Scheme
*  The shared object manager (at the master copy) maintains a log (a
stack) of operations performed on the object.
*  We assume that all these operations can be undone or redone.  That
is, no irreversible side effects result from these operations.
Further, we assume that it is possible to know if two operations
affect the same datum.
*  When the user requests an undo of his operation, we do the
following.
Undo Algorithm

      Let the operation to be undone be k deep from the top of the
operation stack.
(1)  Remove and undo, one by one, the top k - 1 operations from the
operation stack and log the corresponding redo operations on a new
stack.
(2)  Remove and undo the k th operation. (Do not log its
corresponding redo on the new stack.)
(3)  Remove and redo, one by one, the top k - 1 operations from the
new stack and log them on the original operation stack.
(4)  If a redo depends on portions of the object affected by the
"undo",  then se...