CRDTs, Strong Eventual Consistency & Anti-Entropy

How diverged replicas come back together

When you go AP you accept that replicas diverge, and you need a story for how they come back together. The naive story is last-write-wins with a timestamp, which silently discards concurrent edits. CRDTs (Conflict-free Replicated Data Types) are the disciplined answer: data structures whose merge function is defined so that any two replicas that have seen the same set of updates are byte-for-byte identical, with no conflict resolution and no coordination. That property is Strong Eventual Consistency (SEC): eventual consistency plus a guarantee that convergence is deterministic.

The property that makes it work: the merge operation must be commutative, associative, and idempotent. Order does not matter, grouping does not matter, and applying the same update twice is harmless. Together these mean you can deliver updates in any order, duplicated, across an unreliable network, and every replica lands in the same state. Merge is often a mathematical join on a lattice (for a counter, element-wise max; for a set, union).

The workhorse types

• G-Counter / PN-Counter: a grow-only counter is a vector of per-replica counts; the value is the sum, merge is element-wise max. A PN-Counter is two G-Counters (increments and decrements).
• OR-Set (Observed-Remove Set): tags each add with a unique id so a concurrent add and remove resolve to "add wins" correctly. The set most people actually want.
• LWW-Register: a single value with a timestamp; simple, but it still loses concurrent writes by design.
• RGA / sequence CRDTs: ordered lists for collaborative text (the basis of Yjs and Automerge).

Costs are real and interviewers probe them. OR-Set elements carry add/remove tags, and removed elements leave tombstones so a late-arriving add does not resurrect deleted data. Metadata and tombstones grow, so you need garbage collection, which itself needs some coordination or a causal-stability threshold. And CRDTs cannot enforce global invariants: "this username is globally unique" or "the balance never goes negative" require agreement, and agreement is exactly what CRDTs avoid. For invariants you need consensus.

Anti-entropy: the part people forget

Convergence does not happen by magic. Replicas must actually exchange the updates they missed. Gossip: each node periodically pushes/pulls state with a few random peers, so updates spread epidemically in O(log n) rounds. Merkle trees: to compare a huge key range cheaply, each replica hashes its data into a tree; two replicas swap root hashes and only descend into subtrees whose hashes differ, finding the diverged ranges in log time. Dynamo and Cassandra use exactly this. Two more mechanisms fill gaps: read repair (a read that sees stale replicas writes the fresh value back) and hinted handoff (a down node's writes are held by a neighbor and replayed on return).

Interview nuance: the classic wrong turn is describing CRDTs and stopping. Without anti-entropy, a write that lands on replica A during a partition never reaches replica B, so they never converge. CRDTs give you a safe merge; gossip plus Merkle-tree reconciliation is what actually delivers the updates to merge.

Recap: CRDTs give Strong Eventual Consistency because their merges are commutative, associative, and idempotent, they cost metadata and tombstones and cannot enforce global invariants, and they only converge if paired with anti-entropy (gossip, Merkle trees, read repair, hinted handoff).