Collaborative Editing

Open a Google Doc with a coworker. You both start typing in the same paragraph. Somehow, your edits merge seamlessly -- no data loss, no weird glitches. It feels like magic, but under the hood it is one of the hardest problems in distributed systems: making concurrent writes to shared state converge to the same result regardless of network delays or operation order.

This pattern shows up more often in interviews than you might expect. Any system where multiple users modify shared state simultaneously -- the Slack question with concurrent message edits, the Online Chess question where two players submit moves against the same board, even the Crossword Puzzle question where multiple solvers fill in the same grid -- needs some form of collaborative conflict resolution.

Why Naive Approaches Fail#

The core problem is deceptively simple. Two users start with the same document and make edits at the same time. Their edits travel over the network and arrive at different times. If you just apply each edit as it arrives, the result depends on arrival order, and the two users end up with different documents.

You cannot solve this with simple locking (one user edits at a time) because it destroys the real-time experience. You cannot solve it with last-write-wins because you would silently discard edits. You need an algorithm that preserves every user's intent and guarantees all clients converge to the same document state. Two algorithms have emerged to solve this: Operational Transformation (OT) and Conflict-free Replicated Data Types (CRDTs).

Operational Transformation (OT)#

OT is the older approach, battle-tested at Google scale since 2006. The idea: when two operations are generated concurrently, a transformation function adjusts one operation's parameters based on the effect of the other so both can be applied in any order and still converge.

Here is a concrete example. The document is "Hello". User A inserts "X" at position 0, producing "XHello". Concurrently, User B deletes the character at position 1 (the "e"), intending "Hllo". If User B's delete arrives at User A's client after the insert, position 1 is now "H" instead of "e" -- the wrong character gets deleted. OT solves this by transforming User B's operation: since User A inserted a character before position 1, User B's delete position shifts from 1 to 2. Both clients converge to "XHllo".

The critical constraint: OT requires a central server that acts as the single source of truth for operation ordering. All clients send their operations to the server. The server assigns each operation a sequence number, transforms it against any concurrent operations it has already processed, and broadcasts the result. This is the same server-authoritative model used in the Online Chess question, where the server validates and orders all game moves to prevent conflicting board states.

Google Docs uses OT. It works, it scales, and decades of production experience have ironed out the edge cases. The downside: the transformation functions grow complex as you add more operation types (text formatting, table edits, embedded objects), and you cannot edit offline because every operation needs the server to determine its position in the global sequence.