How do CRDTs merge changes without conflicts?

Two copies of the same data, called replicas, are edited while they cannot reach each other. The edits are concurrent: each was made without knowledge of the other. When the replicas meet again, something has to decide what the combined data looks like.

Some replicated systems apply an update, discover later that it clashes with another, and roll it back. A CRDT avoids that step. Shapiro, Preguiça, Baquero and Zawirski define the goal as strong eventual consistency: any two replicas that have received the same set of updates are in the same state, with no rollback and no vote.

“Conflict-free” does not mean two people never edit the same thing. It means the data type has already decided what the merged result will be, so no conflict is left for anyone to resolve. There are two ways to build that guarantee.

In a state-based CRDT, each replica changes its own state and from time to time sends that state to another replica. The receiver combines the incoming state with its own using a merge function.

The paper gives the conditions that make this converge. The possible states must be ordered so that any two of them have a least upper bound, the smallest state that contains both. The merge must compute that least upper bound, and every local update must move the state upward, never back. A merge built this way is automatically:

• Commutative: merging A with B gives the same result as merging B with A.
• Associative: merging A with B and then with C gives the same result as merging A with the result of B and C.
• Idempotent: merging A with itself gives A.

A grow-only counter shows how this works in practice. Each replica keeps a count for every replica and only increments its own entry. Merging takes the larger value for each entry, and the counter’s value is the sum. If phone A has counted three items and phone B two, any merge of their states reads five, however many times the states are exchanged. Adding the entries together on merge would be wrong, because receiving the same state twice would count it twice. The older name for this family is convergent replicated data type (CvRDT).

In an operation-based CRDT, each change is turned into an operation, such as “increment” or “insert this character after that one”, and the operation is sent to every replica. The rule here is that any two concurrent operations must commute: applying them in either order leaves the replica in the same state. Addition commutes, so an operation-based counter just adds each increment it receives.

This style moves less data but asks more of the network. The papers assume reliable causal delivery: every operation reaches every replica exactly once, and an operation is never applied before the operations it depended on. The CRDT glossary puts the practical side plainly: the system must resend operations that are lost and ignore duplicates. The older name is commutative replicated data type (CmRDT).

The comprehensive study weighs the two. State-based CRDTs are simpler to reason about and work over weak channels, but sending whole states can be expensive for large objects. Operation-based CRDTs have simpler payloads but need reliable broadcast, which in general means tracking who is in the group. Delta CRDTs sit between them: they are state-based, but replicas send only the part of the state that changed. The 2011 paper also proves that each style can emulate the other.

The three properties map onto what goes wrong on unreliable links. Kleppmann and Beresford design their JSON CRDT for a network that “may arbitrarily delay, reorder and duplicate messages”.

• Because merges commute, it does not matter which device’s changes arrive first.
• Because they are associative, a device can merge changes it collected from several others and pass the combined state on, and the result is the same as merging each one separately.
• Because they are idempotent, a change that arrives twice through two routes does no harm.

Yjs states the same thing about its own document updates: they are commutative, associative and idempotent, so they can be applied in any order and more than once. This is why CRDTs pair well with store-and-forward delivery and peer-to-peer links. Shapiro and colleagues note that any group of replicas that can talk to each other converges, even while cut off from the rest, and no consensus protocol is needed.

Convergence means every device agrees, not that everyone gets what they intended. The data type picks the outcome in advance:

• A set has to choose whether a concurrent add or remove of the same item wins. The comprehensive study shows that a replicated set cannot behave exactly like a sequential one, so every CRDT set is an approximation with a stated rule.
• A last-writer-wins register keeps one of two concurrent values and drops the other.
• Two people can each book the last seat, and both bookings merge cleanly into a state that breaks the rule. Shapiro’s paper defines a conflict as concurrent updates that are each correct but together violate an invariant, and a merge alone cannot prevent that.

Metadata has a cost too. In some CRDTs a deleted item leaves a tombstone so that a late concurrent edit still has something to refer to, and the comprehensive study reports that CRDTs tend to become inefficient as tombstones accumulate. For choosing between merging, keeping both versions and asking an authority, see how sync conflicts are resolved. The kinds of CRDT article covers which rule each common type uses.