Systems Dictionary • Distributed Systems • CRDT

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 Collaborative Canvas →

Figma implements fractional indexing and tree-structured CRDTs to synchronize multi-user vector manipulation across WebAssembly browser clients without server lock latency.

Obsidian Sync Engine →

Obsidian utilizes end-to-end encrypted delta-state CRDTs to reconcile markdown vault modifications between mobile devices and desktop computers working offline.

← Back to Dictionary Next: SIMD Vectorization →
Arkajit Das
Author • Verified Entity

Co-Founder & Chief Product Officer at Fraoula. Technology product executive leading enterprise AI, data platform architecture, and distributed systems.