If Your CRDT Test Ends by Syncing Everyone, It Tests Nothing

A CRDT has exactly one advertised job. Hand two replicas the same set of edits in different orders and they must show you the same document. That is a property, not a design philosophy, so you can brute-force it instead of believing it: generate a short operation log, push every permutation of that log through a fresh replica, diff the strings.

I did that to the list CRDT I was about to publish here. Four hundred logs, six operations each, all 720 orderings per log, stopping at the first mismatch; 80,251 orderings actually ran. Three hundred and ten of the four hundred logs produced two different documents depending on delivery order.

That implementation had unique IDs, parent pointers, tombstones, an apply that ignored anything it had already seen — the whole vocabulary. It just did not converge, and three particular orderings are what showed me why.

Ordering one: delete, insert, insert

The shortest failing case has no concurrency in it at all. One author, three operations, a network that reordered them.

// Alice types "HI", then deletes the "H".
// Three ops go on the wire: ins(H), ins(I), del(H).
// A fresh replica receives them in two different orders:
 
replayNaive([insH, insI, delH]);  // -> "I"    correct
replayNaive([delH, insH, insI]);  // -> "HI"   the H came back

One line of the remote-apply path is responsible:

function applyDroppingDelete(doc, op) {
  if (op.t === "ins") {
    if (doc.nodes.has(op.k)) return;                 // already seen, skip
    doc.nodes.set(op.k, { value: op.value, parent: op.parent, deleted: false });
  } else {
    const n = doc.nodes.get(op.k);
    if (n) n.deleted = true;                         // and when it is not there yet?
  }                                                  // nothing. The delete evaporates.
}

if (n) is the bug. A delete for a node this replica has not received yet is thrown away, and when the insert lands afterwards the character is resurrected with deleted: false. Nothing later repairs it. The replicas are permanently different and neither has any way to find out.

Isolate that one line and nothing else, and the same harness reports 310 of 400 logs divergent over 80,076 orderings. Now split the algebra and the picture gets sharper. Commutativity: 2,086 violations out of 20,000 operation pairs applied both ways round from a shared prefix. Idempotence: 0 violations out of 20,000 redeliveries.

Read those two lines together and the trap opens up. Redelivery is harmless and redelivery is also the repair: if your test finishes by syncing every replica with the full operation set a second time, the second copy of the insert arrives before the second copy of the delete, the tombstone finally lands, and everything agrees. I ran that harness against the broken code (2,000 operation sets, four replicas each, two full shuffled passes) and got zero divergence. Green light, wrong code.

There are two honest ways out. Make apply total — buffer the orphan:

function applyBufferingDelete(doc, op) {
  if (op.t === "ins") {
    if (doc.nodes.has(op.k)) return;
    const dead = doc.pendingDeletes.delete(op.k);   // an orphan delete was waiting
    doc.nodes.set(op.k, { value: op.value, parent: op.parent, deleted: dead });
  } else {
    const node = doc.nodes.get(op.k);
    if (node) node.deleted = true;
    else doc.pendingDeletes.add(op.k);              // consumed when the insert lands
  }
}

Or declare causal delivery a precondition and build the transport that provides it. That second option is what the literature assumes. An operation-based CRDT is specified against a reliable broadcast channel that delivers every update to every replica in an order the data type gets to constrain, and the commutativity requirement it places on you is narrower than it first looks: concurrent operations must commute. Concurrent, not all. An insert and the delete of that same insert are not concurrent, and they do not have to commute — provided something guarantees they never arrive backwards.

(I wanted to quote the Shapiro, Preguiça, Baquero and Zawirski tech report directly here, since it is where that distinction is set out most precisely. Its host is behind a bot wall I could not get through, and a quotation I have not read on the page is not a quotation, so you get my paraphrase and a pointer instead: the paper is INRIA RR-7506, Shapiro et al., 2011, on convergent and commutative replicated data types.)

Either answer is fine. Claiming "apply updates in any order, one or many times" while quietly depending on an ordering guarantee you never built is not.

Ordering two: one author, one machine, five keystrokes

The second failure needs no network at all. Press Home, leave the cursor there, and type O, L, L, E, H. Each character lands in front of the one before it, the line fills up backwards, and you end on HELLO. Every one of those five inserts anchors to the head of the document, so all five are siblings, and the read path has to break the tie between them.

The naive version broke it by sorting the random unique IDs. They are random, so the order is random:

// one replica, no concurrency, cursor held at position 0
const doc = new NaiveList();
for (const ch of "OLLEH") doc.insert(HEAD, ch);   // O first, H last; should render "HELLO"
doc.text();   // "EHLLO" ... "HLELO" ... "OLHLE"

Sorting five random strings hands you each of the 120 node orderings equally often, and two of them spell HELLO, because the two Ls are interchangeable. One in sixty, then. Over 200,000 trials it came out 3,319 times — 16.6 per thousand against a predicted 16.7. Three separate runs of a thousand trials each gave me 15, 16 and 7, which is why the count I quote is the one from the long run.

The tie-break is not a free choice. Kleppmann, Gomes, Mulligan and Beresford spell out the read path for RGA in Interleaving anomalies in collaborative text editors (PaPoC '19); the caption of their Figure 5 reads: "The document state corresponds to a depth-first pre-order traversal over this tree, with sibling nodes visited in descending timestamp order." Newest sibling first. That is what brings a run of inserts sharing one anchor back out in the order the cursor put them on screen, and it is why the ID has to be a Lamport timestamp rather than a UUID.

Ordering three: converged, identical, and unreadable

Fix the tie-break, fix the orphan delete, and the permutation harness goes quiet: 288,000 orderings, zero divergent. Then read the document.

// Alice types "AB" at the start of an empty doc.
// Bob concurrently types "XY" at the start of his copy.
// Both replicas, every delivery order:
"XAYB"

The read path was still breadth-first — a queue, level by level. A and X both hang off the root, so both get emitted before the traversal ever looks at B or Y. Every replica agrees. Every replica is wrong.

This one is worse than the other two, because comparing replicas cannot see it. Breadth-first is a deterministic function of the state; it passes the permutation test, and commutativity, associativity and idempotence, 20,000 cases each. It just shuffles your users' sentences together. Depth-first pre-order is the read; breadth-first is a different function that happens to typecheck.

What survives 288,000 orderings

Fifty-four lines, no dependencies. Lamport clock, tree of inserts, a set for deletes that outran their insert, depth-first read.

export const ROOT = "0@_";
const key = id => `${id.c}@${id.s}`;
const parse = k => { const i = k.indexOf("@"); return { c: +k.slice(0, i), s: k.slice(i + 1) }; };
// siblings in DESCENDING timestamp order; site id breaks the tie
const cmpDesc = (a, b) => {
  const x = parse(a), y = parse(b);
  return y.c - x.c || (y.s < x.s ? -1 : y.s > x.s ? 1 : 0);
};
 
export class RGA {
  constructor(site) {
    this.site = site;
    this.clock = 0;
    this.nodes = new Map();              // key -> { value, parent, deleted }
    this.kids = new Map([[ROOT, []]]);   // parentKey -> [childKey], kept sorted
    this.pendingDeletes = new Set();     // deletes that outran their insert
  }
  insertAfter(parentKey, value) {
    const k = key({ c: ++this.clock, s: this.site });
    const op = { t: "ins", k, value, parent: parentKey };
    this.apply(op);
    return op;
  }
  deleteKey(k) { const op = { t: "del", k }; this.apply(op); return op; }
  apply(op) {
    if (op.t === "ins") {
      if (this.nodes.has(op.k)) return;                  // idempotent
      this.clock = Math.max(this.clock, parse(op.k).c);  // Lamport catch-up
      const deleted = this.pendingDeletes.delete(op.k);  // consume an orphan delete
      this.nodes.set(op.k, { value: op.value, parent: op.parent, deleted });
      const arr = this.kids.get(op.parent) ?? [];
      arr.push(op.k); arr.sort(cmpDesc);
      this.kids.set(op.parent, arr);
    } else {
      const n = this.nodes.get(op.k);
      if (n) n.deleted = true; else this.pendingDeletes.add(op.k);
    }
  }
  keys() {
    const out = [];
    const walk = k => {
      for (const c of this.kids.get(k) ?? []) {          // depth-first, pre-order
        if (!this.nodes.get(c).deleted) out.push(c);
        walk(c);
      }
    };
    walk(ROOT);
    return out;
  }
  text() { return this.keys().map(k => this.nodes.get(k).value).join(""); }
  insertAt(i, ch) { const ks = this.keys(); return this.insertAfter(i === 0 ? ROOT : ks[i - 1], ch); }
  typeAt(i, str) { let at = i; return [...str].map(ch => this.insertAt(at++, ch)); }
  deleteAt(i) { return this.deleteKey(this.keys()[i]); }
}

Notice what apply never does. It never reads this.site, never asks a wall clock, never checks that the parent has arrived. An insert whose parent is still in flight sits in kids under a key nobody has yet, and is picked up for free the moment the parent lands. The state is a pair of grow-only maps and the render is a pure function over them. That, and not the tombstones, is why it converges.

The harness:

// assumes RGA and ROOT from the listing above
const assert = (cond, msg) => { if (!cond) throw new Error(msg); };
 
const perms = a => a.length <= 1 ? [a] : a.flatMap((x, i) =>
  perms([...a.slice(0, i), ...a.slice(i + 1)]).map(p => [x, ...p]));
 
const replay = ops => { const r = new RGA("_"); for (const o of ops) r.apply(o); return r.text(); };
 
// seeded PRNG so a failing case replays exactly
const rand = s => () => { s = s + 0x6D2B79F5 | 0; let t = Math.imul(s ^ s >>> 15, 1 | s);
  t = t + Math.imul(t ^ t >>> 7, 61 | t) ^ t; return ((t ^ t >>> 14) >>> 0) / 4294967296; };
 
// n replicas, random edits, 50% chance a peer hears about each one -> real concurrency
function genLog(seed, nRep, nOps) {
  const rnd = rand(seed);
  const reps = [...Array(nRep)].map((_, i) => new RGA(String.fromCharCode(65 + i)));
  const log = [];
  for (let i = 0; i < nOps; i++) {
    const ri = Math.floor(rnd() * nRep), r = reps[ri], vis = r.keys();
    const op = vis.length && rnd() < 0.3
      ? r.deleteKey(vis[Math.floor(rnd() * vis.length)])
      : r.insertAfter([ROOT, ...r.nodes.keys()][Math.floor(rnd() * (r.nodes.size + 1))],
                      "abcdefghij"[i % 10]);
    log.push(op);
    if (rnd() < 0.5) reps.forEach((o, j) => { if (j !== ri) o.apply(op); });
  }
  return log;
}
 
let sets = 0, orderings = 0, divergent = 0;
for (let seed = 0; seed < 400; seed++) {
  const log = genLog(seed, 3, 6);
  if (!log.length) continue;
  sets++;
  let base = null;
  for (const p of perms(log)) {
    orderings++;
    const s = replay(p);
    if (base === null) base = s;
    else if (s !== base) { divergent++; break; }
  }
}
console.log(sets, "op-sets,", orderings, "orderings,", divergent, "divergent");
assert(divergent === 0, "replicas diverged under permutation");

What that harness and its variants printed on the listing above, on Node 22:

• 400 op-sets, all 720 orderings each — 288,000 orderings, 0 divergent
• 3,000 op-sets of 14 operations across 4 replicas, 8 shuffles each — 24,000 orderings, 0 divergent
• 3,000 op-sets under shuffled delivery with 40% duplicates and 30% held back to the end — 122,656 deliveries, 0 divergent
• 20,000 operation pairs applied both ways from a shared prefix — 0 commutativity violations
• 20,000 redeliveries — 0 idempotence violations
• 4,000 three-way splits of an op log merged both ways — 0 associativity violations

Insert into a region another replica concurrently deleted (remove HELLO from HELLO WORLD while inserting __ inside it) and both replicas render __ WORLD, which is what Yjs does too. Delete-then-reinsert of the same character survives 500 random delivery orders with one outcome. Those are the cases people expect to be hard. For RGA they are not.

The orderings it converges on and still ruins

Strong eventual consistency does not promise you a readable document, and this is where the promise runs out.

Two users open Hello!. One types Alice between the o and the !; the other concurrently types Charlie into the same gap. Kleppmann et al. show Logoot and LSEQ merging this into Hello Al Ciharcliee! — converged, identical on both replicas, unreadable. RGA is proved not to do that when text is typed sequentially, and the paper says only two outcomes are legal. Measured, with Yjs 13.6.32 alongside for comparison:

RGA above: "Hello Charlie Alice!"   (same on every delivery order)
Yjs:       "Hello Alice Charlie!" or "Hello Charlie Alice!"

Yjs picks between the two legal answers on the randomly assigned clientID, so it is a coin flip across processes and a fixed answer within one. Four hundred fresh document pairs split 212 to 188. My RGA looks stable only because its site IDs are A and B and I chose them.

Then there is the case RGA does not survive, which the same paper calls the lesser anomaly. User 1 types reader before the !, then moves the cursor back and types dear in front of it. User 2 concurrently types Alice. Because RGA anchors each insert to the character immediately to its left, the first character of dear, of reader and of Alice all hang off the o in Hello, and nothing in the structure relates Alice to the gap between the other two runs.

Descending timestamp order puts dear first and the ! last, and drops Alice wherever its timestamp happens to fall. Over 2,000 random delivery orders my implementation gave one answer every time; Yjs again gave one of two, on the same 50/50 client-ID coin:

RGA above: "Hello dear Alice reader!"
Yjs:       "Hello Alice dear reader!" or "Hello dear reader Alice!"

Every replica converged in both systems, and every one of those answers splits one user's sentence in half to drop another user's word into the seam. The paper lists three legal outcomes for this scenario; those are all three of them.

The paper's stated worst case for RGA is a document typed back to front — cursor held at position 0, characters entered in reverse. That is the HELLO from ordering two, which was harmless with one author because descending timestamps put the run back in order. Add a second author and it stops being harmless: every character on both sides anchors to the head and is ordered by timestamp alone, so concurrent runs can shred each other completely. Two replicas, one entering abc back to front and one entering xyz, 200 trials with different site IDs:

Yjs is not RGA. Its INTERNALS.md names the difference: items carry "an originRight as well as an origin property, which improves performance when many concurrent inserts happen after the same character." An item pinned between a left and a right neighbour is not hanging off a single anchor, and the back-to-front case stops being degenerate. I verified the behaviour 200 times, not the proof — and the Yjs README is careful to say the formal verification effort covers preservation and commutativity so far.

The paper also proposes a repair for plain RGA: ship, with each insert, the timestamps of every sibling that already existed under the same anchor, and order concurrent inserts by the first timestamp at which their histories diverged. The authors call it a conjecture and leave the proof to future work. If you are picking an algorithm rather than writing one, that is the sentence to weigh.

Tombstones, weighed

Tombstones are the standard caveat and almost never a measurement. Same workload for both systems: each round, append 200 characters and then delete every other one of those 200.

// yjs 13.6.32, Node 22; RGA from the listing above
import * as Y from "yjs";
 
const ydoc = new Y.Doc(), ytext = ydoc.getText("t"), rga = new RGA("A");
for (let round = 1; round <= 5; round++) {
  const base = ytext.length, kept = rga.keys().length;
  ytext.insert(base, "x".repeat(200));
  for (let j = 199; j >= 1; j -= 2) ytext.delete(base + j, 1);
  for (let i = 0; i < 200; i++) rga.insertAt(rga.keys().length, "x");
  for (let j = 199; j >= 1; j -= 2) rga.deleteAt(kept + j);
  const graves = [...rga.nodes.values()].filter(n => n.deleted).length;
  console.log(round, rga.nodes.size, graves, rga.keys().length,
              Y.encodeStateAsUpdate(ydoc).byteLength);
}

Two nodes of structure per surviving character, forever, each one a separate object under a separate string key.

That right-hand column is not quite deterministic, for a reason worth knowing before you quote it at anyone. Y.Doc draws a random 32-bit clientID, every item that writes an explicit origin writes that id as a varint, and a clientID below 2^28 encodes in four bytes instead of five. Across 400 fresh documents I got 10,821 B at round five in 378 of them and 9,820 B in the other 22 — 22 being close enough to one in sixteen. Same code, same version, same workload; a byte of entropy in a header.

Change one thing — delete the 200 characters as a contiguous run instead of every other one — and Yjs's number stops moving. Five rounds, 1,000 characters typed and deleted, and encodeStateAsUpdate returns 24 bytes every round (22 on the short-clientID draw). The RGA still holds 1,000 nodes for an empty document.

That is not garbage collection. Yjs's INTERNALS.md describes deletes as a separate state-based structure, a set of ID ranges with no record of who deleted what or when, so contiguous deletion by one client collapses to a single run. The README states the limit plainly: "We can't garbage collect deleted structs (tombstones) while ensuring a unique order of the structs," then lists what it does instead: merge adjacent structs, drop the content of deleted ones, and collect tombstones fully only once the parent is gone and order stops mattering. Their figure for a real editing trace is the honest version of the tradeoff — the B4 benchmark document, 182k inserts and 77k deleted characters, carries a 4.5 KB delete set.

Nobody I checked is running plain RGA

This is the paragraph where collaborative-editing writing gets loose, so here is only what the vendors say in their own documentation.

Figma does not use a CRDT. Evan Wallace's How Figma's multiplayer technology works says it in as many words: "Figma isn't using true CRDTs though. CRDTs are designed for decentralized systems where there is no single central authority to decide what the final state should be." What they built is homegrown and inspired by the literature: last-writer-wins registers per property, fractional indexing for child order, with a central server as the authority. The same post is where you find that Figma cannot merge concurrent edits to one text value at all: change B to AB and to BC at once and you get one or the other, never ABC.

Microsoft's Fluid Framework does not use a CRDT either. Its FAQ answers the question directly: "Fluid does not use Conflict-Free Replicated Data Types (CRDTs), but our model is more similar to CRDT than OT. The Fluid Framework relies on update-based operations that are ordered using our Total Order Broadcast to prevent conflicts. This allows us to have non-commutative operations because there is an explicit ordering." A total-order broadcast is the thing a CRDT exists in order not to need.

Google Docs is the canonical operational-transformation system, not a CRDT one — Figma's post calls OT "the standard multiplayer algorithm popularized by apps like Google Docs." I could not find a Google engineering page claiming a move to CRDTs, and I am not going to relay one I cannot read.

Yjs and Automerge are real CRDTs. Yjs implements a modified YATA, and its README lists 56 products using it — AFFiNE, Evernote, GitBook, JupyterLab, Linear, Typst and Proton Docs among them. Automerge is maintained at Ink & Switch and has been production-ready since 2.0; the same lab's Peritext is a research prototype for rich-text inline formatting published at CSCW 2022, built on a simplified Automerge called Micromerge rather than a shipping library.

If a claim about who runs a CRDT does not come with a link to that company's own writing, treat it as folklore. Several of the most-repeated ones are contradicted by the vendor's own docs.

Converging on nonsense

Three orderings, three kinds of wrong. A reordered delete broke convergence outright, and was the easiest to find once each operation was delivered precisely once. A random sibling tie-break wrecked a document with one author and no network at all. The breadth-first read left every replica in perfect agreement about a scrambled string — and that is the one that would have shipped, because the obvious test, compare the replicas, returns true.

So test the algebra apart rather than in a bundle. Commutativity is what breaks, idempotence is what hides it, and only a harness that delivers each operation exactly once separates them. Then test the output, not just the agreement: type two runs of text concurrently into the same gap and read what comes back, because converging on nonsense is a passing test and a broken editor.

Which leaves the question I would put to my own code before anyone else's. My suite was green on an implementation that resurrected deleted characters, and it was green because it ended by syncing everybody with everything. If yours does the same thing at the bottom of the file, what has it been telling you?