13 Third-party operational transformation ideas

Operational transformation originated in research on real-time group editors. The principal ideas developed before the CEDA work were immediate execution of local edits, transformation of concurrent remote edits, causal ordering, convergence conditions, operation contexts and control algorithms for choosing a valid transformation path. This chapter gives the historical context needed to distinguish those contributions from the later work in this archive.

1989: GROVE and dOPT

Ellis and Gibbs introduced transformation-based concurrency control in the GROVE group outline editor. A local operation was executed immediately and propagated to other sites. A remote operation was transformed against concurrent operations already executed at the receiving site, allowing collaboration without locking and without requiring every site to execute concurrent operations in the same order.

The dOPT control algorithm used a linear log of executed operations and transformed a causally ready remote operation from left to right against concurrent operations in that log. It established the basic division that remained characteristic of OT: a generic control algorithm determines which operations are transformed, while application-specific transformation functions determine how their parameters change. The dOPT puzzle later showed that transforming operations which were defined in different document states could cause divergence.

1995: Jupiter

Jupiter used a central server and a separate two-party transformation state space for each connected client. A client applied a local edit immediately, before acknowledgement, sent it to the server and appended it to an outgoing queue. A later server message acknowledged a prefix of that queue. The client removed the acknowledged prefix and transformed the incoming server operation against the locally applied operations which remained outstanding.

For example, suppose clients A, B and C generate a1, b1 and c1, followed by a2, b2 and c2, and the server serialises them as

a1, b1, c1, a2, b2, c2.

Client C may already have applied c1 and c2 when it receives operations from the server. It does not undo those edits and replay the literal server sequence. Instead, each incoming server operation is inclusion-transformed across C's outstanding queue. At each crossing both the server operation and the outstanding local operation are transformed, as in Dual IT. Thus c2 is progressively expressed in the advancing server context until it is acknowledged, while the transformed server operations can be applied after C's speculative edits. C executes a different sequence of operation representations but reaches the same document state as the server.

This works without the TP2 cube because a Jupiter client has only two ordered streams: its own FIFO stream and the server's authoritative stream. They form a two-dimensional grid. Each crossing fills one commuting square using dual IT, and TP1 ensures that the two paths around that square produce the same state. The control algorithm never chooses between different paths through a three-dimensional lattice, so it does not require TP2. It also has no need for ET. The central server and the per-client grids therefore restrict the possible transformation paths; they do not solve the general peer-to-peer TP2 problem. The same architectural idea subsequently became important in production collaborative editors.

1996: adOPTed and transformation properties

Ressel, Nitsche-Ruhland and Gunzenhäuser introduced adOPTed and stated the convergence properties now usually called TP1 and TP2. TP1 requires two concurrent operations to form a commuting square after transformation. TP2 requires the transformed form of a third operation to be independent of which equivalent two-operation path supplies its context. adOPTed retained multiple transformed forms in a multidimensional interaction graph so that an operation could be transformed along a valid path.

1997: SOCT2

SOCT2 used state vectors to enforce causal readiness and used inclusion and exclusion transformations to transpose operations into an order in which the required transformation was valid. This made the relationship between causal order, operation context and transformation order explicit, but could require quadratic work when a long linear history had to be rearranged.

1998: GOT

Sun, Jia, Zhang, Yang and Chen defined an operation's context as the sequence of operations whose effects were present when it was generated. Inclusion transformation adds an operation's effect to a context; exclusion transformation removes one. Their list forms, LIT and LET, apply those transformations successively. The Generic Operation Transformation control algorithm, GOT, uses them to convert a causally ready operation from its generation context to the current history-buffer context.

GOT was combined with an undo/do/redo convergence scheme. Let Pi be the history prefix that causally precedes an incoming operation Oa, and let X1,…,X5 be the following operations, which are concurrent with it. Those operations are undone, Oa is transformed by GOT and executed, and the undone operations are transformed and redone as X1′,…,X5′.

This scheme makes every site establish the same global execution order. If a site's current history does not have that order, undo/do/redo reconstructs the required context rather than relying on different transformation paths to converge. GOT therefore requires IT and ET, including the reversibility needed to remove and restore operation effects, but its convergence argument requires neither TP1 nor TP2.

Triangular network of exclusion and inclusion transformations used to insert an operation into a GOT history buffer

The upper half of the diagram maps each Xi backwards through the operations before it using exclusion transformation. The lower half maps it forwards over Oa and the already transformed operations using inclusion transformation. For a suffix of n operations, this performs n(n−1)/2 exclusion transforms and n(n+1)/2 inclusion transforms: n2 transformations in total. The triangular network makes the quadratic cost visible.

1998: GOTO

GOTO optimised GOT by first reordering the history into a causally preceding prefix and a concurrent suffix. The incoming operation could then be transformed directly against the concurrent suffix. This avoided much of GOT's undo/do/redo transformation network, but in exchange required the IT and ET functions to satisfy TP1 and TP2. It retained the linear history-buffer model.

2010: Google Docs

Google's public description of the 2010 Google Docs editor presents a central-server protocol related to Jupiter, with a stronger restriction on sending. A client records the last server revision it has received, one change which has been sent but not acknowledged, subsequent local changes which have not yet been sent, and its current document. Conceptually, its state has the following form: 

struct ClientState
{
    RevisionId serverRevision;
    std::optional<Operation> sent;
    std::optional<Operation> pending;
    Document document;
};

A local change is applied to document immediately. If sent is occupied, however, the change is accumulated in pending rather than being sent to the server. An acknowledgement clears sent, after which the pending change can be sent. Google Docs therefore waits for an acknowledgement before sending the next change, but not before applying that change locally.

The server maintains the authoritative document and a linear revision log. A submitted change names the server revision on which it was based. If later revisions have already been committed, the server inclusion-transforms the submitted change against them before appending it as the next revision. When a client receives a remote revision, it transforms the remote change against its locally applied sent and pending changes and also updates those local changes. This is dual IT between the ordered server stream and the client's speculative local stream.

As in Jupiter, TP1 makes each client/server crossing commute. The authoritative server sequence and the restriction to one sent but unacknowledged change prevent clients from choosing arbitrary paths through a TP2 cube. The protocol therefore uses IT, including dual IT at the client, but does not need ET or TP2. The restriction simplifies synchronisation without making local typing wait for the network. This describes the design Google published in 2010; it should not be read as a description of the undisclosed current Google Docs implementation.

2019: Fluid Framework and 2021: Loop components in Microsoft Teams

Microsoft announced the Fluid Framework in 2019 and released Loop components in Teams chat in 2021. Teams is a host for several collaboration systems rather than a single collaborative editor. The description here concerns Loop components, which Microsoft states are powered by Fluid. Word, Excel and PowerPoint files opened through Teams use their respective Microsoft 365 co-authoring systems, whose current concurrency algorithms have not been published in comparable detail.

Fluid applies a local change immediately and submits an operation to a Fluid service. The service assigns each operation a monotonically increasing sequence number and broadcasts the resulting total order to all clients, including the sender. The service does not interpret the operation or maintain the application state. Each client maintains its own state, receives the sequenced operations and performs the data-structure-specific merge locally.

Microsoft explicitly describes Fluid as using neither operational transformation nor CRDTs, although its model is closer to a CRDT than to OT. Fluid's Distributed Data Structures define deterministic merge rules under the total-order broadcast. Its sequence implementation, MergeTree, uses persistent sequence structure and operation metadata rather than repeatedly transforming ordinary numerical positions through a temporal history buffer. Concurrent insertions are resolved using their global order. A removal affects only content which was visible when that removal was generated, so it does not inadvertently remove a concurrent insertion.

Several local operations may be speculative while waiting to be sequenced. As their authoritative positions in the stream arrive, the client reconciles its local state using the merge rules of the Distributed Data Structure. There is no classical IT or ET and there are no OT transformation paths to which TP1 or TP2 would apply. Convergence instead follows from every client processing the same sequenced operations with the same deterministic merge logic. This has some affinity with the later CEDA representation of vector changes in spatial order: both move information needed for merging into the representation of the changing sequence rather than depending on a linear history of ordinary positional operations.

Relationship to the CEDA research

The early CEDA implementation adopted the common vocabulary of a linear history buffer, vector time, IT, ET, LIT, LET, GOT and undo/do/redo. The later CEDA work did not merely propose another way to traverse the same temporal list. It developed operation algebras for database fields and then represented composite changes in forms that could be merged and factorised without reconstructing a large quadratic transformation network. The chapters that follow record that separate line of development.

References

  1. C. A. Ellis and S. J. Gibbs, Concurrency Control in Groupware Systems, 1989.
  2. D. A. Nichols, P. Curtis, M. Dixon and J. Lamping, High-Latency, Low-Bandwidth Windowing in the Jupiter Collaboration System, 1995.
  3. M. Ressel, D. Nitsche-Ruhland and R. Gunzenhäuser, An Integrating, Transformation-Oriented Approach to Concurrency Control and Undo in Group Editors, 1996.
  4. M. Suleiman, M. Cart and J. Ferrié, Serialization of Concurrent Operations in a Distributed Collaborative Environment, 1997.
  5. C. Sun, X. Jia, Y. Zhang, Y. Yang and D. Chen, Achieving Convergence, Causality-Preservation, and Intention-Preservation in Real-Time Cooperative Editing Systems, 1998.
  6. C. Sun and C. Ellis, Operational Transformation in Real-Time Group Editors: Issues, Algorithms, and Achievements, 1998.
  7. J. Day-Richter, What's different about the new Google Docs: Making collaboration fast, 2010.
  8. Microsoft, Microsoft introduces new cloud experiences and developer tools for all creators at Microsoft Build, 2019.
  9. Microsoft, Total order broadcast and eventual consistency.
  10. Microsoft, Sequences.
  11. Microsoft, Transforming creation and collaboration with Microsoft Loop components in Teams chat, 2021.