The question this answers
Can I make merge automatic and provably convergent — and what does that not give me?
A CRDT guarantees strong eventual convergence: any two replicas that have received the same set of updates hold the same state, regardless of the order or multiplicity of delivery, with no coordination whatsoever. That is the entire guarantee. It says nothing about the converged value being correct for your domain, and it cannot enforce any constraint involving state the type does not hold.
Everything below is bought to hold this sentence. "Strongly consistent" with no scope attached is a slogan, not a guarantee — read what it actually covers, and what it explicitly does not.
A replica knows its own state and any state or operations it has received, and knows that merging is safe to perform at any time in any order. It does not know whether it has received everything — there is no "final" state, only the state given what has arrived so far. Any decision that requires knowing no further update is coming (such as enforcing a limit) is outside what the replica can support.
A node knows its own state and the messages that arrived. Everything else is inference from evidence that was already stale. "B has not replied in five seconds" is knowledge; "B is down" is a decision — and usually the bug.
The idea: make merge a join
The previous lesson established that a merge converges exactly when it is commutative, associative and idempotent. A CRDT takes that observation and builds it into the type: the state space is arranged as a partially ordered set where every pair of states has a least upper bound, and merge *is* that least upper bound. Convergence then follows as a theorem rather than as a property you have to test for.
Two families implement this. State-based (CvRDT): replicas ship their whole state, and merge is the join — robust to lost, duplicated and reordered messages, at the cost of sending more data. Operation-based (CmRDT): replicas ship operations that are designed to commute — cheaper on the wire, but it requires the delivery layer to deliver each operation exactly once (and often in causal order), which pushes the hard part into the transport. Most production systems are hybrids: ship operations for efficiency, keep a state-based merge for repair and catch-up.
The practical consequence is worth being clear about: the write path has no conflict resolution step at all. Every replica accepts every write immediately, merge happens whenever convenient, and the result is the same everywhere. That is a genuinely strong property, and it is why CRDTs power offline-capable apps and collaborative editors.
- G-Counter (grow-only counter) — a map from replica id to that replica's count. Merge takes the element-wise max; the value is the sum. Increments never conflict, and redelivery is harmless because
maxis idempotent. - PN-Counter — two G-Counters, one for increments and one for decrements; the value is the difference. Supports decrement, and still cannot enforce "never below zero".
- G-Set (grow-only set) — merge is union. Trivially a join. Cannot remove.
- 2P-Set — an add-set and a remove-set; once removed, an element can never be re-added. Simple, and the restriction is usually unacceptable.
- OR-Set (observed-remove set) — each add carries a unique tag; a remove deletes only the tags it *observed*. A concurrent add therefore survives a remove, which is almost always the behaviour users expect.
- LWW-Register — last-write-wins, made honest: it is a CRDT (max on a total order) and it converges, and it still discards the losing write (Last Write Wins Is Data Loss You Chose by Default).
- Sequence CRDTs (RGA, Logoot, Yjs/Automerge-style) — position identifiers that allow concurrent insertion without renumbering. This is what makes collaborative text editing work.
Why OR-Set is the one worth understanding
The set types are a good lesson in how much design goes into "obvious" behaviour, because the naive version has a bug everybody hits.
Take a G-Set: merge is union, which is a perfect join. Now add removal. If you represent the state as a plain set and merge by union, a removal is undone by the next merge with a replica that still has the element — the element comes back. If you keep a separate remove-set (2P-Set), you fix that and acquire a new problem: an element removed once can never be added again, because the remove-set always wins.
The OR-Set solves it by making adds distinguishable. Each add generates a unique tag, so "add x" twice produces two tags. A remove records exactly which tags it saw and deletes those. An element is present if it has at least one tag that has not been removed. Now: a remove concurrent with an add removes only the older tag, the new add survives, and the element remains — add wins over concurrent remove, which is what a user who just added something to their cart expects.
The point generalises. The convergence is free once the type is a join, but the *semantics* under concurrency are a design choice with no default. Add-wins and remove-wins are both perfectly convergent and they behave differently, and choosing between them requires knowing what your users expect. That choice is not made for you by "using a CRDT".
What CRDTs cannot do — stated plainly
This section matters more than the previous two, because CRDTs are routinely oversold and the gap between "converges" and "correct" is where systems get hurt.
They cannot enforce a global invariant. This is the fundamental limit and it is not an implementation gap. A PN-Counter cannot guarantee "balance never goes negative", because each replica must accept a decrement without consulting the others — that is what makes it coordination-free — and two replicas each accepting an affordable withdrawal produce an unaffordable total. Enforcing the invariant requires knowing what the other replicas are doing before you act, which is coordination, which is the thing CRDTs exist to avoid. You cannot have both (Start From the Invariant, Not From the Architecture, Coordination Avoidance: Restructuring the Problem Instead of Paying for It for how to bound the damage).
They make merge deterministic, not correct. Both add-wins and remove-wins converge. Both are CRDTs. They give different answers, and only your domain says which is right. "We use a CRDT" answers the convergence question and leaves the semantics question completely open — and the semantics question is the one users notice.
Automatic merge can produce output no human wrote. A text CRDT will happily interleave two concurrent edits into a sentence neither author intended and both consider wrong. Convergence is preserved; meaning is not. For prose, "show both and ask" often beats any automatic merge (Only the Application Knows What the Merge Means).
Metadata is not free. Tombstones for removed elements, tags for every add, position identifiers that grow with editing history — these persist after the data they describe is gone, and garbage-collecting them safely requires knowing every replica has seen the removal, which is a coordination problem sneaking back in. Long-lived CRDT documents growing far beyond their content is a normal, well-documented operational issue, not a sign of a bad implementation.
Not everything has a natural CRDT. Types with strong internal constraints — a balanced tree, a schema-validated record, an ordered list with a uniqueness rule — often have no join that preserves the constraint. Forcing one usually means weakening the constraint until the join exists, which is the same trade in different clothing.
| Does a CRDT give you this? | Detail | |
|---|---|---|
| All replicas converge to the same stateprotocol | Yes, provably | Strong eventual consistency, no coordination needed |
| Safe under reorder, duplication, retryprotocol | Yes | Join is commutative, associative, idempotent |
| Available during a partitionprotocol | Yes | Every replica accepts every write immediately |
| The converged value is what users wantedassumption | No | Add-wins and remove-wins both converge; only you know which is right |
| Enforces "balance ≥ 0" or "seat booked once"protocol | No — impossible without coordination | Requires knowing peers' state before acting |
| Bounded metadatatypical | No | Tombstones and tags persist; safe GC needs agreement |
| Sensible merge of proseassumption | No | Converges to text neither author wrote |
Where they genuinely earn their place
With the limits stated, the wins are real and specific. CRDTs are the right tool when the data is naturally a set, a counter, a map of independent fields, or a sequence; when writes must be accepted offline or during partition; and when no invariant spans replicas.
Concretely: shopping carts (union of adds, observed removes), user preferences and settings (per-field registers), presence and status, tag and label sets, view and reaction counters, collaborative documents and whiteboards, offline-first mobile applications, and the internal state of geo-replicated caches and session stores.
And a design pattern worth borrowing even when you do not adopt a CRDT library: reformulate the operation until it commutes. "Set the total to 7" does not commute; "add 1" does. "Set the tag list" does not commute; "add this tag" does. Recording intent rather than resulting state converts a large fraction of conflicts into non-conflicts, and that reformulation is available in ordinary code with no library at all (What "Eventually Converges" Actually Requires).
The honest summary: CRDTs move the hard problem from the write path to the data model. If your data model fits, you get availability and convergence for free. If it does not — because an invariant spans replicas — no CRDT will supply what only coordination can, and recognising that quickly is worth more than any library.
Key points
- A CRDT arranges its state space so that merge is a least upper bound, making convergence a theorem rather than a test.
- State-based ships whole states and tolerates loss, duplication and reordering; operation-based ships commuting operations and needs exactly-once delivery.
- OR-Set shows that convergence is free but *semantics* are a choice: add-wins and remove-wins both converge and behave differently.
- CRDTs cannot enforce a global invariant — "balance ≥ 0" requires knowing peers' state, which is coordination.
- They make merge deterministic, not correct. The converged value may be one no user wanted.
- Metadata (tombstones, tags, position ids) persists, and collecting it safely reintroduces a coordination requirement.
- The transferable trick is reformulating operations so they commute — available without adopting any library.
The chain, answered
Every field here is required, which is why no lesson in this domain can recommend a design without naming what an operator sees when it fails, what survives the partition, what repairs it afterwards, and the simpler thing to consider first.
- • The type's states form a partially ordered set in which every pair has a least upper bound.
- • Merge is defined as that least upper bound, making it commutative, associative and idempotent by construction.
- • Each replica applies local updates immediately, without consulting any peer.
- • States or operations propagate by any means — gossip, anti-entropy, direct replication — with no ordering requirement for state-based types.
- • Any replica may merge any received state at any time; replicas that have seen the same updates hold identical state.
- • An operation-based CRDT is deployed over a transport that delivers duplicates, and non-idempotent operations corrupt the state.
- • Tombstones are garbage-collected before every replica has observed the removal, and removed elements reappear.
- • Metadata growth outpaces the data, and objects exceed size limits or become expensive to transfer.
- • A custom type is written that is not actually a join — usually failing associativity — and replicas diverge despite the CRDT label.
- • The chosen semantics (add-wins vs remove-wins) do not match user expectation, so the system converges reliably on the wrong answer.
- • An invariant is assumed to be enforced by the type, and is not — the most consequential failure in this list.
- • Deleted items reappear: a user removes something, it goes away, and it is back after a sync. The operator finds tombstone GC running ahead of a lagging replica, with every operation reporting success.
- • Document size grows without bound: a collaborative document reaches tens of megabytes of metadata for a few pages of text, and load times degrade steadily. The operator sees payload size, not request rate, as the growth driver.
- • Balance goes negative: concurrent withdrawals on two replicas each pass a local check. The operator sees an account below zero with no failed transaction anywhere, and no bug in either replica.
- • Interleaved text nobody wrote: two authors edit the same paragraph offline and the merged result is grammatically mangled. Both authors report the system "corrupted" their work; the merge behaved exactly as specified.
- • Divergence in a hand-rolled type: replicas disagree despite using "a CRDT". The operator observes anti-entropy repairing the same keys endlessly — the type is not associative, and two-replica tests never caught it.
- • None on the write or merge path. This is the defining property and the reason the technique exists.
- • Coordination reappears in two places, both easy to overlook: safe garbage collection of tombstones, and any invariant the type cannot enforce.
- • A common production shape is CRDTs for the bulk of state plus a small consensus-backed component for the few invariants that matter (Do You Actually Need Consensus?).
- • Reformulating operations to commute removes coordination *requirements* rather than paying for them, which is the only genuinely free move available (Coordination Avoidance: Restructuring the Problem Instead of Paying for It).
- • Every replica remains writable during a partition, and all writes are preserved.
- • On healing, replicas converge with no conflict resolution step and no operator involvement.
- • Duplicated or reordered delivery is harmless for state-based types; operation-based types depend on their transport for that.
- • Invariants spanning replicas are unenforced throughout, and remain violated afterwards — the merge cannot repair what it cannot see.
- • Detect: monitor metadata-to-payload ratio and tombstone age; both grow quietly for months before becoming an incident.
- • Contain: bound document and set sizes with an explicit policy, and cap the metadata a single object may carry.
- • Recover: for divergence in a custom type, property-test the merge for the three properties — associativity is almost always the one that fails.
- • Reconcile: for invariant violations, apply a business-level compensation, because no merge will fix them (A Refund Is Not a Rollback).
- • Verify: run a partition test with concurrent add/remove pairs and confirm the semantics match what your product intends, not merely that the replicas agree.
- • Ratio of metadata bytes to payload bytes per object, trended over months rather than hours.
- • Tombstone count and the age of the oldest tombstone, plus the GC watermark, which together predict a resurrection before it happens.
- • Replica divergence after anti-entropy completes — should be zero for a genuine CRDT, and is the direct test of the algebra.
- • Frequency of concurrent add/remove pairs on the same element, which tells you whether your add-wins choice is actually being exercised.
- • Invariant checks run out of band (negative balances, over-allocated resources), since the type will not report these itself.
- • Offline-first and mobile applications, where the partition is normal operation rather than an incident.
- • Collaborative editing of structured data — lists, sets, maps, whiteboards — where users expect concurrent work to combine.
- • Multi-region active-active state with no cross-region invariant: carts, preferences, presence, counters (Active-Active: Every Conflict Scenario Becomes Real).
- • Replacing an LWW register on data where the discarded write mattered, at no cost in availability.
- • Anything with a global invariant — the type cannot enforce it and its presence creates false confidence.
- • Long-lived documents with heavy edit histories, where metadata growth becomes the dominant cost.
- • Prose and creative content, where automatic merge produces output both authors reject.
- • Data with strong structural constraints that no join preserves, where adopting a CRDT means weakening the constraint.
- • Single-writer data, where the machinery buys nothing at all.
- • An application merge function with the same three properties — the same algebra, without a library, when the type is simple (Only the Application Knows What the Merge Means).
- • Keep siblings and resolve on read, when semantics vary by context and no fixed rule fits (Version Vectors: Making the Conflict Visible).
- • Operational transformation for text, which preserves intent more carefully at the cost of requiring a central server in most deployments.
- • Coordinate on the small set of operations that touch an invariant and use CRDTs for everything else — the common production shape.
- • Reformulate operations to commute without changing storage at all: record "add 1", not "set to 7".
- • A single writer per object, if the concurrency is incidental rather than essential.
Merge as a theorem, and the part it does not prove
r1: adds ["r0#1"] removes ["r0#1"] → x absent r2: adds ["r0#1","r2#1"] removes [] → x present merge(r1, r2) = adds ["r0#1","r2#1"] removes ["r0#1"] → x present merge(r2, r1) = adds ["r0#1","r2#1"] removes ["r0#1"] → x present merge with a redelivered state = adds ["r0#1","r2#1"] removes ["r0#1"] → x present
What people believe, and what is true
CRDTs solve conflict resolution.
They make merge deterministic and convergent. Whether the converged value is right for your domain is a separate question the type cannot answer.
A CRDT counter can enforce a spending limit.
It cannot. Each replica must accept a decrement without consulting peers, so concurrent withdrawals can breach any limit. That needs coordination.
CRDTs remove the need to think about conflicts.
They remove conflict *resolution* from the write path and move the decision into the data model, where you must still choose add-wins or remove-wins and live with it.
CRDT text merging gives you what both authors meant.
It gives you a convergent interleaving. For overlapping edits to the same sentence, that is often text neither author wrote.
CRDT metadata is a solved problem.
Tombstones and tags persist, and collecting them safely requires knowing every replica has seen the removal — coordination re-entering through the back door.
If it converges, it is a CRDT.
Convergence must hold for every order and multiplicity. Hand-rolled types usually fail associativity, and two-replica tests do not detect it.
Go deeper
Only the levels this lesson can honestly fill — a missing level is a claim nobody had.
Overview
Design the type so merging is a mathematical join. Then every replica can accept every write immediately and all replicas end up identical — but "identical" is not "right", and no CRDT can keep a balance above zero.
Practical
Use them for sets, counters, per-field maps and sequences with no cross-replica invariant. Decide add-wins versus remove-wins deliberately and test it. Monitor metadata growth and tombstone age from day one. Keep a separate coordinated path for the few operations with a real invariant.
Advanced
The states form a join-semilattice and merge is the least upper bound, so convergence holds for any delivery order and any multiplicity. State-based types tolerate an arbitrary lossy transport; operation-based types demand exactly-once delivery and often causal order, which pushes the requirement into the network layer. The CALM theorem sharpens the boundary: a program has a coordination-free implementation exactly when it is monotonic — and enforcing a lower bound on a balance is not, which is why that specific example is impossible rather than merely unimplemented.
Apply it
- 🔧 Implement a G-Counter and a PN-Counter, then write a test that shows the PN-Counter breaching a limit under concurrency.
- 🔧 Take a hand-rolled merge in your codebase and property-test associativity with three generated inputs. Report what you find.
- ⚡ Users report items reappearing in a list after they delete them, roughly once a week. Where do you look?
- ⚡ A collaborative document has grown to 40 MB for six pages of text. Explain the mechanism and the options.
- ⚡ Two concurrent withdrawals leave an account at −40. Both replicas checked the balance first. What went wrong, and what is the fix?
- 💬 Explain why a CRDT counter cannot enforce a non-negative balance. Be precise about what would be required.
- 💬 What does a G-Set gain by adding tags to each element, and what does that cost?
- 💬 A team proposes CRDTs for an inventory system with limited stock. What is your response?
- 💬 What is the difference between state-based and operation-based, and what does each demand of the network?