CRDT: Conflict-free Replicated Data Types

Replicas can edit independently without asking each other, and any node that has seen the same set of changes converges to the same state. Instead of resolving conflicts after the fact, the data type is designed so that conflicts cannot arise.

Removing conflicts instead of resolving them

In distributed systems, replication is close to mandatory for availability and response time. But when several nodes modify the same data at once, a conflict appears. Something has to decide which change survives and which one is dropped.

The traditional answers came in two flavors. One is strong consistency, where every write goes through majority agreement. The other is Last-Write-Wins (LWW), where the timestamp decides which value stays. Both carry an obvious cost.

A Conflict-free Replicated Data Type (CRDT) takes a third route. Rather than resolving conflicts afterwards, it designs the data type so that a conflict cannot occur in the first place. Replicas modify their own copy with no consensus and no locking, and merging later still lands every replica on the same point.

The algebraic structure behind convergence

The heart of a CRDT is a merge function forced to obey three algebraic properties: commutativity, associativity and idempotency. Given all three, the final state is the same regardless of merge order and regardless of duplicate delivery of the same message.

Each property pairs with a specific network defect. Messages can arrive out of order, so commutativity and associativity remove order dependence. Messages can be duplicated by retransmission, so idempotency makes applying the same change twice safe.

A state space with these properties is what mathematics calls a join-semilattice. Merging two states yields their least upper bound (LUB), the smallest state that contains both. When merge is always defined as the LUB, replicas only ever move monotonically upward and eventually meet at one point.

The guarantee this buys is Strong Eventual Consistency (SEC). Two replicas that have received the same set of updates are immediately in the same state, with no further coordination. The 2011 INRIA report by Shapiro and colleagues (RR-7506) laid out these convergence conditions and their proofs.

The diagram shows two replicas incrementing a counter separately and then exchanging their states. Because merge is the per-slot maximum (the LUB), both replicas converge to the same state no matter which side sends first.

State-based and operation-based

There are two broad ways to synchronize a CRDT across replicas. The fork in the road is what gets put on the wire: the full state, or only the change operation.

The state-based form is called a Convergent Replicated Data Type (CvRDT). Replicas periodically exchange their entire state and merge whatever they receive. Because merge is the LUB, duplicated or reordered messages are harmless, but sending the whole state every time is expensive.

The operation-based form is a Commutative Replicated Data Type (CmRDT). A replica broadcasts only the operations that change its state. The payload is small, but the network has to guarantee causal delivery and concurrent operations must commute with each other.

The canonical state-based example is the G-Counter (Grow-only Counter), a counter that only increases. State is a vector with one slot per node, and each node increments only its own slot. Merge takes the maximum of each slot.

def increment(state, node):
    state[node] = state.get(node, 0) + 1
 
def value(state):
    return sum(state.values())
 
def merge(a, b):
    keys = set(a) | set(b)
    return {k: max(a.get(k, 0), b.get(k, 0)) for k in keys}

Running this code makes convergence visible. If replica A raises its slot to 3 and B raises its own to 1, merging in either order, or merging the same state twice, still gives {A: 3, B: 1} with a value of 4. Because max on each slot is the LUB, commutativity, associativity and idempotency all hold at once.

To support decrements as well, use a PN-Counter (Positive-Negative Counter). It holds one G-Counter for additions and another for subtractions, and reads the value as the difference of the two sums. Keeping decrements in their own counter makes subtraction converge independently of order.

Delta-state CRDTs

The weakness of the state-based form is that it ships the entire state every time. Transmitting a whole vector when a single counter slot changed is wasteful. A delta-state CRDT (δ-CRDT) sends only the delta, the smallest changed fragment, and cuts that cost.

It works in three steps. An operation that changes state also returns a delta containing only the changed part. That delta is buffered and sent to the peer node, and the receiver merges it with the same join used for ordinary merging.

def delta_increment(state, node):
    state[node] = state.get(node, 0) + 1
    return {node: state[node]}   # return only the changed slot as the delta
 
def join(state, delta):
    keys = set(state) | set(delta)
    return {k: max(state.get(k, 0), delta.get(k, 0)) for k in keys}

Deltas are combined with the same LUB merge, so duplicated or reordered deltas are still safe. If an acknowledgement never arrives, resending the delta is enough, and no separate reliability layer is required. Akka Distributed Data and IPFS both adopted the δ-CRDT approach.

The main CRDT types

Beyond counters there are sets, registers, sequences and more. They are distinguished by which operations they support and how they converge. The commonly used ones are as follows.

The tricky part in set types is deletion. A plain set difference goes wrong when one node removes an element while another node re-adds the same element. The Observed-Remove Set (OR-Set) solves this with dots.

A dot is a unique tag built from a node identifier and a monotonically increasing sequence number. An add attaches a fresh dot, and a remove deletes only the dots that node has actually observed. An element added concurrently with a removal carries a new dot and therefore survives. This rule, where a concurrent add beats a concurrent remove, is called add-wins.

Synchronization cost and limits

The price of a CRDT is memory and metadata. An OR-Set carries a dot for every element, and tombstones for deleted elements linger until garbage collection. On delete-heavy workloads the metadata can outgrow the data itself.

Transfer volume is a burden too. State-based replication exchanges whole states and consumes a lot of bandwidth, and δ-CRDTs only go so far in reducing it. Recent work, ConflictSync (arXiv:2505.01144, 2025-05), decomposes state into digests and reframes synchronization as a set reconciliation problem. It reports up to an 18x reduction in transmitted data compared with full state synchronization.

That saving is conditional, though. The same paper notes that once two replica states are more than 93% similar, the Bloom filter preprocessing costs more than it saves, so skipping it is better. The right choice depends on which similarity band you are in.

The most fundamental limit is semantic. A CRDT defines only 'how the merge happens', not 'whether that merge matches user intent'. When two people edit the same name at the same time, an LWW-Register quietly discards one of them: the state converged, but it may not be what the users wanted.

Where to use it and where not to

Real services use CRDTs where the semantics are simple. Riak ships OR-Set and PN-Counter as built-in database data types. The active-active configuration in Redis Enterprise handles multi-master replication with CRDTs. Automerge, a CRDT library used for real-time collaboration, synchronizes text with an RGA-family sequence type.

The places to avoid CRDTs are equally clear. Bank balances and inventory decrements carry an invariant of the form 'this value must never go below zero'. If two users buy the last remaining item at the same time, a PN-Counter will happily go negative, so those cases call for distributed locking or strong consistency such as Raft.

Collaborative editing splits as well. When preserving user intent is the priority, Operational Transformation (OT), which transforms the operations themselves, has the advantage. Google Docs uses OT for server-mediated real-time editing. A CRDT guarantees convergence through the data structure itself, which suits peer-to-peer or serverless settings. The cost is awkward insertion-order handling and higher memory use.

The deciding factor comes down to whether an invariant exists. If the business logic says 'this must not be added past a limit', use strong consistency; if the workload is pure aggregation or set membership, use a CRDT.

Summary

A CRDT does not resolve conflicts after the fact; it forces the merge function to be commutative, associative and idempotent so that conflicts cannot arise. That structure gives replicas strong eventual consistency, converging to the same state after independent edits with no coordination.

Synchronization splits into state-based, which ships the full state, operation-based, which ships only operations, and delta-based, which ships only the changed fragment. Each has different bandwidth and network requirements. The cost is metadata overhead such as tombstones and causal context, plus the semantic limit that convergence may not match user intent. The safe rule is to use CRDTs where semantics are simple, such as counters, sets and collaborative editing, and leave transactions with real invariants to strong consistency.