Implement Operational Transformation

transforming concurrent edits

Challenge 8 of Partitioning & ReplicationAdvanced~60 min

Let two people edit the same document at the same time and still end up with identical text. Operational Transformation is the algorithm behind Google Docs: represent edits as insert/delete operations, then transform a concurrent operation against another so that applying them in either order converges. Build apply, the four transform cases, and prove the convergence property that makes real-time collaboration possible.

4 steps

  1. 1Applying Operations
  2. 2Transforming Two Inserts
  3. 3All Four Cases
  4. 4The Convergence Property
Start step 1