hard CRDTs: State-Based vs Operation-Based

Converging without coordination

Conflict-free Replicated Data Types (CRDTs) let replicas accept writes independently — even while partitioned — and still converge to the same value with no consensus round and no locking, because reconciliation is deliberately restricted to a merge operation that is commutative, associative, and idempotent: apply it in any order, any number of times, and the result is the same. That single restriction is the entire trick behind every CRDT; state-based and operation-based CRDTs differ only in what goes on the wire and what the transport underneath is required to guarantee.

State-based CRDTs (CvRDTs)

Mechanism: each replica holds its full local state and periodically gossips that entire state to other replicas (or a coordinator polls it). On receipt, a replica doesn't overwrite its state with the incoming one — it computes merge(local, received), a join that returns the least upper bound of the two states on a semilattice. Because that join is commutative, associative, and idempotent by construction, it doesn't matter which order messages arrive in, whether the same state arrives twice, or whether a message is lost and only shows up on a later retransmission — the eventual merged result is identical either way.

That tolerance is what makes state-based CRDTs attractive operationally: the transport underneath can be as weak as unreliable, at-least-once gossip. No causal ordering, no deduplication, no delivery guarantee beyond "it'll get there eventually, maybe more than once." The cost is bandwidth — sending the whole state on every round trip gets expensive as state grows, which is why production systems often ship delta-CRDTs (only the recent delta of the state, not the whole thing) as a bandwidth optimization on top of the same state-based model.

Operation-based CRDTs (CmRDTs)

Mechanism: instead of exchanging state, each replica broadcasts the operation it performed — e.g. increment(A) — and every other replica applies that operation directly to its own local state. Messages are small: an operation, not a whole document or counter vector.

But the safety argument moves from the merge function to the transport. Operations must be commutative (concurrent, causally-unrelated operations may arrive in different orders on different replicas and must still produce the same result) — that part mirrors the state-based case. The new requirement is delivery: an operation like increment is not idempotent on its own — applying it twice produces a different (wrong) result — so the broadcast layer underneath must guarantee exactly-once delivery in causal order: no operation is delivered twice, none is dropped, and causally-dependent operations (e.g. an "add" that must be seen before a later "remove" of the same item) arrive in the right order. Building that reliable causal-broadcast layer — typically deduplication by operation ID plus a causal-order buffer keyed on something like a vector clock — is real infrastructure, which is the price paid for the smaller wire messages.

Traced example — a G-Counter under both models

A G-Counter (grow-only counter) keeps one slot per replica; a replica only ever increments its own slot, and the total is the sum of all slots. Two replicas, A and B, each increment their own slot once, concurrently, starting from {A:0, B:0}:

Both models reach the same correct total, 2, under normal delivery — the difference only shows up under message duplication, which is exactly the failure state-based CRDTs are engineered to shrug off and op-based CRDTs must prevent one layer down, in the broadcast mechanism.

Pitfalls

• Treating an operation as safe to retry. "Just retry on timeout" is a reflex for RPCs, but for op-based CRDTs a naive retry after an ack is lost can double-apply a non-idempotent operation like increment — the exactly-once guarantee has to be real, not assumed.
• Assuming state-based CRDTs need no design work at all. The full-state gossip is only cheap for small state; without delta-CRDTs, a large document or set can make every gossip round expensive, and the convergence delay under partition can be long if gossip fan-out is sparse.
• Naive remove breaks commutativity. A plain "delete the value" in a set does not commute with a concurrent "add" of the same element — CRDT sets (OR-Set) solve this with unique add-tags and tombstones, not by wishing the operations were simpler.
• Expecting CRDTs to enforce global invariants. A per-replica merge rule can only ever look at the states/operations it has locally — it has no way to enforce a property that spans all replicas at once, like global uniqueness.

When CRDTs beat consensus (and when they don't)

• State-based (CvRDT) — choose when you want the simplest possible delivery contract: plain, unreliable, at-least-once gossip is enough because the merge absorbs duplicates, reordering, and resent messages for free. It costs message size — full state per round — unless you add delta-CRDTs on top.
• Op-based (CmRDT) — choose when message size matters more than transport simplicity: you send only the operation, not the state. It costs a reliable causal-broadcast layer underneath (dedup + causal delivery), which is genuine infrastructure to build and operate correctly.
• CRDTs beat consensus when you want the AP side of CAP — coordination-free writes during a partition, multi-master or offline-first systems (collaborative editors, shopping carts, distributed like/view counters) — where the answer to "what happens if two replicas write concurrently" is "merge them automatically," not "block one of them."
• CRDTs lose to consensus the moment the application needs a global invariant that no local merge rule can express: a username that must be unique across all replicas, an account balance that must never go negative, a lock that only one holder may have at a time. Those require agreement across replicas before the write is accepted — that's consensus (Raft/Paxos-style), the named alternative: consensus buys strict global correctness at the cost of availability during a partition; CRDTs buy availability at the cost of being unable to express that global constraint at all.

Takeaways

• Every CRDT converges via a merge/apply rule built to be commutative (state-based additionally requires associative + idempotent) — that restriction, not vector-clock magic, is the whole mechanism.
• State-based ships whole state and needs only unreliable gossip, because the idempotent join absorbs duplicates, reordering, and lost-then-resent messages; op-based ships small operations but needs exactly-once, causally-ordered delivery underneath.
• The G-Counter trace makes it concrete: merge-by-per-node-max tolerates a duplicate state message and still gives the right total; replaying a duplicate increment operation does not, and over-counts.
• CRDTs win for coordination-free, partition-tolerant (AP) systems; they cannot enforce global invariants like uniqueness or a non-negative balance — those still need consensus.

Sources: Shapiro, Preguiça, Baquero & Zawirski, “A comprehensive study of Convergent and Commutative Replicated Data Types,” INRIA research report RR-7506 (2011), for the CvRDT/CmRDT distinction and the join-semilattice merge requirement; Martin Kleppmann, “Designing Data-Intensive Applications,” ch. 5, on CRDTs vs. Operational Transformation. See also this guide's CRDT overview page (“CRDTs — Conflict-Free Replicated Data Types”) for the catalog of CRDT types (G-Counter, PN-Counter, OR-Set, sequence CRDTs). Re-authored for this guide; G-Counter and state-vs-op diagrams hand-authored as SVG.