Takeaway

CRDTs converge automatically under concurrent, out-of-order updates by designing operations that commute (or using causal metadata to resolve order).

The problem (before → after)

  • Before: Concurrent edits cause conflicts; coordination hurts availability.
  • After: Data types with merge semantics eliminate conflicts while ensuring eventual consistency.

Mental model first

Like keeping separate Lego bins and later pouring them together: the final collection is the union regardless of pour order if the operations are designed to commute.

Just-in-time concepts

  • State-based (CvRDT) vs op-based (CmRDT).
  • Join-semilattices and monotonic growth.
  • Causal context, tombstones, and unique IDs.

First-pass solution

Define a partial order and least upper bound; operations advance state monotonically; merges take LUBs to converge.

Iterative refinement

  1. Delta-state CRDTs reduce bandwidth.
  2. Compact tombstones and GC.
  3. CRDTs for sequences and JSON (RGA, LSEQ).

Principles, not prescriptions

  • Push complexity into data-type design to avoid coordination.
  • Preserve idempotence, commutativity, and associativity of merges.

Common pitfalls

  • Memory growth from tombstones.
  • Misinterpreting “eventual” as immediate convergence.

Connections and contrasts

  • See also: [/blog/cap-theorem], [/blog/raft-consensus].

Quick checks

  1. Why convergence? — Merges are associative, commutative, idempotent.
  2. Why causal metadata? — To make non-commuting ops safe.
  3. Why CRDTs? — High availability with predictable convergence.

Further reading

  • Shapiro et al., 2011 (source above)