80
new sequence E’, in the obvious way. An insertion (m, I
1 …I
n )gives the new sequence
D
1 …D
m-1 I
1 …I
n D
m …D
n . A deletion(s, e)gives the new sequenceD
1 …D
s–1 D
e+1 …D
n .The result of
a history O
1 …O
k ,is the result of successively applying each operation to the result of the
previous applications to produce a final result.
More complex histories can be defined as compositions of these linear histories. For in-
stance, two histories H
1 andH
2 represent versions on separate branches of a version tree, if
they share a common initial set of operations O
1 …O
k . The state defined up toO
k represents
the history of the common ancestor of H
1 andH
2 . Other variations includereverse deltas,as
used in the RCS system. In this approach a final version is always available, and inverse op-
erations are used to represent histories. Reverse deltas interchange the meaning of insert
and delete operations (since the state before and insertion can be found by deleting the in-
serted data, and the state before a deletion can be found by inserting the data that was de-
leted). Otherwise, reverse deltas have exactly the same properties.
This representation is the basic starting point for operational transformation approaches
as well as software version control systems. It has real drawbacks for representing (and im-
plementing) the merge operation, and not only because it does not handle dynamic opera-
tions. The offsets in each insertion and deletion in a sequence of operations depend on the
preceding changes in the history, since the offsets of each character depend on the exact
series of changes applied so far. This means that any merge process must order all operations
into a serial history, and then adjust the offsets of these changes depending on the final
serialization chosen. Adjusting these offsets in the presence of multiple change sources can
be a difficult task. Ellis and Gibbs’ original algorithm for doing this (Ellis and Gibbs 1989) in
a distributed setting has, indeed, proved difficult to get completely correct(Ressel, Nitsche-
Ruhland et al. 1996; Suleiman, Cart et al. 1997; Sun, Jia et al. 1997).
Many of the difficulties with operational transformation stem from the need to simulta-
neously solve several hard problems; operations must be resolved in a way that preserves
new sequence E’, in the obvious way. An insertion (m, I
1 …I
n )gives the new sequence
D
1 …D
m-1 I
1 …I
n D
m …D
n . A deletion(s, e)gives the new sequenceD
1 …D
s–1 D
e+1 …D
n .The result of
a history O
1 …O
k ,is the result of successively applying each operation to the result of the
previous applications to produce a final result.
More complex histories can be defined as compositions of these linear histories. For in-
stance, two histories H
1 andH
2 represent versions on separate branches of a version tree, if
they share a common initial set of operations O
1 …O
k . The state defined up toO
k represents
the history of the common ancestor of H
1 andH
2 . Other variations includereverse deltas,as
used in the RCS system. In this approach a final version is always available, and inverse op-
erations are used to represent histories. Reverse deltas interchange the meaning of insert
and delete operations (since the state before and insertion can be found by deleting the in-
serted data, and the state before a deletion can be found by inserting the data that was de-
leted). Otherwise, reverse deltas have exactly the same properties.
This representation is the basic starting point for operational transformation approaches
as well as software version control systems. It has real drawbacks for representing (and im-
plementing) the merge operation, and not only because it does not handle dynamic opera-
tions. The offsets in each insertion and deletion in a sequence of operations depend on the
preceding changes in the history, since the offsets of each character depend on the exact
series of changes applied so far. This means that any merge process must order all operations
into a serial history, and then adjust the offsets of these changes depending on the final
serialization chosen. Adjusting these offsets in the presence of multiple change sources can
be a difficult task. Ellis and Gibbs’ original algorithm for doing this (Ellis and Gibbs 1989) in
a distributed setting has, indeed, proved difficult to get completely correct(Ressel, Nitsche-
Ruhland et al. 1996; Suleiman, Cart et al. 1997; Sun, Jia et al. 1997).
Many of the difficulties with operational transformation stem from the need to simulta-
neously solve several hard problems; operations must be resolved in a way that preserves
