The Impossible Collision: How Two People Type in the Same Cell at the Same Time — And the Algorithm War That Powers Every Google Doc

It's 3:47 PM on a Tuesday. You're in a Google Sheet with your coworker Sarah. You both click cell B4 at the exact same moment. You type "Q3". She types "Sales". You hit space. She types "Data". You type "Revenue".

The cell now reads: "Q3 Sales Data Revenue".

Not "Q3 Revenue" (yours). Not "Sales Data" (hers). Not a corrupted mess. Not a "conflict detected" error message. Both of your intentions, perfectly merged, character by character, in the order you typed them — even though neither of you saw what the other was doing until it was already done.

This is the hardest problem in computer science that nobody thinks about.

And the algorithm that solves it — Operational Transformation — was born in 1989 in a Xerox PARC lab, almost died in obscurity, got rescued by Google engineers who needed to make Google Docs work, and is now locked in an existential war with a newer, weirder solution called CRDTs that's powering Figma, Notion, and the next generation of collaborative software.

This is the story of how we made multiplayer editing work. And why, after 40 years, we're still fighting about the right way to do it.

The Jupiter Collaboration System: 1989, Xerox PARC

The place where the PC was invented — and promptly given away to Steve Jobs — was also obsessed with another problem: what happens when two people edit the same document at the same time?

David Nichols and his team at Xerox PARC were building the Jupiter Collaboration System. The problem was deceptively simple: if User A and User B both have a copy of a document, and they both make changes, how do you merge those changes without destroying someone's work?

The naive solution: "last write wins." Whoever hits save last, their version becomes the truth. Everyone else's work disappears.

This is how most file systems still work. It's catastrophic for real-time collaboration.

The second naive solution: lock the document. Only one person can edit at a time. This is how Google Docs worked in 2006 when it launched (inherited from the Writely acquisition). It was painfully slow. If you've ever been in a Google Doc with 50 people and felt the lag, you're feeling the ghost of this original architecture.

Nichols realized the problem wasn't about saving or locking. It was about transforming operations.

The OT Insight: Transform, Don't Overwrite

Here's the key insight of Operational Transformation:

If User A inserts "Hello" at position 0, and User B simultaneously inserts "World" at position 0, you don't pick one. You transform User B's operation against User A's operation.

User A's operation: insert("Hello", 0) — the document is now "Hello" User B's operation (original intent): insert("World", 0) — they wanted to insert at the beginning

But User A already inserted 5 characters. So you transform User B's operation: insert("World", 5) — now insert after "Hello"

Result: "HelloWorld"

Both intents preserved. No conflict. No dialog box. No overwrite.

The magic is in the transform function — a mathematical function that takes two concurrent operations and adjusts one to account for the effects of the other.

transform(operation1, operation2) → operation2'

For insertions and deletions, the transform rules look simple:

• If two inserts happen at different positions, the later position gets shifted by the length of the first insert
• If an insert and a delete conflict, the delete position adjusts based on whether the insert came before or after
• If two deletes overlap, you have to figure out which characters still exist

But here's where it gets nasty: what if three people are editing at once?

The OT Puzzle: Convergence Hell

The Jupiter team discovered something terrifying: if you have three users making concurrent edits, and you transform operations pairwise, you can end up with different final states depending on the order you apply the transforms.

User A inserts "X" at position 0 User B inserts "Y" at position 0 User C inserts "Z" at position 0

If A and B merge first, then merge with C, you might get "XYZ" If A and C merge first, then merge with B, you might get "XZY"

The document diverges. Everyone ends up with a different version.

The solution: a central server that defines a canonical operation order.

Google Docs doesn't let your changes merge peer-to-peer. Every edit you make gets sent to a Google server. The server puts it in a global queue. The server transforms your operation against everything that came before it in the queue. The server broadcasts the transformed operation to everyone else.

You see Sarah's edits not because your browser talked to her browser. You see them because the Google server told you what happened.

This is why Google Docs needs an internet connection. This is why offline editing is so hard. OT requires a central authority to enforce ordering.

The Cost of Correctness

Google's OT implementation (built by engineers who studied the original Jupiter papers) is a monstrosity of edge cases.

The transform function for text insertion alone has to handle:

• Concurrent inserts at the same position (break ties by user ID)
• Deletes that remove characters another user just inserted (delete the range that still exists)
• Cursor positions after insertions and deletions (shift cursors by delta)
• Formatting operations (bold, italic) that overlap with edits
• Undo/redo in the face of concurrent edits (undo your own operation, but transformed against everything that happened since)

By 2010, Google's internal OT codebase was over 400,000 lines of Java. The transform functions had to account for every possible operation type: insert, delete, format, move, paste, indent, bullet points, tables, comments, suggestions.

And every new feature made OT harder.

When Google Docs added tables, they had to write transform functions for: insert row, delete row, insert column, delete column, merge cells, split cells — and every combination of those operations happening concurrently.

Engineers called it "the OT tax." Every feature required weeks of work just to make collaboration not break.

Enter the Rebellion: CRDTs

In 2011, a research paper out of INRIA (the French national computer science lab) proposed something radical:

What if you didn't need a central server?

Conflict-free Replicated Data Types (CRDTs) are data structures that mathematically guarantee eventual consistency without coordination.

The idea: instead of transforming operations, design data structures where any order of operations converges to the same state.

Example: a G-Counter (grow-only counter)

Each user has their own counter. When you increment, you only increment your own counter. To get the total, you sum everyone's counters.

User A increments twice: {A: 2, B: 0} → total = 2 User B increments once: {A: 0, B: 1} → total = 1

They merge: {A: 2, B: 1} → total = 3

No matter what order the increments happened, no matter how the messages arrived, the total is always correct.

No central server. No transform functions. No ordering.

The Text CRDT Problem: Sequence CRDTs

Counters are easy. Text is brutal.

How do you represent a text document as a CRDT? You can't just use a string — strings have positions, and positions change when you insert or delete.

The breakthrough: give every character a unique, immutable ID.

Instead of "Hello" as a string, represent it as:

[{id: A1, char: 'H'}, {id: A2, char: 'e'}, {id: A3, char: 'l'}, {id: A4, char: 'l'}, {id: A5, char: 'o'}]

Now when User B inserts "W" at the beginning, they don't say "insert at position 0." They say "insert W with ID B1, and it comes BEFORE A1."

[{id: B1, char: 'W', before: A1}, {id: A1, char: 'H'}, ...]

No matter what order these operations arrive, the final ordering is deterministic.

This is called an RGA (Replicated Growable Array). It's one of the earliest sequence CRDTs.

But RGA has a problem: tombstones.

When you delete a character, you can't actually remove it from the data structure (other users might still reference it). You mark it as deleted.

Type "Hello", delete "Hello", type "Hello" again — your internal data structure has 15 characters (5 visible, 10 tombstones).

Google Docs with CRDTs would eventually grind to a halt under the weight of deleted characters.

YATA: The CRDT That Changed Everything

In 2016, a German PhD student named Kevin Jahns built Yjs — a JavaScript CRDT library that solved the tombstone problem.

Yjs uses an algorithm called YATA (Yet Another Transformation Approach — a cheeky nod to OT).

The trick: compress tombstones.

Instead of keeping every deleted character forever, YATA collapses consecutive tombstones into a single range marker. Delete 1000 characters? That's one tombstone range, not 1000 tombstones.

Yjs is fast. It's small (30KB gzipped). And it works offline.

Notion uses Yjs. Nimbus Note uses Yjs. Linear uses Yjs. Jupyter Notebooks use Yjs.

But Google Docs still uses OT.

The OT vs CRDT War: Why Google Won't Switch

Why doesn't Google Docs switch to CRDTs?

Three reasons:

1. Intent preservation

OT has a central server that enforces a canonical order. This means Google can make editorial decisions about what "makes sense."

If you type "Hello" and I type "Goodbye" in the same spot at the same time, OT can say "alphabetical order" or "user A always wins." CRDTs just say "concurrent inserts have a deterministic order based on user IDs." You get "GoodbyeHello" or "HelloGoodbye" based on... who signed up first? Not great UX.

2. Undo/redo semantics

OT makes undo/redo work like you expect: undo YOUR last operation, even if others have edited since.

CRDTs make this hard. If you insert "X", I insert "Y" after it, then you undo — what happens to "Y"? Does it move? Does it stay? There's no "correct" answer.

3. The sunk cost

Google has 15 years of OT infrastructure. Billions of documents. A transform function battle-tested by a billion users. Switching to CRDTs would mean rewriting the entire collaboration stack — and risking bugs in an algorithm that "just works."

The Figma Gambit: Custom CRDTs at Scale

But one company made the bet that CRDTs were the future: Figma.

Figma's CTO, Evan Wallace, built a custom CRDT for multiplayer design editing. Not text — vector graphics, layers, properties, constraints.

Figma's CRDT isn't based on Yjs or Automerge. It's bespoke. It uses Last-Write-Wins Registers (LWW-Registers) for properties like "this rectangle is red" — if two people set the color at the same time, the one with the higher timestamp wins.

But it uses sequence CRDTs for ordering layers — so if two people insert layers at the same position, they both survive.

Figma's advantage: no server roundtrip for every edit. Your changes merge locally with other users' changes. You see updates faster. You can keep working offline (sort of).

The trade-off: occasional weirdness. If you and a teammate both move the same object at the same time, it sometimes "jumps" as the CRDT resolves the conflict.

But Figma decided this was acceptable. Google decided it wasn't.

The Cursor Presence Problem

One last thing that haunts every real-time collaboration system: how do you show where everyone else is typing?

You see those colored cursors in Google Docs. Sarah's cursor is blue. It follows her around as she types.

This isn't part of OT. It's not part of CRDTs. It's a separate presence protocol.

Google Docs uses WebSockets to broadcast cursor positions every 100ms. Your cursor position is represented as a "path" through the document tree (e.g., "3rd paragraph, 2nd sentence, 5th character").

But here's the problem: when someone inserts text, everyone else's cursor positions are wrong.

If Sarah's cursor is at position 100, and you insert 5 characters at position 50, Sarah's cursor is now at position 105.

Google Docs transforms cursor positions using the same OT algorithm. Every operation that changes the document also shifts every active cursor.

It's OT, all the way down.

The Legacy: 40 Years and Still Unsolved

In 2013, Google deprecated their public Realtime API (the OT library they offered to developers) because it was too hard to maintain. They said: "build your own."

In 2024, there's still no "solved" solution for real-time collaboration.

OT requires a central server and is monstrously complex. CRDTs are decentralized but have weird edge cases and undo problems. Automerge and Yjs are battling for mindshare in the open-source world. Figma's custom CRDT is proprietary.

But every time you see two cursors in the same cell, both typing at once, both surviving — you're watching 35 years of computer science theory playing out in real time.

The next time you're in a Google Doc with your team, inserting comments, moving paragraphs, undoing each other's typos, remember:

None of this should work.

That it does — that you never see a "conflict detected" dialog, that your work never disappears, that 50 people can edit the same sentence simultaneously — is a small miracle of algorithms, engineering, and the stubborn refusal of very smart people to accept that multiplayer editing was impossible.

It wasn't impossible.

It was just really, really hard.