The Invisible Algorithm That Keeps You From Overwriting Your Coworker: How Google Sheets' Engineers Solved the 'Two People, One Cell' Problem With Math From a Xerox Lab

It's 2:47 PM on a Tuesday. You're in a Google Sheet with your team, updating Q4 revenue projections. You type "$42" into cell B7. At the exact same moment, 2,000 miles away, your coworker Sarah types "$38" into the same cell.

Both of you hit Enter.

Neither of you sees an error message. Your screen shows one number. Sarah's screen shows another. Then, in less than 200 milliseconds, both screens flicker and converge on the same value. No data lost. No conflict dialog. No "Sarah's version" vs "your version."

You've just witnessed one of the most elegant pieces of distributed systems engineering in the modern web — and you didn't notice at all.

This is the story of how that magic works. It starts in a Xerox lab in 1989, runs through a PhD thesis that almost nobody read, and ends with a schism in the collaborative editing world between two fundamentally different approaches to solving the same problem: What happens when two people edit the same thing at the same time?

The Jupiter Problem

Xerox PARC, 1989. Two researchers, David Nichols and David Curtis, are staring at a problem that would define the next 30 years of collaborative software.

They're building a system called Jupiter — a multi-user text editor. The vision: multiple people typing into the same document simultaneously, from different computers, with changes appearing in real-time for everyone.

The naive approach doesn't work. If User A types "Hello" at position 0, and User B simultaneously types "World" at position 0, you get chaos. Send both operations to the server, apply them in order of arrival, and you get either "HelloWorld" or "WorldHello" — neither of which reflects what either user intended.

Locks don't work either. Lock the document when someone's typing? You've just built a turn-based text editor. Congratulations, you've reinvented the typewriter.

The breakthrough came from a deceptively simple idea: Don't send the operation you performed. Send the intent of what you wanted to do — and transform that intent based on what happened concurrently.

They called it Operational Transformation (OT). The paper, published in 1989, got 47 citations in the first decade. Today, it has over 2,000 — and powers Google Docs, Google Sheets, and the collaborative editing infrastructure behind billions of edits per day.

The Transform Function

Here's how OT works. Imagine two users editing the string "cat":

• User A inserts "s" at position 0 → wants "scat"
• User B deletes character at position 2 (the "t") → wants "ca"

Both operations happen at the same time, on the same base state: "cat".

User A's client sends insert(0, "s") to the server. User B's client sends delete(2) to the server. The server receives A's operation first (network latency is non-deterministic).

The server applies A's operation: "cat" → "scat".

Now B's operation arrives. But delete(2) was meant for the string "cat", not "scat". If you blindly apply it to "scat", you delete the "a" instead of the "t". Wrong.

This is where the transform function saves you.

The server says: "B's operation was delete(2), but A's operation insert(0, "s") happened first and shifted all positions by +1. So I need to transform B's operation against A's operation."

The transform function T(delete(2), insert(0, "s")) returns delete(3) — the delete position is shifted by 1 to account for the insert.

Now the server applies delete(3) to "scat" → "sca". Perfect.

Meanwhile, User A's client receives B's original operation delete(2). It transforms it against its own local operation: T(delete(2), insert(0, "s")) → delete(3). Applies it. Gets "sca".

User B's client receives A's operation insert(0, "s"). It transforms it against its own local operation: T(insert(0, "s"), delete(2)) → insert(0, "s") (insert position doesn't change because the delete happened after it). Applies it to "ca" → "sca". Then applies its own transformed delete.

All three states — server, User A, User B — converge on "sca".

Convergence. Intent preservation. No conflicts.

This is the magic. Every operation is transformed against every concurrent operation, in a way that preserves the original intent, until everyone agrees on the same final state.

The Google Docs Problem

Fast-forward to 2006. Google has just acquired Writely, a tiny startup building a web-based word processor. The team is tasked with making it truly real-time — multiple users typing simultaneously, like they're sitting at the same keyboard.

The problem: Operational Transformation is hard. Like, academically hard.

The transform function must satisfy two properties:

1. TP1 (Convergence): For any two operations a and b, applying a then T(b, a) must produce the same state as applying b then T(a, b).
2. TP2 (Transformation Property 2): For any three operations a, b, c, the transform must compose correctly. This gets into complex three-way transformation scenarios that break human intuition.

Getting TP1 and TP2 right for all possible operation types (insert, delete, formatting, cursor moves, undo) is a PhD-level problem. The Jupiter paper punted on undo. Most academic OT systems punted on rich text. Google needed it to work for everything.

The Google Docs team spent 18 months debugging edge cases. There's a legendary Google Docs bug from 2010 where specific sequences of bolding and unbolding text in a three-user session would cause one user's client to diverge permanently from the server. The fix required rewriting the transform function for formatting operations.

But they got it working. By 2010, Google Docs was handling millions of concurrent editing sessions. The Realtime API (now deprecated) exposed the OT engine to third-party developers. Google Sheets inherited the same infrastructure.

Under the hood, every keystroke becomes an operation object:

{
  "type": "insert",
  "position": 42,
  "text": "Hello",
  "clientId": "user_abc",
  "revision": 1583
}

The server maintains a central revision history. Every operation is tagged with the revision number it was based on. When the server receives an operation from a client, it transforms that operation against all operations that happened since that revision, then broadcasts the transformed operation to all other clients.

Clients maintain an operation queue — operations they've sent but not yet acknowledged by the server. When an operation from another user arrives, they transform their queued operations against it, reapply them to their local state, and update the UI.

It's a 200-millisecond ballet of transformation functions, queues, and WebSocket messages. You never see it. You just see your coworker's cursor moving.

The CRDT Rebellion

By 2015, a new generation of engineers started asking: Does it have to be this complicated?

Operational Transformation has a fatal flaw: it requires a central server. The server is the source of truth for the total operation order. Clients transform their operations against the server's ordering.

This means:

• No true offline support. If you're offline, your edits are in limbo until you reconnect and the server transforms them.
• Server is a bottleneck. Every operation must round-trip to the server for ordering.
• Complex correctness guarantees. TP1 and TP2 are fragile. Miss an edge case, and states diverge.

Enter CRDTs (Conflict-free Replicated Data Types).

CRDTs are data structures designed to be replicated across multiple nodes, edited independently, and guaranteed to converge to the same state when synced — without a central server.

The key insight: Don't transform operations. Design the data structure so that operations commute.

A simple example: a G-Counter (Grow-only Counter). Each node maintains a vector of counts, one per node. To increment, you increment your own count. To read the total, you sum all counts. If two nodes increment concurrently, both increments are preserved. No conflicts. No transforms.

For text editing, CRDTs use sequence CRDTs like RGA (Replicated Growable Array) or YATA (Yet Another Transformation Approach, ironically named).

Here's how YATA works (used by Yjs, the most popular CRDT library for collaborative editing):

Every character inserted into the document gets a unique ID (a combination of client ID and a logical timestamp). Characters are stored in a tree structure where each character knows its left and right neighbors by ID. When you insert a character, you say "insert character X between character A and character B" (referencing their IDs).

If two users concurrently insert between the same two characters, the CRDT uses a deterministic tie-breaking rule (like lexicographic ordering of client IDs) to decide the order. Both clients apply the same rule. Both clients converge.

No transform function. No central server. Just math.

Figma uses a custom CRDT for multiplayer canvas editing. Automerge and Yjs are open-source CRDT libraries used by Notion-like apps, Obsidian plugins, and decentralized collaboration tools.

The Trade-Offs

So why doesn't Google Sheets switch to CRDTs?

Because CRDTs have their own costs:

1. Memory overhead. CRDTs store metadata for every character (or element). A 10,000-word document might require 10x the memory of a plain string. OT stores operations transiently.
2. Tombstones. Deleted characters in CRDTs are marked as deleted (tombstones) but never removed, to preserve ordering for late-arriving operations. Documents grow over time.
3. Complexity in rich data types. CRDTs for text are well-understood. CRDTs for spreadsheet formulas, conditional formatting, pivot tables? Still research territory.
4. Latency. CRDTs guarantee eventual consistency. OT can provide stronger consistency guarantees via the central server (e.g., "your operation was definitely applied before theirs").

For Google Sheets, the central server is a feature, not a bug. It enables:

• Access control. The server enforces who can edit what.
• Audit logs. Every operation is logged server-side.
• Undo/redo coordination. The server can coordinate undo across users (OT undo is already a nightmare; CRDT undo is worse).

For decentralized, offline-first apps (like peer-to-peer note-taking or local-first software), CRDTs are the future.

The Cursor Presence Problem

Here's a detail Google's engineers had to solve that most people never think about: cursor positions.

You see your coworker's cursor in the Sheet. It's blue, with their name floating above it. As they type, it moves. As you type and shift the document, their cursor moves too, staying in the "right" place.

But cursors aren't operations. They're ephemeral state. If you send cursor positions as absolute coordinates, they become stale the instant someone else edits the document.

Google Sheets uses relative positioning. Cursor positions are stored as logical positions in the document structure (e.g., "row 5, column 3, character offset 7 within the cell"). When an operation arrives that shifts the document (insert/delete), every client transforms the cursor positions of all users against that operation, just like it transforms pending operations.

It's OT for metadata.

And it has to work perfectly, because if your coworker's cursor jumps to the wrong cell, you'll panic and think the Sheet is broken.

The Undo Paradox

The hardest problem in collaborative editing is undo.

You type "Hello", then undo it. Meanwhile, your coworker typed "World" after your "Hello". Your undo arrives at the server after their "World" operation.

What should happen?

Option 1: Remove "Hello", leaving "World". But now "World" is at the beginning of the document, not after "Hello" like your coworker intended. Intent violated.

Option 2: Remove "Hello" and shift "World" back to where it would have been if "Hello" never existed. This preserves intent, but requires transforming the undo operation against every operation that happened after the original operation. Complexity explosion.

Google Docs chose Option 2. Every undo operation is transformed against all intervening operations, recursively. It works, but the code is gnarly. One Google engineer described the undo logic as "the place where senior engineers' pull requests go to die in review."

CRDTs don't make this easier. Undo in CRDTs requires storing the entire history of operations and replaying everything except the undone operation. Most CRDT libraries don't even attempt to support collaborative undo.

The Legacy

Today, every time you open a Google Sheet and watch your coworker's edits appear in real-time, you're watching the descendants of the Jupiter system from Xerox PARC. The transform function. The central server. The operation queue.

But the next generation is being built on CRDTs. Figma's multiplayer canvas. Notion's offline editing. Linear's real-time issue updates. These are CRDT systems, designed for a world where the server is optional, where local-first software wins, where your data lives on your device and syncs peer-to-peer.

The irony: Operational Transformation was invented to escape the tyranny of the central server's locks. CRDTs were invented to escape the tyranny of the central server's ordering.

Both solved the same problem: How do you let two people edit the same thing at the same time?

One said: Transform the operations.

The other said: Transform the data structure.

Google Sheets bet on the first. The future might belong to the second.

But for now, when you and Sarah both type into cell B7 at the exact same moment, and nobody's work gets lost, you can thank a 1989 paper from a Xerox lab, a decade of Google engineers debugging transform functions, and a 200-millisecond symphony of WebSocket messages you'll never see.

The magic is invisible. The math is eternal.