CRDTs guarantee convergence under stated operation and dissemination conditions, not automatic preservation of business rules or user intent.
What convergence means
A Conflict-free Replicated Data Type (CRDT) supports independent replica changes that can later be combined. Shapiro et al.'s SSS 2011 paper states conditions for Strong Eventual Consistency. The data type and dissemination rules jointly ensure that replicas receiving the same changes reach the same state.
Here, conflict-free does not mean that different users' intentions always agree. A data type can determine which concurrent value survives. Whether that result meets business requirements is a separate question.
State-based and operation-based replication
A state-based CRDT defines a partial order over states and uses their least upper bound, or join, for merging. Merge is commutative, associative, and idempotent. Local updates must also increase state monotonically in that order. Listing only the three merge properties omits a necessary update condition.
| Form | Payload | Required conditions |
|---|---|---|
| State-based | Full state | Monotonic updates, join merge, eventual dissemination |
| Operation-based | Operation effects | Commuting concurrent effects and the design's delivery conditions |
| Delta-state | Mergeable partial state | Delta dissemination and repair, with required causal conditions |
The basic operation-based construction assumes reliable causal delivery and prevention of duplicate application. State-based merging tolerates duplication and reordering, but cannot recover a change that is never delivered. Every form therefore has dissemination requirements.
A grow-only counter
A G-Counter has one slot per node, and each node increments only its own slot. Merge takes the per-slot maximum; queries sum the slots. The following example shows only this state rule.
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}If A has {A: 3, B: 0} and B has {A: 0, B: 1}, the merged state is {A: 3, B: 1}. Merging the same state again leaves the value at 4. This example does not implement identifier reuse after restart, durability, or network dissemination.
A PN-Counter records increments and decrements in separate G-Counters and also converges. It does not guarantee that their difference stays nonnegative. Inventory or balance limits need additional coordination, rights allocation, or another suitable design.
Delta dissemination and semantic limits
Almeida, Shoker, and Baquero's JPDC 2018 paper sends joinable delta-states instead of full state. A G-Counter delta can contain only the updated node's new cumulative value. This does not mean every data type produces a minimum-size change fragment.
A's slot: 3 → 4
Delta to send: {A: 4}
Receiver merge: maximum of its slot and 4Every update's effect must eventually reach other replicas through delta groups or full state. In a G-Counter, receiving {A: 4} includes the earlier increment even if {A: 3} was lost. This does not require delivery of every individual delta message.
The paper also supplies anti-entropy algorithms and conditions for causal consistency. A bandwidth claim detached from the dissemination algorithm omits those conditions.
An LWW register selects a concurrent value using a defined order. An add-wins OR-Set preserves concurrent additions that a removal did not observe. Both provide convergence rules, but preservation of user intent and safe metadata reclamation remain separate questions.
Summary
CRDT convergence requires the data type, local operations, and dissemination conditions to hold together. Idempotent state-based merging tolerates duplicate transmission but does not fix permanent loss of update effects. Delta-state reduces transmitted state, while business invariants and the suitability of merge semantics still need separate review.