What is the structural difference between a state-based CRDT (CvRDT) and an operation-based CRDT (CmRDT), and what does each approach require from the network layer to guarantee convergence?

## State-based: the CvRDT **State-based CRDTs**, formally called **CvRDTs** (convergent replicated data types), represent a replica's data as a single value drawn from a mathematical structure called a **join-semilattice** — a set with a partial order and a "least upper bound" (join) operation for any two elements. 1. A write mutates the local state **monotonically** (moves it "up" the lattice, e.g. a G-Counter's slot only increases). 2. To synchronize, a replica periodically ships its **entire current state** to peers (directly, or via gossip/anti-entropy). 3. The receiving replica calls `merge(local, incoming)`, which computes the **join** of the two states. Because join in a semilattice is commutative, associative, and idempotent by definition, CvRDT convergence is automatic: any two replicas that have (directly or transitively) observed the same set of updates end up in the same state, regardless of the number of times, order, or duplication of the merge messages. ## Operation-based: the CmRDT **Operation-based CRDTs**, **CmRDTs** (commutative replicated data types), instead ship the delta — the operation itself — rather than the resulting state. Because there is no full-state reconciliation step to fall back on, the correctness burden moves from the merge function to the **delivery channel**: - Operations that don't commute unconditionally (e.g. an add and a remove of the same set element) must be delivered in **causal order** (applied only after everything they causally depend on has already been applied). - Every operation must be delivered **exactly once** — a dropped message means a permanently missing update, and a duplicated message means a corrupted counter. CmRDT designs typically split each operation into a **prepare** phase (executed once, at the origin) and an **effect** phase (executed at every replica when the operation is delivered), with effects specifically designed to commute pairwise; Shapiro et al.'s 2011 formalization of both CvRDT and CmRDT proved their equivalence in expressive power. ## The trade, in opposite directions The two designs trade bandwidth against delivery-reliability requirements in opposite directions — CvRDT's *ship the whole state* approach against CmRDT's *ship the delta* approach: | CvRDT | CmRDT | |---|---| | Any missed, reordered, or duplicated gossip message is **self-healing** — the next full-state exchange re-merges everything and nothing is permanently lost — a natural fit for unreliable, best-effort transports like gossip over UDP. | **Bandwidth-efficient**: only what actually changed is sent, which matters enormously for large, frequently-mutated structures like collaborative text. | | The cost is bandwidth and CPU: shipping the entire state every sync round is wasteful once the state is large, and the merge itself can be expensive. | But it demands a reliable **causal-broadcast layer** (a message queue with per-sender sequence numbers and causal buffering), which is real infrastructure to build and operate correctly. | ## How each one fails in production - **A common production failure with CmRDTs** is underestimating the delivery guarantee: teams wire operations through an ordinary at-least-once queue without deduplication or causal buffering, and either lose operations during a broker failover (permanent data loss, no full-state fallback) or double-apply retried operations. - **A common CvRDT failure** is treating periodic full-state gossip as cheap indefinitely — as the state grows (e.g. an OR-Set that has accumulated years of tombstones), each sync round's bandwidth and merge CPU grows with it, silently degrading until sync rounds fall behind real-time write rates, widening convergence lag. ## Where each one ships - **Riak's** built-in CRDT types are state-based (CvRDTs), gossiped between nodes with causal-context metadata attached, chosen because Riak's underlying transport (Dynamo-style read-repair and anti-entropy) already exchanges full replica states rather than a reliable operation log. - Collaborative editors built with **Yjs** use an operation-based-flavored design over a reliable WebSocket/relay connection specifically because shipping the entire document state on every keystroke would be far too expensive — each keystroke is instead a small, causally-tagged operation.