Agreement Without a Vote: CRDTs and the Art of Conflict-Free Replication

The Hook: Two People, One Shopping List, No Signal

Picture you and your partner sharing a shopping list in an app. You are on the subway with no reception and you cross off "milk," because you still have some. At the same moment, in the supermarket and also on a flaky connection, your partner adds "milk," because the fridge looked empty. Ten minutes later both phones are back online. What happens?

In a naive system, whoever writes last wins — and depending on the roll of the network-latency dice, "milk" ends up either on the list or not, with nobody able to reconstruct why. Worse, one sync may overwrite the other wholesale and half the list simply vanishes. Anyone who has ever edited a document twice and later found a "conflicted copy (2)" in the folder knows the feeling.

This mundane example contains one of the deepest problems in distributed computing: how can several replicas of the same data be modified concurrently, independently, and offline — and still be guaranteed to reach the same, sensible final state the moment they meet again? The classic answer is coordination. You make the replicas vote, elect a leader, impose an ordering. That is the world of distributed consensus — powerful, but expensive, slow, and, under a network partition, simply blocked.

There is a radically different answer. It says: if we build our data types cleverly enough at the mathematical level, we need no coordination at all. Conflicts are not resolved by voting; they are ruled out by construction — they cannot arise in the first place. These data types are called Conflict-free Replicated Data Types, or CRDTs. This article takes you from the intuition, through the surprisingly elegant mathematics behind it, to the systems in which CRDTs today merge billions of operations a day — from Redis to Riak to the collaborative editors in which this very text may have been written.

Part 1: Why Agreement Is Normally So Expensive

The CAP Dilemma in One Sentence

Eric Brewer's CAP theorem, proved formally by Gilbert and Lynch in 2002, confronts every distributed system with an uncomfortable choice. When the network is partitioned — when two parts of the system can no longer reach each other, which in practice is unavoidable — you must pick between two evils. Either you refuse writes until the connection is restored (consistency over availability, "CP"), or you accept writes on both sides and risk the states drifting apart (availability over consistency, "AP").

Systems built on consensus — etcd, ZooKeeper, anything on top of Paxos or Raft — consistently choose the first option. They guarantee there is only ever one truth, but they pay for it with latency (every decision needs at least one network round trip to a majority) and with stalls during a partition. That is exactly right for a bank transfer or for electing a cluster leader. For a shopping list, a chat counter, or a shared document it is almost absurd: nobody wants their notes app to freeze just because the train's Wi-Fi is bad.

Eventual Consistency — and Its Sore Spot

The AP world chooses availability. Its promise is called Eventual Consistency: if no new updates arrive, all replicas will eventually reach the same state. Amazon's famous Dynamo paper (2007) made this model respectable for industry, and it sits behind many later articles in this vault, from Consistent Hashing to the Merkle trees of anti-entropy.

The sore spot hides in the word "eventually." Classic eventual consistency says that replicas converge, not how. When two concurrent writes hit the same key, a conflict arises, and someone has to resolve it. Dynamo often handed this job back to the application: it stored both versions as "siblings" and let the client decide. That is honest but inconvenient — and done wrong, it loses data. The most naive resolution, Last-Writer-Wins (the later timestamp wins), is convenient but silently discards writes, and with imprecise clocks the literally wrong version sometimes wins.

So the crucial question is not "do we converge?" but "do we converge deterministically, automatically, and without data loss?" This is exactly where CRDTs come in.

Part 2: Strong Eventual Consistency — a Stronger Promise

In 2011, Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski formalized, in two companion works — the comprehensive INRIA research report and the concise conference version at SSS 2011 — a consistency model sharper than plain eventual consistency. They called it Strong Eventual Consistency (SEC). The definition has two parts:

Eventual Delivery: every update applied by one correct replica is eventually applied by all correct replicas.

Strong Convergence: two correct replicas that have seen the same set of updates are in an equivalent state — immediately, deterministically, with no further communication.

The difference from classic eventual consistency is subtle but fundamental. Classic EC allows replicas to diverge temporarily and resolve the conflict later via rollback or consensus. SEC forbids conflicts, in the sense of rollbacks, entirely: once two replicas know the same updates, they are guaranteed identical. There is no "negotiation," no rollback, no special session. A data type that satisfies SEC is a CRDT.

Two Roads to the Same Destination

Shapiro and colleagues showed there are two complementary construction principles, both guaranteeing SEC — and, remarkably, each able to emulate the other.

State-based CRDTs (CvRDT — "convergent"): each replica holds its full state. To synchronize, a replica sends its entire state to another, and the receiving replica combines both states with a merge function. Convergence is guaranteed if three conditions hold: the possible states form a semilattice (more on this shortly), local updates only make the state "grow" in the sense of that lattice (monotonicity), and merge computes the least upper bound of two states. The great advantage: the network may lose, duplicate, or reorder messages arbitrarily — as long as state gets through now and then, the system converges.

Operation-based CRDTs (CmRDT — "commutative"): instead of whole states, individual operations are transmitted (say, "add X" or "increment by 3"). Each replica applies operations as they arrive. Convergence is guaranteed if concurrent operations commute — that is, yield the same result in any order. The price is a stronger demand on the network: operations must be delivered reliably and in causal order, exactly once (or multiple times, if they are additionally idempotent). You therefore need a dependable broadcast layer. Anyone wondering how "causal order" is defined precisely will find the answer in the vector clocks of Lamport timestamps and vector clocks — they are the foundation on which operation-based CRDTs stand.

The trade-off is practical: state-based CRDTs are robust against a bad network but may ship a lot of ballast (the whole state). Operation-based CRDTs are frugal but demand more of the delivery layer. A later innovation, the delta-state CRDTs of Almeida, Shoker, and Baquero (2016), unites both worlds: you transmit only the small "deltas" that changed since the last sync, while keeping the robustness of the state-based approach.

The Mathematics Behind It: the Semilattice

Why does any of this work? The answer is one of the loveliest ideas in the whole story, and it comes from order theory. The state-based approach requires the possible states to form a join-semilattice. That sounds forbidding but is a simple structure: a set with an ordering in which any two elements have a unique least upper bound (the "join"). The merge function is exactly that join.

For convergence to be guaranteed, the join must have three algebraic properties:

Commutativity: merge(a, b) = merge(b, a). The order in which states are combined does not matter.

Associativity: merge(a, merge(b, c)) = merge(merge(a, b), c). The grouping does not matter.

Idempotence: merge(a, a) = a. Feeding in the same information twice changes nothing.

These three properties are precisely the antidote to the three cruelties of a real network: commutativity defeats reordering, associativity defeats arbitrary grouping of batches, and idempotence defeats duplicates. A network may deliver messages out of order, bundled, and multiple times — the semilattice does not care. As long as the state only travels "upward" and merge takes the least upper bound, all replicas inevitably land at the same point. Here, convergence is not a happy accident but a mathematical theorem.

Part 3: The Zoo of Data Types — from Counter to Set

Theory becomes tangible through examples. Let us look at the canonical CRDTs, ordered from simple to subtle.

G-Counter — the Growing Counter

The grow-only counter counts only upward (likes, page views, tickets sold). The naive approach — a single number that every replica increments — fails at once: if two replicas independently go from 5 to 6 and then merge, the result is 6 instead of the correct 7. The trick: each replica keeps its own partial count in a vector indexed by replica ID. A replica increments only its own entry. The merge takes the element-wise maximum of the two vectors, and the value of the counter is the sum of all entries. Element-wise maximum is obviously commutative, associative, and idempotent — the G-Counter is a clean semilattice. (Look closely and you will recognize the structural kinship with the vector clock.)

PN-Counter — Down as Well

A counter that can also decrement seems to break the maximum principle (decrements do not "grow"). The solution is startlingly simple: use two G-Counters, one for all increments (P) and one for all decrements (N). The value is sum(P) − sum(N). Both parts grow monotonically, the semilattice stays intact. This pattern — "model a negative event as its own positive event" — is one of the recurring mental tricks of the CRDT world.

G-Set and 2P-Set — Sets and Their Deletion Problem

A grow-only set is trivial: elements can only be added, merge is union. Union is commutative, associative, idempotent — done.

The problem begins with deletion. The two-phase set (2P-Set) combines two G-Sets: a set of added elements (A) and a tombstone set of removed ones (R). An element is present if it is in A and not in R. This works — but has two ugly properties: an element once deleted can never be added again (it stays in R forever), and tombstones grow without bound. The 2P-Set is a lesson that a construction can converge and still have unusable semantics.

LWW-Register and Multi-Value Register

A register holds a single value. The last-writer-wins register attaches a timestamp to every write and keeps, on merge, the one with the higher timestamp (ties broken deterministically, e.g. by replica ID). It converges by guarantee but, on genuinely concurrent writes, silently discards one of them. The alternative is the multi-value register (MV-Register): on true concurrency it keeps both values and hands the decision to the application — precisely the "sibling" model from Dynamo, now cleanly formalized.

OR-Set — the Set You Can Delete Correctly

The climax of set design is the observed-remove set (OR-Set). Its idea elegantly solves the re-add problem of the 2P-Set: every add tags the element with a unique, hidden tag (a kind of invisible serial number). A remove does not delete "the element," but only exactly the tags it has already seen. If another replica concurrently adds the same element with a new tag, that new tag survives the concurrent removal — the element stays in the set. This is called add-wins semantics: on a concurrent add and remove of the same element, the add wins.

That is not "more correct" than the opposite variant (remove-wins), but it is an explicit, comprehensible decision — and that is precisely the decisive advance over the randomness of last-writer-wins. Bieniusa and colleagues showed an optimized OR-Set in 2012 that drastically reduces the metadata ballast of the tags and thereby made practical use feasible. Combine several such building blocks and you get composite structures like maps (Riak's data types), in which the values are themselves CRDTs.

Part 4: The Hardest Case — Collaborative Editing

Counters and sets are unordered. Text, however, is an ordered sequence, and order is the final boss of conflict-free replication. When two authors type in different places at the same time, the insertions must not overwrite each other, and the relative order of characters must be reconstructed identically everywhere — without any central authority.

Why Positions as Numbers Are Not Enough

The naive idea of storing each character at an index position fails immediately: if replica A inserts a character at position 3, all following indices shift, and replica B's concurrent insertion at "position 5" lands in the wrong place. The solution of all sequence CRDTs is the same core idea: every character gets a stable, unique identifier that fixes its position relative to its neighbors and never changes again. It must always be possible to insert a new identifier between any two — so you need dense, infinitely divisible position identifiers, often in the form of fractional numbers or paths in a tree.

A Family Tree of Algorithms

The family is large and has grown over a good two decades: WOOT (2006) as an early pioneer; Treedoc and Logoot with tree- and position-based identifiers; LSEQ with a clever strategy that keeps identifiers short; RGA (Replicated Growable Array) with timestamp-based linking; and finally YATA, the algorithm behind the today very popular library Yjs by Kevin Jahns. Notably, the merge behavior of YATA and RGA is essentially the same at its core.

Two projects shape practice: Yjs is optimized for fast text editing and enjoys a reputation for high performance; Automerge by Martin Kleppmann and collaborators implements a full JSON CRDT, uses a compact columnar encoding, and was rewritten in Rust for speed. For rich text — text with formatting — Litt, Kleppmann, and colleagues developed Peritext in 2022, which merges formatting spans conflict-free together with the text.

The Interleaving Anomaly — an Honest Warning

CRDTs guarantee convergence, but not always a humanly sensible result. A well-known problem is interleaving: when two authors concurrently insert whole words at the same spot, some algorithms can interleave the characters of the two contributions — in the extreme, "Hello" and "Howdy" become an unreadable alphabet soup, even though all replicas dutifully converge. Kleppmann and colleagues analyzed these anomalies in detail in 2019 and in "The Art of the Fugue" (2023). The lesson matters: convergence is necessary, but not sufficient for good collaborative semantics. The choice of algorithm remains a design decision with tangible consequences for the user.

An Often-Misunderstood Footnote: Figma

It is frequently claimed that collaborative design tools like Figma run on CRDTs. That is not quite right, and because precision matters here: Figma's multiplayer technique is inspired by CRDT ideas but is not a pure peer-to-peer CRDT. Figma uses a central server as authority and, per object property, a last-writer-wins-style resolution. I am of the opinion that this example illustrates the most important practical insight: if you already have a central server, you often do not need the full machinery of a CRDT — the conflict-free construction unfolds its greatest value where there is no reliable central authority, such as offline-first apps and true peer-to-peer synchronization.

Part 5: The Deeper Truth — the CALM Theorem

Why do CRDTs actually work, and where exactly does their limit lie? The surprisingly general answer is the CALM theorem — Consistency As Logical Monotonicity. Joseph Hellerstein sketched it in his PODS keynote in 2010; together with Peter Alvaro he later formalized and popularized it (the widely read version, "Keeping CALM: When Distributed Consistency Is Easy," appeared as a 2019 preprint and in 2020 in Communications of the ACM).

The theorem says in one sentence: a problem has a consistent, coordination-free distributed implementation if and only if it is monotonic. "Monotonic" means, roughly: new information can only confirm or extend a conclusion once drawn, never retract it. A monotonic program draws only conclusions that later data will not force it to take back.

This is the conceptual bracket around everything said so far. A join-semilattice is the algebraic embodiment of monotonicity: the state only travels "upward," never back. CRDTs are therefore nothing other than the data-type-made-flesh realization of the CALM principle. And CALM simultaneously explains the hard limit: non-monotonic problems — those in which a later piece of information can invalidate an earlier decision — cannot be solved coordination-free. For them, consensus is mandatory.

This is no academic hair-splitting but the compass for architecture. CALM is the constructive, positive flip side of the rather negative message of the CAP theorem: CAP says what is not possible; CALM says exactly when it is possible after all. Where a problem can be phrased monotonically, you may forgo coordination and deploy CRDTs. Where it cannot — more on this shortly — there is no way around voting.

Part 6: CRDTs in the Wild

The theory is elegant, but CRDTs have long been production reality, merging enormous volumes of operations every day.

Riak by Basho was, around 2012/2013, one of the first production stores to make CRDTs first-class data types: counters, sets, registers, flags, and maps. Riak thereby replaced its old, laborious "sibling" conflict model with automatically merging types and used delta techniques internally to save bandwidth.

Redis Enterprise offers, with its Active-Active databases (conflict-free replicated databases, CRDBs), geographically distributed replicas that are all locally writable. Under the hood, Redis combines vector clocks with CRDT semantics and guarantees exactly the strong eventual consistency of Part 2: values may briefly differ between data centers but converge deterministically. Counters and sets are native CRDT types here.

In local and collaborative software, Automerge and Yjs are the load-bearing pillars for offline-first and real-time applications. They deliver on the original promise: edit without a network, sync without a conflict. Other databases such as Azure Cosmos DB offer related, CRDT-adjacent resolution strategies for multi-region writes, without necessarily being pure CRDTs.

The Costs and Limits — the Honest Part

CRDTs are no panacea, and a good architect knows the price.

Metadata ballast and garbage collection. Tags, timestamps, and above all tombstones (gravestones for deleted elements) accumulate. Removing them entirely is delicate, because you must be sure that truly every replica has seen the deletion — and establishing that certainty ("causal stability") sometimes demands exactly the coordination you wanted to avoid. Garbage-collecting CRDT metadata is an active, non-trivial research and engineering topic.

Convergence is not correctness. This is the single most important limitation. CRDTs guarantee that all replicas reach the same state — not that this state respects every business rule. The classic counterexample is a bank account with the invariant "the balance must never go negative." If two replicas concurrently allow a withdrawal because each still sees funds locally, the PN-Counter account converges cleanly — onto a forbidden negative value. Such global invariants and uniqueness constraints (say, "this username may be assigned only once") are non-monotonic and thus fall squarely under the verdict of the CALM theorem: they need coordination. No CRDT in the world can get around this.

Semantics must be chosen deliberately. Add-wins or remove-wins? On concurrent writes, do we keep both values or only one? These questions have no universally correct answer; they depend on the application. CRDTs force the developer to make these decisions explicitly — which is a blessing, but also demands mental effort.

Frameworks and Comparison

State- vs. Operation-Based

The Three Algebraic Commandments (state-based)

The Data-Type Zoo at a Glance

The Central Takeaway

The central insight of CRDTs is a reversal of the usual direction of thought. Normally we ask, "How do we resolve conflicts when they occur?" CRDTs ask, "How do we build data so that conflicts cannot arise in the first place?" The key is to shift the price of reliability from runtime into structure — from expensive coordination in operation to a one-time, careful mathematical construction of the data type.

In practice this means: before reflexively reaching for locks, transactions, or a consensus cluster for a feature, ask the CALM question — is my problem monotonic? Can every operation only "add," never "retract"? If yes, you can probably forgo coordination, cut latency, and gain genuine offline capability by choosing a suitable CRDT. If no — if a global invariant like a non-negative balance or a uniqueness constraint is in play — then the same theorem honestly tells you that no trick in the world spares you the coordination. That clarity about when you must coordinate and when you need not is valuable even if you end up deploying no CRDT at all.

A Question to Ponder

Think of a system you know or are building. Which of its data operations are in truth monotonic — pure additions of facts that never need to be taken back — and for which have you perhaps unconsciously treated a non-monotonicity (a "may only once," a "never below," a "the new replaces the old") as if it necessarily required a central truth, even though it could just as well be reformulated monotonically?

Cross-References in the Vault

• Order Without a Clock: Lamport Timestamps, Vector Clocks, and Causality in Distributed Systems – the causal order and vector clocks on which operation-based CRDTs are built.
• How Machines Come to Agree: Distributed Consensus from FLP to Paxos to Raft – the coordination-based counterpole; CRDTs are the attempt to avoid it.
• The Logbook of Truth: Understanding Event Sourcing and CQRS – operation-based CRDTs are at heart a distributed, commutative event log.
• The Ring That Shares the Load: Consistent Hashing and the Art of Moving Gracefully – Dynamo, the home of eventual consistency and siblings.
• The Tree That Condenses Truth: Merkle Trees and the Art of Efficient Integrity Verification – anti-entropy, which reconciles replicas efficiently.
• Write First, Sort Later – Log-Structured Merge-Trees and the Inversion of the Database – a related storage engine behind Riak and Cassandra.

Sources

• Shapiro, Preguiça, Baquero, Zawirski: Conflict-free Replicated Data Types, SSS 2011 (INRIA/LIP6): https://www.lip6.fr/Marc.Shapiro/papers/2011/CRDTs_SSS-2011.pdf
• Springer version (SSS 2011): https://link.springer.com/chapter/10.1007/978-3-642-24550-3_29
• Almeida, Shoker, Baquero: Delta State Replicated Data Types (2016): https://arxiv.org/pdf/1603.01529
• Bieniusa et al.: An optimized conflict-free replicated set (2012): https://arxiv.org/pdf/1210.3368
• Hellerstein, Alvaro: Keeping CALM: When Distributed Consistency Is Easy, CACM 2020 (arXiv 2019): https://arxiv.org/pdf/1901.01930 · https://cacm.acm.org/research/keeping-calm/
• Kleppmann et al.: The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing (2023): https://arxiv.org/pdf/2305.00583
• Litt, Kleppmann et al.: Peritext: A CRDT for Collaborative Rich Text Editing (2022): https://dspace.mit.edu/bitstream/handle/1721.1/147641/3555644.pdf
• Redis Docs: Active-Active geo-distributed Redis (CRDBs): https://redis.io/docs/latest/operate/rs/databases/active-active/
• Riak Docs: Concept: Data Types (CRDTs): https://docs.riak.com/riak/kv/2.2.3/learn/concepts/crdts/index.html
• CRDT.tech – paper index: https://crdt.tech/papers.html

← All articles