CRDTs & Conflict-Free Replication

Why CRDTs exist

Last-write-wins and ad-hoc merges lose updates under concurrent writes. CRDTs (Conflict-free Replicated Data Types) guarantee that replicas converge to the same state without coordination, as long as all operations eventually reach every replica.

Two families:

Family	Idea	Examples
State-based (CvRDT)	Merge full states with a commutative, associative, idempotent function	G-counter, OR-set, LWW-register
Operation-based (CmRDT)	Broadcast operations; apply in any order if ops commute	RGA text, op-based counters

The math requirement (interview level)

A state-based CRDT needs merge ∪ such that:

• Commutative — merge(A,B) = merge(B,A)
• Associative — merge(merge(A,B),C) = merge(A,merge(B,C))
• Idempotent — merge(A,A) = A

Then replicas converge regardless of delivery order.

Common types to name

• G-counter / PN-counter — increment-only or increment/decrement counters
• OR-set — add wins over remove (observed-remove set)
• LWW-register — timestamped last-write-wins per register (not global wall clock chaos)
• RGA / Yjs-style sequences — collaborative text with unique op IDs

CRDT vs coordination

Approach	Pros	Cons
CRDT	High availability, partition tolerant merges	Metadata overhead, limited data models, tombstone GC
Strong consensus (Raft)	Simple mental model for linearizable state	Unavailable under partition if minority

Use CRDTs when availability + merge correctness beats single global order — collaborative editors, presence, counters, shopping carts with commutative adds.

Link to Topic 5

Version vectors detect concurrent writes; CRDTs define how to merge them without a central resolver.

Link to Databases track

Document DBs often use LWW at the field level (Dynamo-style). CRDTs are the principled alternative when LWW loses data you care about.

Interview answer template

"We'd use an OR-set for the wishlist so concurrent add/remove from two devices converges. For account balance we'd not use a CRDT — that needs linearizable transactions."