Skip to content

CRDT-Like State Merge

Data model — instantiates Shared-State Consistency Contract Design

Represents shared state as data types whose concurrent updates merge deterministically, so replicas accept writes independently and always converge to the same value.

CRDT-Like State Merge represents the shared state as conflict-free replicated data types — structures whose update operations are commutative, associative, and idempotent, so any two replicas that have absorbed the same set of updates hold the same value no matter what order or how many times those updates arrived. Its defining move is to make conflict impossible by construction rather than detected and arbitrated: the merge of two divergent replicas is a mathematical join (a least upper bound), so there is never a moment where the system must ask "which write wins?" Every write is accepted locally and immediately; a common value is recovered later, for free, when replicas exchange state and merge.

Example

Two roommates share a grocery list in an offline-capable app. Both are underground on the subway with no signal: one adds "oat milk," the other removes "eggs" and adds "coffee." With a naive latest-value store, whoever syncs second could clobber the other's edits. Modeled as an OR-Set CRDT, each device tags every add and remove with a unique id and applies edits locally with no wait. When the phones reconnect, the two replicas exchange their sets and merge by union-with-tombstones: both "oat milk" and "coffee" survive, "eggs" stays removed, and — crucially — the result is byte-identical on both phones regardless of which synced first. Nobody's edit was lost and nobody had to be online at the same time. The design work was choosing an add-wins OR-Set rather than a plain set, because the household's intent is "don't silently drop an item someone added."

How it works

The state is modeled as a join-semilattice — a value space where any two states have a well-defined merge that is insensitive to order, duplication, and grouping. Each replica applies local operations without coordination and, on contact with a peer, merges the two states (state-based CRDTs ship the whole value; operation-based ones ship operations and require causal delivery). Because the merge is a least upper bound, replicas that have seen the same updates are identical, and the system reaches strong eventual consistency[1] once all updates propagate. The real engineering is picking, per field, the CRDT whose built-in merge encodes the intended rule — a counter, an add-/remove-wins set, a register, or an ordered sequence.

Tuning parameters

  • CRDT type per field — counter, set, register, or sequence; choose the one whose automatic merge matches the business rule. The wrong type still converges, but to a value the domain never intended.
  • State- vs. operation-based — ship whole state (simple, idempotent, bandwidth-heavy) or ship operations (compact, but needs causal, effectively-once delivery).
  • Add-wins vs. remove-wins — which side a concurrent add/remove race resolves toward; sets the bias when the two genuinely race.
  • Tombstone retention — how long deletion markers live. Longer keeps concurrent deletes correct; shorter caps the metadata that would otherwise grow without bound.
  • Merge granularity — per-field vs. per-object versioning; finer merges reduce false conflicts at the cost of more metadata.

When it helps, and when it misleads

Its strength is coordination-free, always-available local writes with guaranteed convergence — the natural fit for offline-first apps and geo-replication where waiting for a quorum is unacceptable. But convergence is not correctness: the merge only guarantees replicas agree, not that they agree on what a human wanted — an add-wins set can resurrect a deleted item, and no CRDT can enforce an invariant that spans objects or needs a global view ("balance ≥ 0," "this seat booked exactly once"). The classic misuse is reaching for a CRDT precisely to dodge coordination on state that has a real cross-object invariant, then shipping a legal-but-wrong outcome; metadata (tombstones, version tags) can also bloat silently. The discipline is to use CRDTs only where the invariant is expressible as a monotone merge, and route genuinely global invariants to a coordinating sibling.

How it implements the components

  • merge_policy — the commutative/associative/idempotent join is the merge policy; convergence is a theorem about its algebra rather than a runtime negotiation.
  • recovery_and_reconciliation_path — divergence created by independent writes is reconciled automatically the moment replicas merge, so recovery after a partition needs no special repair logic.

It does not move the bytes between replicas — that propagation/repair loop is Anti-Entropy Synchronization's; the newest-timestamp-wins special case and the version token it compares belong to Last-Write-Wins Register; cross-object causal ordering is Causal-Consistency Protocol's.

Notes

The Last-Write-Wins Register is itself the simplest CRDT. The line between the two mechanisms is what the merge does with concurrent information: general CRDTs here keep it (union a set, sum a counter), while an LWW register discards all but one value. Choosing between them is really choosing whether concurrent writes to this state are additive or single-valued.

References

[1] Strong eventual consistency — replicas that have delivered the same set of updates are in the same state, with convergence guaranteed by the data type's merge rather than by agreement on an order. This is the property CRDTs (formalized by Shapiro and colleagues) are designed to provide, and it is strictly weaker than the total order a linearizable design requires. ↩