81
user intentions, operations must be correctly transformed, and parties to the collaboration
must track each other’s state sufficiently to determine what transformation to apply. Palimp-
sest provides, for individual changes, an invariant representation that separates synchroni-
zation from intention preservation. The best description of the state of the art in operational
transformation is found in (Sun and Ellis 1998; Sun, Jia et al. 1998).
Palimpsest eliminates the notion that the operations in a history must be totally ordered,
instead relying only on a partial order that reflects data dependencies in the changes. This
also means, as we have seen, that the addressing mechanism does not rely on offsets or any
other information related to a specific state. This has a significant effect on implementa-
tions, since it is no longer necessary to have even partial knowledge of the distributed state
of other collaborating parties.
4.2 Basic Definitions
The fundamental objects of the Palimpsest formalism are changes, change sets, and se-
quence states. A changerepresents a user’s editing operation on a sequence, and includes
enough information to indicate the editing intention of that change. A change setis a set of
changes, whose actions are to be composed. From a change set, it is possible to extract a
sequence state, the particular state defined by properly executing the operations in that
change set. A system based on the Palimpsest model will maintain a number of change sets.
One is the “universal change set,” containing all changes of whose execution the system has
even been informed, others will correspond to particular states (versions) that the applica-
tion is interested in.
User operations that affect the history of a sequence correspond to the maintenance of
different change sets representing different states that are of interest. An automatic merge
of two states can be accomplished simply by taking the union of the two change sets repre-
senting those states. A user request to undo a change is accomplished by removing that par-
user intentions, operations must be correctly transformed, and parties to the collaboration
must track each other’s state sufficiently to determine what transformation to apply. Palimp-
sest provides, for individual changes, an invariant representation that separates synchroni-
zation from intention preservation. The best description of the state of the art in operational
transformation is found in (Sun and Ellis 1998; Sun, Jia et al. 1998).
Palimpsest eliminates the notion that the operations in a history must be totally ordered,
instead relying only on a partial order that reflects data dependencies in the changes. This
also means, as we have seen, that the addressing mechanism does not rely on offsets or any
other information related to a specific state. This has a significant effect on implementa-
tions, since it is no longer necessary to have even partial knowledge of the distributed state
of other collaborating parties.
4.2 Basic Definitions
The fundamental objects of the Palimpsest formalism are changes, change sets, and se-
quence states. A changerepresents a user’s editing operation on a sequence, and includes
enough information to indicate the editing intention of that change. A change setis a set of
changes, whose actions are to be composed. From a change set, it is possible to extract a
sequence state, the particular state defined by properly executing the operations in that
change set. A system based on the Palimpsest model will maintain a number of change sets.
One is the “universal change set,” containing all changes of whose execution the system has
even been informed, others will correspond to particular states (versions) that the applica-
tion is interested in.
User operations that affect the history of a sequence correspond to the maintenance of
different change sets representing different states that are of interest. An automatic merge
of two states can be accomplished simply by taking the union of the two change sets repre-
senting those states. A user request to undo a change is accomplished by removing that par-
