When two people edit the same document at the same time —a cloud document, a Figma board, a distributed chat—, what stops each person’s last write from stepping on the other’s and losing work? The answer that matured in the 1990s and is now in mass production is called a CRDT: a data type designed so that two machines can edit in parallel and converge on their own, with no central arbiter.
The underlying problem: the conflict of simultaneous editing
When there is no non-negotiable central order, two replicas of the same data can diverge. Alice types “tro” at position 5 of a paragraph while Bruno inserts “!?” at position 8: both edits are legitimate, but a simple “last write wins” fabricates inconsistency depending on which replica applies it first. You need a data type that, under any interleaving of operations, converges to the same result on every replica. That is exactly the contract of a CRDT.
What a CRDT is
A CRDT (Conflict-free Replicated Data Type) is a data structure with a mathematical guarantee: given the same set of operations, all replicas end in the same state, with no coordinator and no manual conflict resolution. The key is that its operations are commutative, associative and idempotent, or that the whole state can be merged with a join operation that obeys those same three laws —those of a semilattice.
Operations that accept any order: commutativity
For two operations to be applicable in any order and give the same result, they must commute. A shared counter is the classic example: each replica keeps one cell per origin —a G-Counter— so the sum is commutative. Operation-based CRDTs (op-based) also depend on messages being delivered in causal order, achieved with vector clocks: each node keeps a counter per participant, and a message is only applied once every message that causally precedes it has been applied.
States that merge: the semilattice
In state-based CRDTs (CvRDTs), when two replicas meet they exchange their full state and merge it with a join. If the set of states with its merge operation is a semilattice —partially ordered, idempotent and commutative—, a convergence theorem guarantees that any pair of replicas eventually equalizes given enough propagation. The advantage is robustness: lost intermediate messages do not matter, the states just need to meet.
Registers, sets and sequences: the classic CRDTs
The most widely used types illustrate the range of solutions:
- Last-Writer-Wins Register: stores a (value, timestamp) pair and the write with the highest timestamp wins. Simple, but it requires a coherent clock —usually a Lamport clock, not the wall clock.
- G-Counter and PN-Counter: counters with one cell per replica; they only allow increment (G) or increment and decrement (PN) using per-node values.
- OR-Set (Observed-Remove Set): a set where each element carries unique identifiers and deletion requires having observed the ids the replica knows, so “add after delete” does not lose the element again.
- For text documents we use sequences such as RGA or LSEQ: they give each character a unique identifier and an order, allowing insertion at any point without reindexing the whole document.
Why it shows up in collaborative apps
Google Docs uses its own operational transformation (OT) model, but the new generation —Figma and its sequences, Miro’s whiteboards, editors built on Yjs and Automerge, Atom’s late Teletype— relies on CRDTs. The practical advantage is enormous: no central server with authority over ordering is needed, replicas can work offline and sync later, and end-to-end encryption is possible because the server only relays operations without needing to read them.
Efficient synchronization: Merkle trees
Exchanging the whole state is expensive. Yjs and Automerge structure the document as a Merkle tree —each node summarizes its children’s content in a hash— so two replicas compare root hashes and only transmit the divergent branches. Editing a paragraph in a huge document transfers only that paragraph’s operations.
The price you pay
It is not free magic. State grows: in an OR-Set, deleted elements become tombs so that replicas that have not yet seen them do not reintroduce them, requiring coordinated garbage collection. Text sequences consume more memory than a plain string. And certain problems —moving a block, schema changes— remain hard, which is why Figma or Google combine CRDTs with a server layer for the cases that do require authority.
The quiet revolution
Every time you edit a document in parallel with another person and do not lose a single letter, a semilattice is quietly working on several machines at once. Collaborative editing is no longer an engineering compromise between server and client: it is pure mathematics applied to two hands on the same text.
