CRDTs: The Data Structure That Makes Distributed Consistency Optional and What It Costs
Conflict-free Replicated Data Types let replicas diverge freely and still guarantee eventual convergence. Here is the math behind why that works, a tour of the most useful types, and an honest look at where CRDTs break down.
1. The Problem CRDTs Solve
Imagine two users editing a shared counter. Node A increments it from 5 to 6 while, simultaneously, Node B also increments it from 5 to 6. When they sync, what should the result be? Naively merging the two writes gives you 6, but the correct answer is 7 — two distinct increments happened and both should count.
Traditional distributed systems solve this with coordination: locks, consensus protocols such as Paxos or Raft, or a central coordinator that serialises every write. Coordination works, but it carries a price: latency spikes, unavailability during network partitions, and throughput bottlenecks. According to the CAP theorem, in the presence of a partition you must choose between consistency and availability.
CRDTs take the other branch of that choice. They sacrifice strong consistency — you will not get linearisable reads — but they guarantee something weaker and often sufficient: eventual consistency with mathematical certainty. No coordinator, no consensus round, no lock. Replicas can accept writes offline, sync in any order, and the states will always converge to the same value.
Where you already use CRDTsGoogle Docs and Apple Notes use CRDT-derived algorithms for collaborative text editing. Redis uses a CRDT internally for its sorted-set replication in Redis Enterprise Active-Active. Riak KV exposes CRDTs as first-class data types. Figma’s multiplayer engine is built on a variant of the same ideas.
2.The Mathematics: Join-Semilattices and Monotone Functions
CRDTs are not a clever hack — they rest on a precise mathematical foundation. Understanding that foundation is what makes the convergence guarantee feel inevitable rather than lucky.
Join-semilattices
A join-semilattice is a partially ordered set in which every pair of elements has a least upper bound — called the join, written ⊔. Think of a set of subsets ordered by inclusion: the join of {A, B} and {B, C} is {A, B, C}. Three properties define a valid join operation:
Semilattice axioms (must all hold for convergence to be guaranteed) Commutativity: a ⊔ b = b ⊔ a Associativity: (a ⊔ b) ⊔ c = a ⊔ (b ⊔ c) Idempotency: a ⊔ a = a — together these mean: merge in any order, any number of times → same result
These three properties are exactly what a distributed merge function needs. Commutativity means messages can arrive in any order. Associativity means you can batch merges arbitrarily. Idempotency means you can safely replay a message you already received, which is critical in at-least-once delivery networks.
State-based vs. operation-based CRDTs
There are two families of CRDTs, and the distinction matters for what your network layer must guarantee.
| Property | State-based (CvRDT) | Operation-based (CmRDT) |
|---|---|---|
| What is transmitted | Full state snapshot | Individual update operations |
| Merge function | Must satisfy semilattice axioms on the state space | Concurrent operations must commute |
| Network requirement | Eventual delivery only | Exactly-once delivery (or idempotent ops) |
| Bandwidth | High — full state per sync | Low — delta operations only |
| Typical use | Counters, sets, flags | Collaborative text editing |
In practice, modern systems often use delta-state CRDTs — a hybrid that sends only the portion of state that changed since the last sync, achieving the bandwidth efficiency of operation-based CRDTs while requiring only eventual delivery from the network.
3. A Tour of the Main CRDT Types
Rather than an exhaustive catalogue, what follows covers the types you are most likely to encounter in real systems — along with the subtleties that catch developers off guard.
G-Counter: the simplest CRDT in code
The G-Counter is the “Hello, World” of CRDTs. Implementing it from scratch takes about a dozen lines of Java and, as a result, makes the core idea immediately tangible.
import java.util.HashMap;
import java.util.Map;
public class GCounter {
// One slot per replica node, identified by its node ID
private final Map<String, Long> counts = new HashMap<>();
private final String nodeId;
public GCounter(String nodeId) { this.nodeId = nodeId; }
// Local increment — no coordination needed
public void increment() {
counts.merge(nodeId, 1L, Long::sum);
}
// Global value is the sum of all slots
public long value() {
return counts.values().stream().mapToLong(Long::longValue).sum();
}
// Merge: take the maximum of each corresponding slot (? operation)
public void merge(GCounter other) {
other.counts.forEach((id, v) ->
counts.merge(id, v, Math::max) // max is the join for natural numbers
);
}
}
// ?? Demo: two nodes increment concurrently, then sync ??
GCounter nodeA = new GCounter("A");
GCounter nodeB = new GCounter("B");
nodeA.increment(); // A = {A:1}
nodeA.increment(); // A = {A:2}
nodeB.increment(); // B = {B:1}
// Sync in any order — result is always 3
nodeA.merge(nodeB);
nodeB.merge(nodeA);
// nodeA.value() == 3 ✓
// nodeB.value() == 3 ✓
Notice that Math::max is the join operation here. It satisfies all three semilattice axioms: max(a,b) = max(b,a), max(max(a,b),c) = max(a,max(b,c)), and max(a,a) = a. The whole convergence guarantee falls out of those three lines.
OR-Set: where the semantics get interesting
The OR-Set is worth studying because it reveals the design trade-offs that all CRDT authors face. Earlier designs — the 2P-Set and the U-Set — had intuitive semantics but either disallowed re-adding removed elements or required a global source of unique IDs. The OR-Set solves both problems by tagging every addition with a universally unique identifier (UUID in practice) and defining removal as “remove all tags I have currently observed for this element.”
The result is that a concurrent add(x) and remove(x) always resolves in favour of the add — because the add generates a fresh tag that the remove operation never saw. Whether that semantic is correct depends entirely on your application. For a collaborative shopping cart, it is usually right (the person who added the item wins). For a permission revocation system, it is emphatically wrong.
“The right CRDT for your use case is the one whose conflict-resolution semantics match what your users actually expect — not the one with the most elegant theory.”
4. How Convergence Actually Happens
The semilattice proof guarantees that if every replica eventually receives every update, they will converge. But “eventually” hides a lot of engineering. In practice, convergence requires an anti-entropy protocol — a background process where replicas periodically exchange state and reconcile differences.
The most common pattern is gossip (epidemic) propagation: each node, at random intervals, picks a small set of peers and exchanges its current state (or delta). The convergence rate is probabilistically bounded and depends on the gossip fanout and the network topology.
Gossip Convergence: Fraction of Nodes Converged Over Time
One important subtlety: convergence tells you nothing about when a replica will see a given update. If Node A is partitioned for six hours, its stale reads are perfectly valid CRDT behaviour — the data structure makes no availability guarantee for reads. Applications that need “read your own writes” semantics need to route reads back to the originating replica or maintain a causal consistency layer on top.
5. What CRDTs Cost You
The mathematical elegance of CRDTs can make them sound like a free lunch. They are not. Each benefit comes with a specific and sometimes painful cost.
Tombstone Accumulation in a PN-Counter Over Time
1. Metadata bloat and the tombstone problem
Every deletion in a set-based CRDT leaves a tombstone — a permanent record that the element was removed. Without tombstones, a replica that missed a delete would simply re-add the element on the next sync. Over time, tombstones accumulate and can dominate the storage cost of the data structure. Production deployments need a garbage-collection protocol (sometimes called “stable compaction”) that only removes tombstones once every replica has acknowledged the deletion — which, ironically, requires a coordination step.
2. Conflict resolution is semantic, not automatic
CRDTs resolve structural conflicts automatically, but they cannot resolve semantic conflicts. If two users concurrently rename a file to different names, an LWW-Register silently discards one rename. If two users concurrently delete and modify the same document section, the OR-Set semantics favour the modification. These outcomes may or may not align with user intent. The CRDT handles the mechanics of convergence; your application must handle the meaning.
3. Causal consistency is not guaranteed by default
A plain CRDT sync does not preserve causality. Node B might receive “Alice replied to Bob’s message” before it receives “Bob’s message” — because gossip delivers updates in arbitrary order. Applications that need causal ordering (which includes most chat, collaboration, and workflow systems) must layer a vector-clock or causal-consistency protocol on top of the CRDT.
| Limitation | Practical Impact | Mitigation |
|---|---|---|
| Tombstone growth | Unbounded storage cost for delete-heavy workloads | Stable compaction with a coordination round |
| Semantic conflicts | Silent data loss that users notice | Application-level conflict UI; intent-preserving CRDTs |
| No causal ordering | Out-of-order delivery breaks application logic | Vector clocks; causal broadcast middleware |
| LWW clock skew | Writes from clocks running behind are silently dropped | Hybrid Logical Clocks (HLC) instead of wall clocks |
| Throughput under churn | High-churn workloads amplify gossip traffic | Delta-state CRDTs; adaptive gossip fanout |
6. Byzantine-Fault-Tolerant CRDTs: The Frontier
Standard CRDTs assume a crash-fault model: nodes may fail by stopping, but they do not send malicious or corrupted messages. In open, adversarial networks — think peer-to-peer systems, blockchain-adjacent applications, or multi-tenant edge deployments — this assumption breaks down. A single Byzantine node can forge operations, replay deleted values, or inject arbitrary state into the merge function, corrupting the CRDT on every honest replica it syncs with.
This limitation received serious academic attention through the 2020s. The key insight from researchers at INRIA and Imperial College London (Kleppmann et al., 2022) is that Byzantine-fault tolerance and CRDT semantics can coexist, but only by adding a cryptographic authentication layer and redefining the merge function to reject unauthenticated state.
Concretely, Byzantine-fault-tolerant (BFT) CRDTs require three additions beyond a standard CRDT:
The trade-off is significant: BFT CRDTs are considerably more expensive in both computation (signature verification per operation) and communication (causal history exchange). As a result, they are mainly applicable to scenarios where Byzantine tolerance is a hard requirement — decentralised collaboration tools, auditability-first data structures, and multi-party computation — rather than typical enterprise distributed systems.
Active research areaBFT CRDTs are not production-standard yet. The Kleppmann et al. framework is theoretically sound but the engineering implementations remain nascent as of mid-2025. If you need Byzantine tolerance today, you are likely combining a standard CRDT with a Byzantine-fault-tolerant consensus protocol (BFT-SMaRt, Tendermint) for write validation, accepting the coordination cost on the write path.
7. What We Have Learned
This article walked through CRDTs from first principles to the cutting edge. To summarise the key takeaways:
- The core trade-off: CRDTs trade strong consistency for availability and partition tolerance, guaranteeing eventual convergence without any coordinator or consensus round.
- The math that makes it work: Join-semilattice structure — commutativity, associativity, idempotency — ensures that merging diverged states in any order always produces the same result.
- Two families: State-based CRDTs (CvRDTs) transmit full state and need only eventual delivery; operation-based CRDTs (CmRDTs) are bandwidth-efficient but need exactly-once delivery. Delta-state CRDTs offer a practical middle ground.
- Practical types: G-Counter (grow-only, slots per node), PN-Counter (two G-Counters), OR-Set (tagged additions with tombstoning), LWW-Register (timestamp-wins, clock-sensitive).
- Hidden costs: Tombstone accumulation, semantic conflicts the data structure cannot resolve, no built-in causal ordering, and LWW’s dependence on synchronised clocks are all real production concerns.
- The frontier: Byzantine-fault-tolerant CRDTs add cryptographic signing and causal history to resist malicious nodes — promising for decentralised systems but computationally expensive and not yet production-standard.
