22
changes so that authorial awareness of changes can be maintained. Since locking often
proves to require too rigid a discipline for many collaborations, Prep’s flexible diff feature
probably represents the state of the art in asynchronous collaboration on documents. In the
context of implementing undo operations, automatically generated differences have distinct
drawbacks, since, in the worst case, one could end up undoing a change (determined by the
diff algorithm) that was never actually executed (in that form). For example, it would be
possible to undo an insertion that was part of a text-move operation without undoing the
deletion of the original source material. The user’s unitary move operation would be split
into two independent operations, with their essential linkage hidden. This objection has re-
cently become less significant because of recent work (Chawathe, Rajaraman et al. 1996)on
comparison algorithms specifically targeted to the detection of changes in documents. These
new algorithms can efficiently detect operations like “move” and “copy”. While they do not
preserve user intention as well as a log of a user’s actual operations, these algorithms would
probably work very well if integrated into a Prep-style system. Technically, such change logs
give the same kind of information as tracking user editing operations would, except that the
algorithm would make an arbitrary decision among the possible operations that might have
created the divergence between states. The resulting history might well violate a user’s ex-
pectations based on her memory of what operations she actually performed.
1.7 Operational transformation
Operational transformation is the name given to the best-known optimistic collaborative
editing approach. While there are many variations of the basic technique, they are all based
on a real-time collaborative editing algorithm due to Ellis and Gibbs (Ellis and Gibbs 1989).
Variations and extensions of this basic algorithm (Prakash and Knister 1992; Choudhary and
Dewan 1995; Palmer and Cormack 1998)have been proposed, as well as improved versions
(Ressel, Nitsche-Ruhland et al. 1996)and (Sun, Jia et al. 1997). The current state of this
changes so that authorial awareness of changes can be maintained. Since locking often
proves to require too rigid a discipline for many collaborations, Prep’s flexible diff feature
probably represents the state of the art in asynchronous collaboration on documents. In the
context of implementing undo operations, automatically generated differences have distinct
drawbacks, since, in the worst case, one could end up undoing a change (determined by the
diff algorithm) that was never actually executed (in that form). For example, it would be
possible to undo an insertion that was part of a text-move operation without undoing the
deletion of the original source material. The user’s unitary move operation would be split
into two independent operations, with their essential linkage hidden. This objection has re-
cently become less significant because of recent work (Chawathe, Rajaraman et al. 1996)on
comparison algorithms specifically targeted to the detection of changes in documents. These
new algorithms can efficiently detect operations like “move” and “copy”. While they do not
preserve user intention as well as a log of a user’s actual operations, these algorithms would
probably work very well if integrated into a Prep-style system. Technically, such change logs
give the same kind of information as tracking user editing operations would, except that the
algorithm would make an arbitrary decision among the possible operations that might have
created the divergence between states. The resulting history might well violate a user’s ex-
pectations based on her memory of what operations she actually performed.
1.7 Operational transformation
Operational transformation is the name given to the best-known optimistic collaborative
editing approach. While there are many variations of the basic technique, they are all based
on a real-time collaborative editing algorithm due to Ellis and Gibbs (Ellis and Gibbs 1989).
Variations and extensions of this basic algorithm (Prakash and Knister 1992; Choudhary and
Dewan 1995; Palmer and Cormack 1998)have been proposed, as well as improved versions
(Ressel, Nitsche-Ruhland et al. 1996)and (Sun, Jia et al. 1997). The current state of this
