When two or more people type on the same document at once, a very simple idea to state becomes a genuinely hard computing problem. This is not a minor design flaw but a real limit: two copies of the same file that are edited separately end up telling different stories. Collaborative editors such as Google Docs, Notion or Figma have solved this with a family of data structures whose name is cryptic but whose idea is elegant: CRDTs (conflict-free replicated data types).
The problem: two copies that start to drift apart
Picture a document that lives on your laptop and on your colleague’s. Both are replicas, copies of the same initial state. If you delete a sentence in your copy while she edits it in hers at the same time, there is no longer a single story: there are two diverging versions. Syncing them later forces you to decide which of the two edits “wins”.
The internet is full of systems that face the same dilemma in similar terms: all the servers of a replicated database and distributed caches share it. The goal is called convergence: that all replicas, no matter the order in which they synchronize, end up in the same final state. If two nodes always converge to the same result, the arrival order of messages stops mattering.
Why “last writer wins” is a bad solution
The crudest remedy is to stamp every edit with a timestamp and keep the most recent one, the well-known last-writer-wins. It is simple and works in some cases, but it destroys information: if you spent hours polishing a paragraph and your colleague touched that same area a second later, your whole work vanishes without warning. Worse, timestamps depend on each machine’s clock, and those clocks are never perfectly synchronized.
Here comes the key idea. Instead of synchronizing states (the whole document), you synchronize operations (what each person changed). And the genius of a CRDT is that its operations are designed to be combined in any order and always yield the same result. To achieve this they must satisfy three mathematical properties:
- Commutativity: whether I apply your change and then mine, or the other way around, the result is identical.
- Associativity: I can group operations however I like; parentheses do not matter.
- Idempotence: applying the same operation twice changes nothing, which is essential if the network resends a duplicated message.
With these three properties, two replicas that receive the same set of operations in a different order converge on their own. There is no central referee and nobody has to be locked out: the data structure itself reconciles the copies.
Registers, counters and the hard case: text
There are CRDTs for every basic data type. A register holds a value that can be overwritten; the version that does not lose edits attaches a logical timestamp to every write and keeps the one with the highest priority, rather than relying on the wall clock. A counter that only grows is implemented with a variant called G-Counter (grow-only), in which each replica adds to its own position of a vector and the total is the sum of all positions: simultaneous increments are never lost.
But text is the real challenge. A document is not a number to add up: it is an ordered sequence of characters, and two people can insert text at the same point at the same time. Who goes first? To settle this, sequence CRDTs give every character a unique identifier, made of a Lamport timestamp and a replica number. A Lamport timestamp is a logical counter that orders events consistently; the replica number acts as the tie-breaker when two stamps coincide.
When you delete a character, it is not really removed: it is flagged as a tombstone. It sounds inefficient, and it is, but it guarantees that inserts by others pointing to that position still make sense after synchronization. Algorithms such as RGA (Replicated Growable Array) or the YATA structure used by the Yjs library implement exactly this reasoning to move cursors, merge histories and keep every user on the same paragraph.
The classic alternative: operational transformation
Before CRDTs, the dominant technique was operational transformation (OT), used by pioneers such as Google Wave and, in its most refined form, by Google Docs itself. In OT, when two edits conflict, a server transforms them so each applies on top of the state already modified by the other. It is fast and smooth, but it demands a central coordinator and notoriously delicate transformation rules: a single unhandled case can make replicas diverge and corrupt the document.
CRDTs were born partly to escape that fragility. Because they need no coordination, they allow offline editing and later synchronization, a paradigm known as local-first: the data lives on your device and the cloud acts as a sync channel, not as the single source of truth. Libraries such as Yjs or Automerge put this model into practice and back modern editors and multi-user design tools.
It is not magic: it has limits too
None of this is free. Keeping tombstones and a history of operations makes CRDTs grow in memory, and very large documents or thousands of collaborators require compaction strategies (removing tombstones and folding history) and fragmentation. When two people edit exactly the same line at the same time, the system must pick a winner by deterministic tie-breaking rules that do not always match human intent. And operations that truly need a global order, such as moving an entire block, still rely on centralized sync services layered on top of the local structure.
Next time you watch a colleague type into your own document without a single word being lost, you will know there is no all-powerful server deciding every keystroke. There is a data structure designed so that machines, even when they sync late, badly and out of order, always end up telling the same story.
