In high-availability distributed systems, partition tolerance requires replicas to accept writes locally without waiting for synchronous consensus. When partitions heal, reconciling conflicting mutations traditionally required complex manual merge resolution or data-destroying “last-write-wins” heuristics. In 2011, Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski revolutionized distributed state reconciliation by introducing Conflict-Free Replicated Data Types (CRDTs). By grounding data types in rigorous abstract algebra—specifically bounded join-semilattices and commutative causal broadcast—CRDTs mathematically guarantee Strong Eventual Consistency (SEC): any two replicas that have received the same set of updates are guaranteed to be in identical states, completely independent of message arrival order.
1. Strong Eventual Consistency (SEC) & Semilattice Foundations
Traditional eventual consistency guarantees convergence only after an indefinite quiescent period without updates. Strong Eventual Consistency (SEC) provides a much stronger formal guarantee:
$$orall i, j: quad mathcal{U}_i = mathcal{U}_j implies mathcal{S}_i equiv mathcal{S}_j$$
Whenever two replicas $i$ and $j$ have received the same set of updates $mathcal{U}$, their internal states $mathcal{S}_i$ and $mathcal{S}_j$ are identical, requiring no consensus rounds, no distributed locks, and zero human intervention.
State-Based CRDTs (CvRDT) & Join-Semilattices
A State-based CRDT (CvRDT) synchronizes by transmitting its entire local state (or delta state) to peers, who merge it using a merge operator $sqcup$. Formally, the state space forms a Join-Semilattice $langle mathcal{S}, sqcup, le
angle$ endowed with a partial order $le$:
- Commutativity: Order of message receipt does not affect state:
$$x sqcup y = y sqcup x$$ - Associativity: Message batching and grouping do not affect state:
$$(x sqcup y) sqcup z = x sqcup (y sqcup z)$$ - Idempotence: Duplicate network deliveries have zero side-effects:
$$x sqcup x = x$$ - Monotonic Growth: Local mutations always advance state monotonically along the partial order:
$$s le s sqcup ext{mutate}(s)$$
Because the merge operator computes the mathematical Least Upper Bound (LUB) on the semilattice, convergence is deterministic and globally guaranteed.
2. Operation-Based CRDTs (CmRDT)
While CvRDTs transmit full states, Operation-based CRDTs (CmRDT) broadcast operations. An operation $o$ is decomposed into a side-effect-free local preparation phase followed by a downstream execution phase at all replicas. As long as concurrent operations commute:
$$o_1 parallel o_2 implies o_1 circ o_2 equiv o_2 circ o_1$$
and the underlying network transport guarantees causal delivery (e.g. via vector clocks), replicas converge without state merging.
3. Concrete CRDT Primitive Structures
Grow-Only Counter (G-Counter)
For a cluster of $n$ nodes, state is a vector $ec{V} in mathbb{N}^n$. Node $i$ increments only its own component $ec{V}[i] leftarrow ec{V}[i] + 1$. The merge operator takes the component-wise maximum:
$$ec{V}_A sqcup ec{V}_B = left[ max(ec{V}_A[1], ec{V}_B[1]), dots, max(ec{V}_A[n], ec{V}_B[n])
ight]$$
The total count is given by the sum of all components: $ ext{Value} = sum_{k=1}^n ec{V}[k]$. A PN-Counter (Positive-Negative) combines two G-Counters: one tracking increments $ec{P}$ and one tracking decrements $ec{N}$, yielding value $sum ec{P} – sum ec{N}$.
Observed-Removed Set (OR-Set)
In set data structures, the challenge is handling concurrent additions and deletions of the same element. The OR-Set resolves this cleanly: each addition of element $e$ is tagged with a globally unique timestamp or UUID $u in mathcal{T}$.
- $ ext{Add}(e)$: generates unique tag $u$, adding pair $(e, u)$ to the addition set $mathcal{A}$.
- $ ext{Remove}(e)$: finds all tags currently associated with $e$ in the local addition set and adds them to the tombstone tomb set $mathcal{R}$.
- $ ext{Lookup}(e)$: returns true if there exists a tag $u$ such that $(e, u) in mathcal{A} land u
otin mathcal{R}$.
If an add and a delete occur concurrently, the new add generates a fresh tag not yet present in the tomb set, ensuring add-wins semantics without lost updates.
4. Sequence CRDTs & Collaborative Text Editing
Building real-time collaborative editors (such as Google Docs, Figma, and Notion) without central servers requires Sequence CRDTs. In a document, text is an ordered sequence of characters. Naive array index positioning fails because concurrent insertions shift subsequent character indices.
Sequence CRDTs (such as RGA, Logoot, LSEQ, and industrial engines Yjs and Automerge) assign each character a fractional, immutable, globally unique coordinate in a dense identifier space $mathcal{I}$:
$$ ext{id}_A < ext{id}_{ ext{new}} < ext{id}_B$$
Because character identifiers never change once generated, concurrent insertions between adjacent positions simply generate fractional positions, sorting deterministically across all peers without index drift.
