Day 6: CRDTs — Conflict-Free Replicated Data Types

Phase 1 · May 25, 2026

Agenda (2–3 hours)

• Read (45 min): Shapiro et al. "A Comprehensive Study of CRDTs" (2011) §1–3; Marc Shapiro's CRDT primer blog post
• Study (45 min): Work through G-Counter, PN-Counter, LWW-Register, OR-Set by hand
• Practice (45 min): Implement G-Counter and OR-Set in Rust
• Challenge (30 min): Design a CRDT-based shopping cart — what merge semantics make sense when two devices have different items?

The Coordination Problem

Strong consistency requires coordination — locks, quorums, consensus rounds.
Coordination means latency and unavailability.

What if the data type itself defined a safe merge operation?

CRDTs guarantee eventual consistency without coordination by ensuring all concurrent updates can be merged deterministically.

CvRDT vs CmRDT

State-based (CvRDT):

• Replicas periodically exchange full state
• Merge function must be commutative, associative, idempotent
• Merge = join in a semilattice (least upper bound)
• Simpler to reason about; potentially large state to ship

Operation-based (CmRDT):

• Replicas exchange operations (deltas)
• Operations must be commutative (concurrent ops can arrive in any order)
• Requires exactly-once delivery; smaller messages

Most systems use op-based or delta-state CRDTs.

Common CRDTs

G-Counter (grow-only): vector of per-node counters; value = sum

merge(a, b) = [max(a[i], b[i]) for each i]

PN-Counter: pair of G-Counters (P increments, N decrements); value = P - N

LWW-Register (last-write-wins): each write carries a timestamp; merge picks the higher timestamp — simple but lossy

OR-Set (observed-remove set): add operations tag elements with unique IDs; remove only removes IDs observed at removal time — concurrent add wins

RGA (replicated growable array): CRDT sequence for collaborative text editing (used by ShareDB, Automerge)

Where CRDTs Are Used

Key Takeaways

• CRDTs trade richer semantics for the ability to merge concurrent updates without coordination
• The merge function must form a semilattice (commutative, associative, idempotent)
• G-Counter, PN-Counter: counters without coordination
• OR-Set: sets where concurrent add-and-remove is resolved in favor of add
• CRDTs shine for collaborative apps and geo-distributed replicas

Tomorrow: Challenge — implement a G-Counter CRDT in Rust with network simulation.