Imagine you and another person edit the same document offline, on different devices. When you both get back online, the two copies must become one again. No referee, no locking, no lost edits. That apparently magical result is exactly what CRDTs (Conflict-Free Replicated Data Types) guarantee: a family of data structures designed so that multiple replicas converge in a mathematically predictable way.
The problem: two copies that must become one
In any distributed system the same data lives on several nodes at once. If those nodes may accept changes in parallel, sooner or later you get concurrent operations: two increments, two deletes, two edits of the same line. The question is not whether disagreement will happen, but how to resolve it.
The classic path is strong consistency: a single leader that serializes every write, as in a classic relational database. It works, but it forces everyone to talk to the same node — impossible on a disconnected phone, a partitioned cluster, or peer-to-peer collaborative editing. The alternative is eventual consistency: every replica answers immediately with what it knows and, sooner or later, everything converges. CRDTs exist so that convergence is guaranteed by construction instead of left to the luck of message ordering.
The core idea: operations that never argue
Every CRDT starts from a simple and powerful constraint: operations must commute. If A and B are two concurrent changes, applying “A first, then B” must produce exactly the same result as “B first, then A”. When that holds, it does not matter in which order messages arrive at each replica: they all end up computing the same state. It is a mathematical property, not a patch bolted onto a normal database.
That idea splits into two families:
- Operation-based CRDTs (CmRDT): each node broadcasts operations to the others. They require causally ordered delivery, or commutativity alone is not enough.
- State-based CRDTs (CvRDT): nodes exchange full states and merge them with a
mergefunction. That function must be commutative, associative, and idempotent — in other words, it must form a join-semilattice: a set where any pair of states has a computable least upper bound. This is the family that dominates in practice, because it tolerates best-effort delivery and lost or duplicated messages.
Cases as simple as they are revealing
The best way to understand them is to look at the classics. The G-Counter (grow-only counter) keeps a vector with one counter per replica: an increment only touches your own slot, and a merge takes the maximum of each slot with max. The total value is the sum of the vector. Because it only grows and max is commutative, associative, and idempotent, it converges without debate.
The PN-Counter joins two G-Counters (one for increments, one for decrements) to support subtraction without breaking the property. The OR-Set (observed-remove set) handles the trickiest case in the distributed world: “I added X while someone else was deleting it.” Each insert produces a unique tag (a UID plus the replica id), and a delete does not physically remove the element: it marks with tombstones the tags this replica has observed. An element appears in the set only when at least one of its tags is unmarked, so a re-add after a delete always works.
For simple registers there are two common schemes: the LWW-Register (last-writer-wins, where the newest timestamp wins) and the MV-Register (multi-value), which keeps all concurrent values and lets the user decide. The MV-Register is the basis of, for example, contact synchronization across Apple devices.
The price you pay
That elegance has a real cost: metadata and space. Tombstones are never physically deleted, and a G-Counter needs one vector entry per replica, so in the worst case the state grows without bound. That is why a CRDT optimizes for automatic convergence, not memory usage: you accept paying in size what you save in locking and centralized coordination.
Already in your pocket
Far from pure academic theory, CRDTs already power the collaborative editing of everyday tools. Yjs and Automerge are the best-known CRDT libraries and sit behind the synchronization of Notion and several multi-user editors. One clarifying note: Google Docs does not use CRDTs — it uses operational transformation (OT), another approach backed by a serializing server. CRDTs thrive precisely where you want neither a single point of failure nor any dependence on message order.
Convergence you can prove, not just wait for
The final appeal of CRDTs is that convergence is proven by construction: if the merge operation satisfies the three semilattice properties, any pair of convergent replicas ends in the same state — no leader, no locks, no retries. The next time a document you edit syncs without losing a single word, you will know what was behind it.
