23
work has been summarized well in (Sun and Ellis 1998; Sun, Jia et al. 1998). All retain the
basic approach of the original. The idea is to track the update state of an instance of a col-
laborative editor in terms of the changes that it has seen from other editor instances. Each
instance then transmits a message containing timestamp information and the operations it
has processed. Other instances can correctly update themselves given the incoming message,
and their own state. On arrival, the operations must be transformed so that the offsets they
represent in the document being edited (essentially a string) correspond to the proper posi-
tions in the receiving editor instance. While the initial algorithm was focused directly on the
problem of implementing text editors, the basic idea of operational transformation can obvi-
ously be generalized. Recent work is just starting to extend the technique to other data
structures, such as spreadsheets (Palmer and Cormack 1998).
This basic technique has been applied to the implementation of a number of different
collaborative editing features, including collaborative undo. The fundamental goal is to
achieve consistent (i.e. identical) displays at all clients (once each client has seen every op-
eration), and not necessarily to guarantee that such views are necessarily sensible in terms
of user operations. This weaker consistency condition is characteristic of on-line collabora-
tion, and means, for example, that a deterministic way of resolving editing conflicts is suffi-
cient, even if the resolution does not preserve the user’s notion of document consistency. It
is perhaps the weakest notion of application consistency possible. For a real-time editor this
is acceptable because users will be able to detect and correct such errors immediately. For
off-line collaborations, this policy can also be acceptable when the ability to make progress
and work without being blocked outweighs the coordination cost of handling conflicts.
One of the real problems with operational transformation is the need for transformations
of the operations. Since affected regions of operations are represented by offsets, an opera-
tion must be transformed whenever an earlier operation in the history is detected, or un-
done. An operational transformation engine must satisfy two conditions:
work has been summarized well in (Sun and Ellis 1998; Sun, Jia et al. 1998). All retain the
basic approach of the original. The idea is to track the update state of an instance of a col-
laborative editor in terms of the changes that it has seen from other editor instances. Each
instance then transmits a message containing timestamp information and the operations it
has processed. Other instances can correctly update themselves given the incoming message,
and their own state. On arrival, the operations must be transformed so that the offsets they
represent in the document being edited (essentially a string) correspond to the proper posi-
tions in the receiving editor instance. While the initial algorithm was focused directly on the
problem of implementing text editors, the basic idea of operational transformation can obvi-
ously be generalized. Recent work is just starting to extend the technique to other data
structures, such as spreadsheets (Palmer and Cormack 1998).
This basic technique has been applied to the implementation of a number of different
collaborative editing features, including collaborative undo. The fundamental goal is to
achieve consistent (i.e. identical) displays at all clients (once each client has seen every op-
eration), and not necessarily to guarantee that such views are necessarily sensible in terms
of user operations. This weaker consistency condition is characteristic of on-line collabora-
tion, and means, for example, that a deterministic way of resolving editing conflicts is suffi-
cient, even if the resolution does not preserve the user’s notion of document consistency. It
is perhaps the weakest notion of application consistency possible. For a real-time editor this
is acceptable because users will be able to detect and correct such errors immediately. For
off-line collaborations, this policy can also be acceptable when the ability to make progress
and work without being blocked outweighs the coordination cost of handling conflicts.
One of the real problems with operational transformation is the need for transformations
of the operations. Since affected regions of operations are represented by offsets, an opera-
tion must be transformed whenever an earlier operation in the history is detected, or un-
done. An operational transformation engine must satisfy two conditions:
