Practical Intro to Operational Transformation
15 days ago
- #crdt
- #operational-transformation
- #collaborative-editing
- Operational Transformation (OT) and Conflict-Free Replicated Data Types (CRDT) are two approaches to collaborative editing.
- OT transforms operations like insert, delete, and update to maintain consistency across different document states.
- CRDT ensures eventual consistency by allowing operations to be applied in any order, using unique IDs for characters and tombstones for deletions.
- OT and CRDT have trade-offs: OT is simpler to implement but struggles with undo operations, while CRDT is more complex but handles undo better.
- OT algorithms consist of basic operations, a transformation function, and a control algorithm to manage operation contexts.
- TP1 and TP2 are transformation properties that ensure consistency and user intent in OT algorithms.
- Control algorithms in OT manage operation contexts to avoid conflicts and ensure correct transformations.
- Undo in OT is challenging due to inverse properties (IP1, IP2, IP3) and often requires tombstones for simplicity.
- A simple OT algorithm uses a central server to manage global history and transform operations, ensuring consistency.
- Real-world implementations of OT include Google Wave, CoWord, and CoMaya, while CRDT is used in distributed systems.
- OT and CRDT comparisons highlight their strengths and weaknesses in terms of simplicity, space/time complexity, and handling rich text.
- OT history includes algorithms like deOPT, Jupiter, GOT, COT, and TTF, each addressing different challenges in collaborative editing.