CRDT: Conflict-Free Replicated Data Types

The Core Problem: Coordination Is Expensive

In a distributed system, multiple copies, or replicas, of the same data often live on different machines: a phone, a laptop, a server in one data center, a server in another. If two replicas are updated at the same time while disconnected, a naive merge can produce different results depending on which update is applied first. Classic solutions force replicas to coordinate before accepting a write, using locks, consensus protocols, or a single leader that all writes must pass through. Coordination guarantees a single, agreed-upon order of updates, but it comes at a steep cost: every write must wait for a round trip to the coordinator, and if the network partitions, the coordinator becomes unreachable and writes must be refused entirely. This tension is captured by the CAP theorem, which observes that a distributed system cannot simultaneously guarantee full consistency and availability during a network partition. CRDTs sidestep this tradeoff for a specific class of problems by giving up the requirement that replicas agree on an order of operations. Instead of asking, in real time, which update happened first, a CRDT is designed so that the final answer does not depend on order at all. Every replica can accept writes immediately, locally, with zero coordination, zero waiting, and zero risk of being blocked by a network outage. The price paid is that CRDTs only work for data structures whose merge operation can be defined with the right mathematical properties, and the set of possible operations on the data is more constrained than in a general-purpose database with arbitrary transactions. But for many real applications, counters, sets, registers, ordered sequences, text documents, that constraint is entirely acceptable, and the payoff is a system that keeps working smoothly even when parts of the network are offline for hours or days, later reconciling automatically and correctly.

The Mathematics: Join-Semilattices

The convergence guarantee behind every CRDT rests on a branch of algebra called lattice theory. A join-semilattice is a set of possible states equipped with a binary merge operation, often written as a join, that combines any two states into a new state representing their least upper bound. For a merge function to make CRDTs work, it must satisfy three properties. First, it must be commutative: merging state A with state B produces the same result as merging B with A. This matters because messages between replicas can arrive in any order, and the final state must not depend on which replica happened to receive an update first. Second, it must be associative: merging A with B, then merging the result with C, produces the same outcome as merging B with C first and then merging with A. This allows replicas to combine updates in batches, or receive them through different network paths, without changing the outcome. Third, it must be idempotent: merging a state with itself, or applying the same update twice, leaves the state unchanged. This matters enormously in real networks, where messages can be duplicated or retransmitted, and a system that is not idempotent would double-count a repeated delivery. Together, these three properties mean that no matter how many times, in what order, or how many duplicates of each update every replica receives, the sequence of merges always arrives at the identical final state. This is sometimes called Strong Eventual Consistency: not just that replicas will eventually agree, but that any two replicas which have received the same set of updates are guaranteed to be in the same state right now, with no waiting period and no possibility of a lingering conflict.

Two Families: State-Based and Operation-Based

CRDTs come in two major flavors that achieve the same convergence guarantee through different mechanisms. The first is the state-based or convergent CRDT, often abbreviated CvRDT. In this design, each replica maintains its entire local state and periodically ships that entire state to other replicas, perhaps over a gossip protocol. When a replica receives another replica's state, it merges the two using the join-semilattice operation described earlier, which effectively takes the combined maximum across every tracked value. Because merge is commutative, associative, and idempotent, it does not matter how partial, stale, or duplicated these state transmissions are; repeated or out-of-order merges simply converge toward the same answer. The tradeoff is bandwidth: transmitting the full state can be expensive as the data grows large, although deltas and version vectors are commonly used in practice to shrink the payload. The second family is the operation-based or commutative CRDT, sometimes called CmRDT or CoRDT. Here, replicas do not exchange full state; instead they broadcast the individual operations applied locally, such as increment this counter or add this element to this set. Every replica applies every operation it receives to its own local copy. For this to converge correctly, the operations themselves must commute with one another, meaning that applying operation X then operation Y must produce the same result as applying Y then X, at least for any operations that could plausibly arrive out of order. Operation-based CRDTs typically assume a reliable, exactly-once delivery channel, or need extra bookkeeping like sequence numbers to guard against lost or duplicated messages, since unlike the state-based approach, replaying the same operation twice can break correctness unless it was specifically designed to be idempotent as well.

A Concrete Example: The Grow-Only Counter

The simplest CRDT to reason about is the Grow-only Counter, or G-Counter, which supports only increments, never decrements. Rather than storing a single shared number, each replica maintains its own private counter, indexed by that replica's unique identifier. When replica A increments the counter locally, it only increases its own slot in its local array; it never touches the slots belonging to other replicas. To read the total count at any moment, a replica simply sums every slot across all replicas it knows about. The merge operation between two replicas' arrays is defined slot by slot: for each replica identifier, take the maximum of the two recorded values. Because taking a maximum is commutative, associative, and idempotent, merging two G-Counters in any order, any number of times, always yields the same combined array, and therefore the same total sum. Consider three replicas, A, B, and C. Replica A increments its own slot twice, reaching a local value of 2, while completely offline. Replica B, also offline, increments its own slot three times, reaching 3. When A and B eventually reconnect and merge, each takes the maximum of every slot: A's slot becomes 2, B's slot becomes 3, and the total reads 5, correctly reflecting all five increments from both replicas, even though the two replicas performed their increments simultaneously and never communicated during that period. A related and equally instructive example is the Last-Write-Wins Register, or LWW-Register, which stores a single value alongside a timestamp; the merge rule simply keeps whichever value carries the later timestamp, using the replica identifier as a tiebreaker for equal timestamps, which is itself commutative, associative, and idempotent.

CRDTs in the Real World

CRDTs are not merely a theoretical curiosity; they underpin systems that people use daily. Collaborative document editors are the most commonly cited example, and the underlying idea, letting multiple people type simultaneously and merging their edits automatically, is exactly the problem CRDTs were built to solve. It is worth noting precisely, however, that many well-known collaborative editors, including Google Docs, historically built their real-time merging on a different technique called Operational Transformation rather than CRDTs, though newer editors and libraries increasingly adopt sequence CRDTs such as RGA or Logoot specifically because they simplify peer-to-peer collaboration without a central server. Distributed databases are another major adopter. Redis offers CRDT-based data types in its Active-Active geo-distribution feature, allowing multiple Redis clusters in different regions to accept writes independently and merge automatically without conflicts. Riak, an early distributed key-value store, built native support for CRDT counters, sets, maps, and registers directly into its data model, letting applications get strong eventual consistency without hand-rolled conflict resolution. The broader movement known as local-first software leans heavily on CRDTs as well: applications like note-taking tools, whiteboards, and offline-capable mobile apps use CRDTs so that a user's device remains fully responsive and functional without any network connection at all, syncing seamlessly and correctly whenever connectivity returns, whether that is seconds or days later. In all these cases, the appeal is the same: predictable, mathematically guaranteed convergence without the latency, complexity, or single points of failure that centralized coordination requires.

Frequently asked questions

Try it live

Everything above runs in your browser — open CRDT: Conflict-Free Replicated Data Types and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.