This chapter matters because it shows the inverse of consensus: replicas converge to the same state automatically, without a leader, quorum, or locks — through the mathematical properties of the merge rather than coordination.
In practice this is the basis of local-first and collaborative editing: edits apply locally and instantly, work offline, and merge without conflicts once connectivity returns.
In interviews and design discussions it gives you the language to justify the choice between coordination (consensus) and convergence (CRDTs), and to name the honest cost of CRDTs — metadata, tombstones, and garbage collection.
Practical value of this chapter
Convergence without coordination
Replicas converge through commutative merge on a semilattice — no leader or quorum, unlike consensus.
Two families
CvRDT (state, merge=join) and CmRDT (operations with causal delivery) — pick by transport channel and message cost.
Text and local-first
Sequence CRDTs (RGA and others) and systems like Automerge/Yjs give offline edits and conflict-free merge in real editors.
The cost of convergence
Metadata, tombstones, and garbage collection are the main overheads; plan for them up front, not after state grows.
Contrasting neighbor chapter
Consensus: Paxos and Raft
The neighboring chapter solves the same replica-divergence problem the opposite way — through coordination, quorums, and a single leader. This chapter shows the other pole.
The neighboring chapter on consensus solves the problem of diverging replicas through coordination: a quorum, a single leader, and linearizability. Every write there passes through a network round of agreement, so a node cannot write without contacting a majority — and offline editing is impossible by definition.
This chapter is about the opposite approach. CRDTs — conflict-free replicated data types — let each replica accept a write locally, with no coordination at all, and then deterministically merge states afterward. The guarantee is called strong eventual consistency (SEC): replicas that have received the same set of updates must reach an identical state — with no leader election, no locks, and no manual conflict resolution.
The vocabulary that matters from here on: CvRDT (state-based, merging via the join of a semilattice) and CmRDT (op-based, commutative operations), version vectors for tracking causality, OR-Set and LWW registers as building blocks, and the tombstones you pay for correct deletions.
CRDTs are needed where replicas must accept writes independently — offline, on different continents, in a mobile app with no network — and still be guaranteed to converge to the same state as soon as updates are exchanged. The price of that convenience is metadata, tombstones, and a limited set of operations that can, in principle, be made commutative.
Foundation
Clock synchronization
The last-writer-wins strategy relies on physical clocks. Their skew turns directly into lost edits — which is the subject of the chapter on time.
The problem: offline edits and why last-writer-wins loses data
Picture a shared document or a shopping cart edited from several devices, including offline. A node must accept an edit immediately — otherwise the UI freezes waiting for the network. So concurrent changes are inevitable, and the only question is what the system does with them.
Last-writer-wins (LWW)
The write with the larger timestamp wins; the rest are silently dropped. Simple, but with clock skew real edits are lost, and two concurrent writes with equal timestamps need an arbitrary tiebreak.
Locks and coordination
Before writing, a node takes a lock or gathers a quorum. Correct, but it requires contacting a majority on every write — an offline node cannot write at all, and the latency adds a network round.
Coordination-free merge (CRDT)
A write is accepted locally, and concurrent versions are merged by a deterministic rule — so the result does not depend on delivery order and loses none of the committed operations.
The key observation: LWW is not "no conflict" but hidden data loss. If Alice adds an item to the cart offline while Bob clears it in parallel, naive last-writer-wins by clock throws away one of the edits. The famous Amazon Dynamo example is the cart, where concurrent changes must be merged rather than one of them chosen: a removed item must not "resurrect", yet an added one must not vanish.
Related theorem
CAP theorem
CRDTs are the engineering answer on the AP side of CAP: keep availability and partition tolerance, reducing the 'deferred' part of consistency to automatic convergence.
The consistency model: SEC, the semilattice, and why replicas converge
Plain eventual consistency promises only that replicas will "eventually" match, but says nothing about how to resolve concurrent writes — that is offloaded to the application. CRDTs strengthen the promise to strong eventual consistency (SEC): any two replicas that have delivered the same set of updates are in an identical state. Conflict resolution is built into the data type itself and is deterministic.
The lattice and the join operation
Replica states form a join-semilattice: there is a partial order over states, and any pair has a least upper bound — the merge result ⊔ (join). Merging two replicas is exactly computing their join.
For replicas to converge, the merge must be commutative (a ⊔ b = b ⊔ a), associative ((a ⊔ b) ⊔ c = a ⊔ (b ⊔ c)), and idempotent (a ⊔ a = a). Those three properties mean the order, grouping, and repeated delivery of updates do not affect the outcome.
Monotonicity as the engine
Every update moves the replica state up the lattice — toward a greater upper bound, never backward. Merge is monotone too: the join of two states is no smaller than either of them.
Monotonicity is precisely what saves you from reordered, lost, and duplicated network messages: a repeated update breaks nothing (idempotence), and a different order lands in the same point (commutativity and associativity). That is why CRDTs need no reliable ordered delivery — it is enough that each update eventually arrives.
How two replicas merge: a grow-only counter
The most intuitive CRDT is the grow-only G-Counter. Each replica holds a vector: "how much each replica has counted." A replica increments only its own slot, and merge takes the element-wise maximum of two vectors. Maximum is commutative, associative, and idempotent — so replicas converge under any delivery order. The counter value is the sum of the vector.
Why not just add two numbers? Because addition is not idempotent: if the same update arrives twice (and the network allows that), the sum doubles. A per-replica vector with the max operation removes the double counting: re-delivering [A:2] does not change the maximum. This is the canonical CRDT move — replace a non-idempotent operation with monotone growth along coordinates.
Reference
crdt.tech
A curated catalog of CRDT papers and implementations, maintained by the research community and the authors of the foundational work.
Two families: CvRDT (state-based) and CmRDT (op-based)
In their 2011 work, Shapiro, Preguiça, Baquero, and Zawirski identified two ways to build a CRDT that are equivalent in expressiveness. They differ in what exactly replicas send each other — a whole state or individual operations — and in what that demands of the network.
CvRDT — convergent, state-based
- Replicas send each other the whole state; the merge is the semilattice
join(least upper bound). - Merge requirements: commutativity, associativity, idempotence. Update requirement: monotonicity (only "upward").
- Tolerates loss, duplication, and reordering of messages: it is enough for states to be exchanged periodically over any channel, including anti-entropy gossip.
- Downside: shipping a full state is expensive. Fixed by delta-CRDTs — sending only lattice "deltas" instead of the entire state.
CmRDT — commutative, op-based
- Replicas send operations (e.g. "add element x with tag t"). They can be applied in any order as long as the operations commute.
- The delivery requirement is stricter: each operation must arrive exactly once and respect causal order (causal delivery) — provided by a reliable causal broadcast.
- Upside: little data on the wire — only the delta operation, not the full state.
- Downside: the "exactly once + causal order" requirement must actually be enforced by the transport, or convergence breaks.
The core trade-off is where you pay: CvRDTs push the complexity into state size (and ask almost nothing of the network), CmRDTs push it into delivery guarantees (but save bandwidth). In practice, hybrids are popular: delta-state CRDTs combine the compactness of op-based with the state-based tolerance of reordering.
The basic CRDT zoo and the catch of each
Almost every practical CRDT is assembled from a few simple constructions. The point is not so much to memorize them as to understand the catch — the spot where a naive implementation loses data or behaves unexpectedly.
| Type | Idea and merge | The catch |
|---|---|---|
| G-Counter | Grow-only counter: a per-replica vector, merge is element-wise max, the value is the sum. | Only supports increment. Decrement would break the monotonicity of max. |
| PN-Counter | Two G-Counters: P (increments) and N (decrements); value = sum(P) − sum(N). | Metadata grows linearly with the number of replicas; a 'negative balance' is formally possible. |
| G-Set | Grow-only set: merge is union, additions are monotone. | Elements cannot be removed at all — that would break monotonicity. |
| 2P-Set | Two-phase set: a set of added elements plus a set of removed ones (tombstones). | Removal is irreversible: an element removed once can never be added again. |
| OR-Set | Observed-Remove Set: every add gets a unique tag; remove drops only the observed tags. Add-wins. | Concurrent add and remove → the element stays (add-wins). Tags accumulate — garbage collection is needed. |
| LWW-Register / LWW-Map | A register (or map) with a timestamp: on merge the write with the larger timestamp wins. | A concurrent write with a smaller timestamp is lost silently; correctness depends on clocks and the tiebreak rule. |
Why OR-Set beats 2P-Set
In a 2P-Set, removal is irreversible: you cannot add the element back. OR-Set fixes this with a unique tag per add. A removal drops only the tags the replica had observed at the time of removal, so a new, concurrent add with a new tag survives the removal. The "add-wins" semantics usually matches user intuition: if someone added the element in parallel, it stays.
When LWW is acceptable
LWW is the cheapest CRDT and often enough for fields where "the latest value is the truth": order status, a profile name, a setting. But by construction it loses the concurrent write, so it is wrong wherever both edits carry meaning (text, sets, a cart). Riak and Cassandra use LWW widely — which is exactly why they require care with clock skew.
Paper
Interleaving anomalies, PaPoC 2019
Kleppmann, Gomes, Mulligan, and Beresford show that some sequence CRDTs interleave characters of adjacent words under concurrent inserts.
Text: sequence CRDTs, positional identifiers, and OT
Collaborative text editing is the hardest task for CRDTs, because here an element is not merely "present/absent" but occupies a position in a sequence, and positions shift concurrently. Numeric indices will not do: an insert at the start shifts all the others. The solution is stable positional identifiers that do not change under other people's inserts.
Sequence CRDTs (RGA, Logoot, LSEQ, Treedoc)
Each character is assigned a unique, densely orderable identifier: between any two positions a new one can always be inserted. RGA (Replicated Growable Array) links characters by references to a "left neighbor" and breaks ties by replica id; Logoot/LSEQ encode the position as a path in a tree of fractional indices.
A deleted character becomes a tombstone: it cannot be erased immediately, or a neighbor would lose its position anchor.
The interleaving problem
Kleppmann et al. (PaPoC 2019) showed a subtle defect: if two replicas concurrently insert whole words in the same place, some sequence CRDTs can interleave their characters — "HELLO" and "WORLD" turn into "HWEOLRLLOD". Logoot and LSEQ exhibit the full defect; RGA shows only a weaker variant (for right-to-left insertions).
This loses no data (SEC holds), but produces nonsensical text. A well-designed sequence CRDT must keep one author's concurrent inserts together, not intermixed.
OT — the alternative: transform operations instead of built-in commutativity
Operational Transformation (OT) solves the same task differently. Instead of stable identifiers it keeps ordinary indices but transforms an incoming operation against the ones already applied: if someone inserted a character to the left, your insert's index shifts by one. That is how Google Wave worked and how Google Docs works.
The catch of OT is that transformation functions are hard to get right for all pairs of operations, and classic OT usually needs a central server to order operations. CRDTs are more popular for local-first and p2p scenarios precisely because commutativity is built into the data type and no ordering server is needed — at the cost of metadata and tombstones.
Foundation
Logical time and causality
A version vector is a relative of vector clocks: it records 'what a node has already seen', letting you tell causally related updates from concurrent ones without physical clocks.
Causality: version vectors and detecting concurrency
To decide whether one edit "won" or the two are concurrent, you need to track causality — and physical clocks will not do for that. CRDTs rely on logical time.
Version vectors and dotted version vectors
A version vector keeps a counter per replica and answers "what have I already seen." Comparing two vectors tells you whether one version precedes the other (one dominates component-wise) or they are concurrent (neither dominates) — in which case you must merge.
A dotted version vector is a refinement that precisely distinguishes concurrent writes even from a single client and avoids false conflicts; this is exactly what Riak uses to version objects.
Causal delivery for op-based
CmRDTs require an operation to be applied only after everything it causally depends on. A causal broadcast provides this: each message carries what its author has already seen, and the receiver buffers an operation until its predecessors arrive.
Without causal order, an op-based CRDT might, for instance, try to remove an element before its addition arrives — and convergence breaks. So "exactly once + causality" is not a wish for CmRDTs but a correctness condition.
Overheads: metadata, tombstones, state growth
Automatic convergence without coordination is paid for in memory and complexity. This is the main reason CRDTs are not universal.
Metadata grows
OR-Set tags, position identifiers, version vectors — all of these are per-element metadata. For text the metadata easily exceeds the text itself several times over.
Tombstones accumulate
Deleted elements cannot be erased immediately: they remain tombstones so concurrent replicas neither 'resurrect' what was deleted nor lose position anchors.
Garbage collection is hard
Removing a tombstone is safe only once every replica is guaranteed to have seen the deletion. That needs knowledge of every replica's progress — a distributed problem of its own.
When CRDTs are expensive: with a huge number of replicas (per-replica metadata in counters), with a long edit history of one document (accumulated tombstones), with operations that inherently commute badly (moving an element, transactional invariants such as "uniqueness" or "sum = 100"). Modern implementations like Yjs and Automerge invest heavily in compact encoding and garbage collection precisely to keep the overhead in check.
Implementation
Yjs
A high-performance CRDT library for collaborative editing: shared types, integrations with ProseMirror, Monaco, CodeMirror, and transport-agnostic sync.
Systems in practice and local-first
| System | Where and how it uses CRDTs |
|---|---|
| Automerge | A JSON-like document as a CRDT for local-first apps: works offline, merges concurrent edits without loss, keeps the full change history. Co-authored by Martin Kleppmann. |
| Yjs | By its own claim the fastest implementation for collaborative editing: shared types (Text, Array, Map), editor integrations, transport-agnostic sync with no central server. |
| Redis Active-Active (CRDB) | Geo-distributed multi-primary replication built entirely on CRDTs: predictable conflict resolution plus vector clocks give strong eventual consistency across clusters. |
| Riak | A distributed KV store with the Riak DT library (counters, sets, maps, registers) and dotted version vectors for object versioning. |
Local-first: why CRDTs are loved
The idea of local-first software (a term from the Ink & Switch group, with Kleppmann among the authors) is that data lives on the user's device, works offline and instantly, and the network is only needed for synchronization. CRDTs are a natural foundation for that approach: they let you edit without an arbiter server and converge when replicas meet. That is why CRDTs are more popular than OT where offline, p2p, and data ownership matter, while OT stays practical in the classic client-server model of Google Docs.
Trade-offs and common mistakes
Common mistakes
- Treating LWW as "conflict-free" — it actually drops the concurrent write silently.
- Adopting an op-based CRDT without ensuring "exactly once + causal order" delivery.
- Expecting invariants ("the sum is always 100", "the nickname is unique") — CRDTs guarantee convergence, not global constraints.
- Forgetting tombstone garbage collection — the state grows without bound.
When CRDTs are the right choice
- You need offline editing and an instant local response.
- Concurrent changes must be merged, not one of them chosen (text, sets, a cart).
- Deferred consistency is acceptable — there is no hard linearizability requirement per write.
- Domain operations can, in principle, be made commutative.
What to remember
- CRDTs give strong eventual consistency without coordination: replicas with the same set of updates reach an identical state.
- Convergence rests on semilattice math: merge is commutative, associative, and idempotent, and updates are monotone.
- CvRDTs pay in state size and ask almost nothing of the network; CmRDTs save bandwidth but require 'exactly once + causal order' delivery.
- LWW is not conflict-free — it loses the concurrent write; OR-Set with tags and add-wins is closer to user intuition.
- Text CRDTs use stable positional identifiers and tombstones; watching for interleaving and garbage collection is mandatory.
- The price of convenience is metadata and tombstones; for hard invariants and linearizability you need the consensus of the neighboring chapter.
When CRDTs can hurt
CRDTs remove coordination but do not repeal physics: they do not give linearizability, do not enforce global invariants, and accumulate metadata. Where a domain needs a single agreed decision right now (debiting money, uniqueness, a quorum commit), the right tool is the consensus of the neighboring chapter, not conflict-free merge.
Sources and further reading
Source map: Shapiro/Preguiça/Baquero/Zawirski provide the formal CRDT base; Kleppmann et al. cover text-CRDT anomalies; crdt.tech is a guide to papers; Yjs, Automerge, and Redis document practical implementations. Claims about metadata, garbage collection, character order, and conflict UX need to be checked against the chosen CRDT type and sync model.
Related chapters
- Consensus: Paxos and Raft - The contrasting neighbor: agreement through coordination, quorums, and a leader instead of coordination-free convergence.
- CAP theorem - Explains why CRDTs pick availability and partition tolerance, paying with deferred consistency.
- Clock Synchronization in Distributed Systems - Shows why LWW on physical clocks loses data and why causality has to be tracked logically.
- Case study: a Google Docs-class collaborative editor - An applied build of collaborative editing where OT, CRDTs, presence, and cursor sync meet.