Operational Transformation

The last lesson ended on the one data type that refused to play: text. A document is a sequence, position is meaning, and "insert after the third word" collides with a concurrent edit that moved the third word. Union has no answer, because order is the whole point.

This lesson is the weapon that answer took: don't merge the states; transform the operations against each other, so each edit can be replayed on a document that has already moved. It's the machine that carried Google Docs for two decades, it is older than the web browser, and it comes with the most instructive scar tissue in this whole field: a trail of published algorithms that were proven wrong, a rescue by architecture rather than mathematics, and a rival school that eventually won half the map. By the end you'll have typed into both sides of that war yourself.

Start with the sentence the cat sat, live on two screens. Ana inserts fat at position 4. At the same moment, Ben deletes positions 4 through 7, the word cat . Each edit is perfectly meaningful on the document it was born on. Now deliver them.

Ben's delete arrives at Ana's screen carrying its birth positions: remove characters 4 through 7. But Ana's document isn't the one Ben saw: position 4 is now the start of fat . Apply the delete as-is and it eats her word, not his: the operation lands exactly where it was aimed and hits something else entirely. Run it the other way and Ben keeps her insert. Two screens, two different sentences, both wrong in different ways.

Notice this is worse than the trap from two lessons ago. There, picking one deterministic order at least made replicas agree. Here even a perfect ordering doesn't help, because the second operation's positions are stale the moment the first one applies. The last lesson's move (grow the value until the merge is a law) has nothing to grab: max and union don't mean anything for where. And yet the operations themselves are pure intent: insert fat before cat, delete the word cat. Intent travels with the edit; only the coordinates rot. So keep the intent and fix the coordinates. That's the whole idea.

Define one function and the problem falls open: T(a, b) rewrites operation a so it means the same thing on a document where b has already happened. For plain text, with inserts and deletes, the whole function is four small cases:

Insert meets insert. If the other insert landed before yours, slide your position right by its length. If you both chose the same spot, someone must go first; a fixed tiebreak (say, by author) decides, deterministically, everywhere.

Insert meets delete. If the deleted span was before you, slide left. If your target sat inside the deleted span, land at the deletion's edge: your text survives even though its old neighbors didn't.

Delete meets insert. Slide right if the insert was before you. And if the insert landed inside the span you're deleting, the honest move is surgical: the delete splits in two and removes only what its author actually saw, leaving the newcomer standing. A delete is a claim about the characters you looked at, not about whatever occupies those coordinates later.

Delete meets delete. Overlap is subtracted; deleting the same characters twice means once.

For this machinery to satisfy the convergence contract, the four cases must obey one law, and it has a name: TP1. Apply a then the transformed b, or b then the transformed a: the two paths must close on the identical document. Drawn, it's a diamond, and it is exactly the order-blindness rule from The Conflict Problem, specialized to sequences. (There is a second, crueler law called TP2, about transforming against operations that were themselves transformed. Hold that thought for two sections; it has a body count.)

Below is the sentence, both carets, and both modes. Do the classic first: stage the classic, sync in naive mode, and watch Ben's delete land on Ana's fat : two screens, two sentences, one word swallowed. Then reset the same history into transform mode: the incoming operations get rewritten mid-flight (the flash shows each position shift), the delete splits around the surviving insert, and both lamps go green.

Then make it yours. Type words into both sides while the link is cut: pick the same spot on purpose, delete a word one side while the other inserts into it, and try to make transform mode lose a letter or split the screens. Flip the delivery order and watch nothing change. That's TP1 under your fingers.

OT is old. Ellis and Gibbs published it in 1989: the GROVE editor, at SIGMOD, when collaborative editing meant a lab full of Sun workstations. Their version was fully distributed: every peer transformed against every other peer, no coordinator anywhere. Perfectly symmetric, and (as the next section shows) brutally hard to get right, because peer-to-peer transformation is precisely where that crueler second law lives.

The rescue came in 1995 from the Jupiter collaboration system, and it was an architecture decision, not a theorem: put one server in the middle. Every edit goes to the server; the server stamps a single, total order; each client transforms its in-flight operations against exactly one stream instead of against every peer. The Jupiter authors were candid that centralizing let them substantially simplify the algorithm: with one ordering point, TP1 is all you need, and TP2 never comes up.

You've seen this shape of move before. A hard symmetric problem, funneled through one door, becomes an easy one. It's the owner-per-round trick from the consensus section, spent here on something much cheaper than agreement: mere ordering. The line from that 1995 paper runs straight through history: Jupiter's design became the skeleton of Google Wave, and the same machinery carried Google Docs: millions of simultaneous cursors, decades of service, four transform cases and a stamp counter at the bottom of it all.

Now the scar tissue, because it teaches the sharpest lesson in the lesson.

Without a server, correctness needs TP2 (transforms must also agree when applied to operations that were themselves transformed), and TP2 turned out to be a monster. The record, from the formal-methods literature: dOPT, adOPTed, IMOR, SOCT2, SDT: peer-reviewed algorithms, each published claiming the property, later later falsified by explicit counterexamples. Some had hand-written proofs that were wrong. Two had machine-checked proofs that were still wrong, because the mechanization rested on a false assumption. Researchers eventually found the bugs by exhaustive model-checking, the same brute honesty this course's little labs use.

Practitioners felt it too. Joseph Gentle, who worked on Wave's machinery and wrote ShareJS, the library that carried OT to the open web, titled his 2011 essay on the experience "implementing OT sucks," and engineers nodded for a decade. Then, in 2020, the same author published "I was wrong. CRDTs are the future." One engineer, both sides of the war, nine years apart.

Read the graveyard correctly. It does not say OT is broken: with a server, Jupiter-style, OT is small, proven, and battle-worn in the best sense. It says serverless OT is a minefield that defeated even machine-checked mathematics, and a minefield is exactly the kind of terrain that gets bypassed rather than cleared. What did the bypassing is the school you met last lesson.

Two schools now claim collaborative text, and the honest comparison is short.

OT ships tiny operations (insert three characters, delete four), preserves intention with surgical transforms, and keeps documents lean. But it wants that ordering server, and its transform matrix grows combinatorially: every new kind of operation must define how it transforms against every existing kind. Fine for text with two operation kinds; painful for a design tool with dozens.

CRDT text, the Yjs and Automerge school, gives every character a permanent identity, so an edit names which characters, not which coordinates. No positions means no transforms, no transform matrix, no TP-anything; it works peer-to-peer and offline by construction. The bill is the one you already know from CRDTs: per-character metadata and tombstones, the mortgage on never writing a merge policy, paid per keystroke.

And the pragmatic middle exists, famously: Figma. Their multiplayer is server-authoritative with last-writer-wins per object property: CRDT-inspired, deliberately not true CRDTs, and deliberately not OT, precisely because a design canvas has too many operation kinds for a transform matrix to stay sane. They kept the funnel, skipped both schools' hard parts, and accepted per-property overwrites, a fork-question judgment straight out of this section's opener.

The verdict discipline, then: real-time text editing with a server you control is OT's proven home turf. Offline-first, peer-to-peer, or local-first work belongs to CRDT text. Structured objects behind a server often deserve Figma's middle. And all three answers assume you asked the right first question: what does this data mean, and what would its users call a correct merge?

• Sequences resist state-merging because position is meaning. The same coordinates point at different text once a concurrent edit lands: intent travels with the edit; coordinates rot.
• T(a, b) rewrites a as if b had already happened. Four cases for text (slide, clamp, split, subtract), and the delete-split is the soul of it: remove what the author saw, never what arrived later.
• TP1 is the convergence contract drawn as a diamond: both orders, transformed, one identical document. TP2 governs serverless transformation, and it broke five published algorithms, two of them past machine-checked proofs.
• Architecture rescued what mathematics couldn't tame. Jupiter's 1995 move (one server, one stamped order, transform against one stream) made TP2 unnecessary and became the skeleton of Wave and Docs. An owner bought for ordering, not agreement.
• The war's honest map: OT for real-time text behind your own server; CRDT text for offline and peer-to-peer; Figma's server-plus-registers middle when operation kinds multiply. All three are answers to the same question: what does a correct merge mean here?

Count the arsenal this section has handed you: keep-both siblings, self-merging counters and sets, transformed operations, plus the blunt instruments that never left, last-write-wins, union, refuse, ask a human. Seven tools and, so far, only instinct for choosing between them. Next lesson builds the judgment itself: the full catalog, each strategy priced by what it can lose and what it demands, and the discipline for matching one to your data on purpose: Conflict Resolution Strategies.