Practical Intro to Operational Transformation

Collaborative editing can be achieved using Operational Transformation (OT) or Conflict-Free Replicated Data Types (CRDTs). OT transforms operations based on the current document state, exemplified by adjusting an insert or delete operation when concurrent edits interfere. CRDTs use position-independent operations with unique identifiers, handling conflicts through inherent data structure properties, often modeling deletions as "hides" (tombstones).

OT algorithms consist of basic operations, a transformation function, and a control algorithm, aiming for consistency and preserving user intent, often formalized by properties like TP1 and TP2. Satisfying TP2 is difficult, so control algorithms often structure operations to avoid it, ensuring operations are transformed against a common, ordered context.

CRDTs are simpler in concept for full distribution, but practical, efficient implementation, especially finding positions, introduces complexity. While basic OT algorithms can be simpler to implement, OT's undo functionality is notoriously complex, often requiring techniques like tombstones, which introduce translation overhead between internal and visible document states. Both approaches have trade-offs regarding distribution, complexity, and handling rich text, with many commercial editors utilizing OT variants. A simple, centralized OT algorithm example involves maintaining a linear global history and local, pending operations.