Conflict-Free Replicated Data Type

Conflict-Free Replicated Data Type (CRDT) is a class of distributed data structures in computation and algorithms that can be replicated across multiple network nodes, updated independently and concurrently without synchronous coordination or distributed locks, and merged deterministically so that any two replicas that have received the same set of updates converge to an identical state. Formalized by Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski in 2011, CRDTs provide a mathematical solution to the availability-versus-consistency trade-off governed by the CAP theorem.

In computational complexity theory and geo-replicated database architecture, enforcing linearizable strong consistency via Paxos or the two-phase commit protocol requires round-trip quorum coordination on every write, rendering replicas unavailable for updates during network partitions. Classical eventual consistency allows disconnected nodes to accept local writes during a partition, but requires ad-hoc conflict resolution heuristics or human intervention when conflicting divergent updates are later reconciled. CRDTs bridge these regimes by ensuring Strong Eventual Consistency (SEC): by constraining either the state merge operator to form a mathematical join-semilattice or all state-mutating operations to commute, replicas accept local updates with zero network latency and converge deterministically without rollbacks as soon as anti-entropy gossip or causal broadcast delivers the updates.

Strong Eventual Consistency (SEC) vs. Classical Eventual Consistency

Let a replicated object be hosted across a set of processes P = {p₁, p₂, ..., p_n}, each maintaining a local replica state s_i ∈ S. Classical eventual consistency (Werner Vogels, 2009) is a liveness property stating only that if all new updates cease, all replicas will eventually reach the same state—potentially after rolling back tentative operations or running consensus arbitration.

Shapiro et al. (2011) defined Strong Eventual Consistency (SEC) by adding a safety invariant:

1. Eventual Delivery (Liveness): Every update executed at a non-faulty replica p_i is eventually delivered to all non-faulty replicas p_j.
2. Strong Convergence (Safety): Any two replicas p_i and p_j that have delivered the same unordered set of updates hold equivalent abstract states (s_i ≡ s_j), without executing any conflict-resolution negotiation or aborting any delivered update.
3. Termination: All local query, update, and merge methods terminate in finite time.

State-Based (CvRDT) vs. Operation-Based (CmRDT) Formulations

Shapiro et al. established two formally equivalent (mutually emulatable) algebraic models for constructing CRDTs:

1. State-Based Convergent Replicated Data Types (CvRDTs):

Each replica mutates its local state s_i ∈ S and periodically transmits its entire local state (or a compact delta-state, in δ-CRDTs introduced by Almeida, Shoker, & Baquero, 2018) to peer replicas over an arbitrary unreliable network channel. The state space (S, ≤, ⊔) is equipped with a partial order ≤ and a binary least-upper-bound join operator ⊔ : S × S → S forming a join-semilattice:

• Associativity: (x ⊔ y) ⊔ z = x ⊔ (y ⊔ z) (grouping of merges does not matter).
  • Commutativity: x ⊔ y = y ⊔ x (arrival order of peer states does not matter).
  • Idempotence: x ⊔ x = x (duplicate delivery of the same state is harmless).

Every local mutator u(s) is required to be inflationary (s ≤ u(s)). Because every update and every merge s_i ← s_i ⊔ s_j moves monotonically upward in the semilattice (S, ≤), any subset of updates merged in any order with any number of duplicates converges to their unique least upper bound ⊔_k s_k.

1. Operation-Based Commutative Replicated Data Types (CmRDTs):

Instead of transmitting full states, a replica executes a side-effect-free prepare phase t = prepare(u, s_i) locally and broadcasts a compact effect operation e(t) to all replicas over a reliable causal broadcast channel (often tracked via a vector clock). Because the delivery channel prevents duplicate messages and enforces Lamport's causal happens-before order (e₁ → e₂), the effect operator only needs to satisfy commutativity for concurrent operations (e₁ ∥ e₂):

Counters: G-Counter and PN-Counter

A naive replicated integer counter that broadcasts its scalar value fails under state merge because max(c₁, c₂) loses concurrent increments on the smaller replica, while c₁ + c₂ is not idempotent.

• Grow-Only Counter (G-Counter): Represents the state at n replicas as an n-element vector P[1 .. n] of non-negative integers (analogous to a vector clock), where only replica i is permitted to increment its own slot P[i] ← P[i] + v. The value of the counter is the sum ∑_k=1..n P[k], and the semilattice join of two state vectors P and Q is the coordinate-wise maximum:

• Positive-Negative Counter (PN-Counter): Supports both increments and decrements by combining two independent G-Counters P (increments) and N (decrements) on the product semilattice (P, N). An increment adds to P[i], a decrement adds to N[i], the merged state is (P₁ ⊔ P₂, N₁ ⊔ N₂), and the read value is ∑_k P[k] − ∑_k N[k].

Registers and Sets: LWW-Register, 2P-Set, LWW-Element-Set, and OR-Set

For sets where elements can be both added and removed, simple set union A ∪ B is a semilattice join that forbids removal, whereas set difference does not commute with union:

• Last-Write-Wins Register (LWW-Register): Associates a value v with a logical or hybrid Lamport timestamp t (breaking ties via replica ID); the join selects the pair (v, t) with the maximum timestamp.
• Two-Phase Set (2P-Set): Combines an add-only G-Set A and a tombstone remove-only G-Set R (A₁ ∪ A₂, R₁ ∪ R₂). An element x is present if x ∈ A \ R; once removed into R, x can never be re-added.
• Observed-Remove Set (OR-Set / Add-Wins Set): Allows arbitrary re-additions without per-element clocks. Each call to add(x) generates a globally unique tag u = (i, seq) and inserts the pair (x, u) into the active set E. A call to remove(x) at replica i removes only those pairs (x, u) currently observed in replica i's local state E (moving their tags u into a tombstone set T or causal context). If replica j concurrently calls add(x) with a fresh tag u′, u′ was not observed by replica i's remove, so (x, u′) survives the merge (add-wins semantics).

A major contemporary application of CRDTs is decentralized real-time collaborative editing of rich documents and source code—an alternative to Operational Transformation (OT) that requires no central transformation server. Sequence CRDTs such as the Replicated Growable Array (RGA) (Roh et al., 2011), YATA / Yjs (Nicolaescu et al., 2016), Automerge (Kleppmann & Beresford, 2017), and Fugue (Weidner, Gentle, & Kleppmann, 2023) assign every inserted character a globally unique immutable identifier (replicaid, lamportcounter) and anchor its position relative to its left and right neighbor identifiers at the time of insertion. When deleted characters are retained as lightweight tombstones and run-length compressed inside a B-tree or rope (data structure), multi-megabyte collaborative documents merge offline edits across thousands of peers in milliseconds alongside consistent hashing storage rings.

How do Delta-State CRDTs (δ-CRDTs) avoid sending the entire state over the network on every update?

In a classical state-based CvRDT, merging requires transmitting the full state s_i (which grows as O(N) with collection size). Delta-State CRDTs (δ-CRDTs) (Almeida, Shoker, & Baquero, 2018) define delta-mutators m^δ(s) that return a tiny state fragment δ ∈ S representing only the incremental change (u(s) = s ⊔ m^δ(s)). Sending and merging only these small δ-intervals achieves the low bandwidth of operation-based CmRDTs while retaining the idempotence and non-causal network tolerance of state-based CvRDTs.

What is the difference between a CRDT and Operational Transformation (OT)?

Operational Transformation (used in early Google Docs) mutates positional index numbers (insert(pos=5, 'a')) as concurrent operations cross each other, which requires either a central serialization server or fragile transformation functions that often fail the TP2 convergence puzzle on 3+ peers. Sequence CRDTs replace mutable integer indices with immutable causal identifiers forming a monotonic tree or directed acyclic graph, achieving mathematical convergence across any peer-to-peer network topology without a central server.

1. Shapiro, M., Preguiça, N., Baquero, C., & Zawirski, M. (2011). "Conflict-free replicated data types." Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2011), LNCS Vol. 6976, 386–400. https://doi.org/10.1007/978-3-642-24550-3_29
2. Roh, H.-G., Jeon, M., Kim, J.-S., & Lee, J. (2011). "Replicated abstract data types: Building blocks for collaborative applications." Journal of Parallel and Distributed Computing, 71(3), 354–368. https://doi.org/10.1016/j.jpdc.2010.12.006
3. Kleppmann, M., & Beresford, A. R. (2017). "A conflict-free replicated JSON datatype." IEEE Transactions on Parallel and Distributed Systems, 28(10), 2733–2746. https://doi.org/10.1109/TPDS.2017.2697382
4. Almeida, P. S., Shoker, A., & Baquero, C. (2018). "Delta state replicated data types." Journal of Parallel and Distributed Computing, 111, 162–173. https://doi.org/10.1016/j.jpdc.2017.08.003
5. Weidner, M., Gentle, J., & Kleppmann, M. (2023). "The art of the fugue: Minimizing interleaving in collaborative text editing." arXiv Preprint, arXiv:2305.00583. https://doi.org/10.48550/arXiv.2305.00583