Two people edit the same shopping list on their phones while the train goes through a tunnel. One adds milk. The other removes milk and adds eggs. When the signal returns, the app has to merge the lists. Someone's change might be lost, or the app might ask you to resolve a conflict.
That is the everyday face of eventual consistency: let every copy accept writes right away, and sort things out later. It scales beautifully and it stays available when networks fail. The catch is that merging by ad hoc rules is error-prone. This paper gives a clean answer: build data types that cannot conflict.
A conflict-free replicated data type (CRDT) is built so that any two copies can be merged automatically and every copy that has seen the same updates ends in the same state, in any order. Counters, sets and registers can all be designed this way.
Strong eventual consistency
Plain eventual consistency only promises that copies will agree eventually, if updates stop. It says nothing about how conflicts are settled, so every team invents its own rules.
The authors define strong eventual consistency: any two replicas that have received the same set of updates are in the same state, immediately, with no further coordination. If you can build a data type that guarantees this, replicas can accept writes without asking anyone, even during a network partition.
The paper gives two recipes, both with a precise mathematical condition.
- State-based. Replicas send their whole state to each other and combine it with a
mergefunction. For this to work, merge must be commutative (order does not matter), associative (grouping does not matter) and idempotent (merging the same state twice changes nothing). Together with states that only grow, these properties form a join semilattice. - Operation-based. Replicas send each small update (an operation) instead of the whole state. The operations must commute, and the network must deliver each one exactly once, in causal order.
Think of merge as "take the maximum." The maximum of 3 and 5 is the same as the maximum of 5 and 3, the same however you group, and taking it twice changes nothing. Design your data so that merging is a kind of maximum, and conflicts disappear.
The simplest example: a counter that cannot lose votes
Suppose three servers count likes. The naive plan is for each server to store one number and merge by taking the larger one. It fails. If two servers both start at 5 and each adds one, both now say 6. Merging by maximum gives 6, but the right answer is 7. One like was lost.
