Operational Transformation

Open a Google Doc with a colleague. Both type simultaneously. Changes appear on each other screens in real time. No conflicts. No lost keystrokes. This is operational transformation.

The problem: two users concurrently edit the same document. User A inserts "Hello" at position 0. User B inserts "World" at position 0. If you apply these naively, positions are wrong. OT transforms operations against concurrent operations so they produce the correct result regardless of order.

Google acquired the team behind Google Wave (which used OT) and applied the technology to Google Docs. The algorithm is fiendishly complex, every combination of insert, delete, and format must be handled correctly. This complexity is why many newer systems prefer CRDTs, but OT remains the foundation of the most-used collaborative editors.

The core idea: Given two concurrent operations A and B, compute A-prime (A transformed against B) such that applying B then A-prime produces the same result as applying A then B-prime.

Insert/Insert example:

• A: insert "X" at position 2
• B: insert "Y" at position 4
• If B is applied first, A stays at position 2 (before B insertion point)
• If A is applied first, B shifts to position 5 (A shifted everything right)

Insert/Delete:

• A: insert "X" at position 2
• B: delete character at position 3
• If B is applied first, A stays at position 2
• B shifts to position 4 (A insertion shifted it right)

The number of edge cases explodes with rich text (formatting, tables, images). This complexity is why OT implementations are notoriously buggy.