Conflict-free Replicated Data Types (CRDT)
A family of data structures that can be replicated concurrently across multiple network nodes and merged deterministically without centralized coordination locks.
Mathematical Foundation
In classical distributed systems, achieving strong consistency requires consensus rounds (such as Paxos or Raft) or centralized locking. CRDTs eliminate synchronization overhead by requiring merge operations to form a join-semilattice mathematically defined by three algebraic properties:
- Commutative: A ⊔ B = B ⊔ A (The order in which node updates are received does not alter the resulting state).
- Associative: (A ⊔ B) ⊔ C = A ⊔ (B ⊔ C) (Network packet batching order does not affect state).
- Idempotent: A ⊔ A = A (Duplicate network packets delivered over unreliable channels have zero harmful side effects).
State-Based (CvRDT) vs Operation-Based (CmRDT)
| Dimension | State-Based (CvRDT) | Operation-Based (CmRDT) |
|---|---|---|
| Payload Transmitted | Full object state or state delta | Discrete mutation operations |
| Network Requirements | Unordered, best-effort packet delivery | Causal order delivery (e.g. via TCP/vector clocks) |
| Bandwidth Usage | Higher (grows with state size unless delta-CRDT) | Minimal (only incremental mutation commands) |
| Merge Complexity | Higher computation at receiver | Simple execution of commutative operation |
Real-World Software Implementations
Figma implements fractional indexing and tree-structured CRDTs to synchronize multi-user vector manipulation across WebAssembly browser clients without server lock latency.
Obsidian utilizes end-to-end encrypted delta-state CRDTs to reconcile markdown vault modifications between mobile devices and desktop computers working offline.