Growing Together Without Coordination – CRDTs and the Mathematics of Conflict-Free Replication

The Hook

Picture three people typing in the same document at the same time. One is on a train drifting in and out of a dead spot, one is in the office, one is at the kitchen table with Wi-Fi that vanishes for seconds at a stretch. Nobody asks permission first, nobody waits for a central server to decide the order of things. And yet all three end up seeing the same document—not roughly the same, but identical character for character. No "editing conflict," no "keep version A or version B?" dialog, no lost change.

From the standpoint of classical distributed-systems theory, this sounds like a contradiction. If several copies of the same data may be changed independently and concurrently, with no coordination, then in the general case inconsistencies arise that can no longer be resolved cleanly after the fact. To restore data integrity, some changes must then be discarded—wholly or partly. That is precisely why so much research is devoted to preventing such concurrent changes: through locks, through consensus, through a leader who dictates the order.

CRDTs—Conflict-free Replicated Data Types—take the opposite road. They allow every change immediately, everywhere, without coordination, and still guarantee that all copies eventually converge. What is remarkable about this is not a clever trick but a mathematical insight: if you design the merge operation so that it satisfies certain algebraic properties, then there simply cannot be an unresolvable conflict anymore. Convergence is then not a stroke of luck but a theorem.

This article explains why replication without coordination normally hurts, which mathematical idea lets CRDTs escape that problem, how the two basic construction styles work, which concrete data types exist—from the humble counter to the collaborative text editor—and where the limits and misconceptions lie. By the end, you should see CRDTs not as magic but as what they are: applied lattice theory in the service of the cloud.

The Core Problem: Why Shared Data Hurts

The moment data lives in more than one place, you must decide what happens when two places simultaneously believe something different about the same value. This is not a fringe question but the hard core of distributed data management.

The most famous tool for thinking about it is Eric Brewer's CAP theorem: during a network partition—that is, when parts of the system cannot reach one another—you must choose between Consistency (everyone sees the same, most-recent value) and Availability (every node keeps answering). During a partition you cannot have both. Classical, strongly consistent systems choose consistency: when in doubt they refuse to answer, or they block until agreement is restored. This is the path of distributed consensus as described by Paxos and Raft—see the vault article on distributed consensus.

For many applications, however, that refusal is unacceptable. A shopping cart that stops working when the network hiccups; a notes app that saves nothing while offline; a chat that freezes when connectivity wobbles—all of these lose users. So a large and practically important class of systems chooses the other road: availability over immediate consistency. This approach is called optimistic replication. Each copy accepts changes immediately and locally; reconciliation between copies happens later, asynchronously, in the background. The promise is not "always identical" but "identical eventually"—eventual consistency.

And this is exactly where the problem lurks. "Identical eventually" is a weak promise. It only says: once no new changes arrive and all messages eventually get through, the copies should converge. It does not say how. In practice you then need conflict resolution, and it is often ugly: "last write wins" with a clock that is never perfectly synchronized across machines; manual selection by the user; or—as notoriously happened with Amazon's early Dynamo shopping cart—the resurrection of already-deleted items, because the merge simply took the union. Eventual consistency without clean semantics is a promise you have to redeem with ad-hoc heuristics, and every heuristic has edges where data silently disappears or wrongly reappears.

The question CRDTs pose is therefore more precise: Is there a subclass of data structures for which the merge of concurrent changes always works unambiguously, always without loss, and always without asking back? The answer is yes—and it is surprisingly elegant.

The Idea: Consistency Through Structure Instead of Agreement

CRDTs were formally defined in 2011 by Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski, building on earlier work by, among others, Baquero and Moura in the late 1990s. Their central coinage is Strong Eventual Consistency (SEC).

The difference from ordinary eventual consistency is decisive. Ordinary eventual consistency only says: eventually the copies will be identical—provided conflict resolution makes it so. Strong eventual consistency sharpens this into a much harder guarantee: two copies that have seen the same set of changes are immediately in the same state—regardless of the order in which the changes arrived, and regardless of whether some arrived twice. There is no more conflict-resolution step, because there is no conflict. Order does not matter. Duplicates do not matter. Delays do not matter.

How can this be? The answer lies in algebra. Shapiro and colleagues showed: if the state of a copy is an element of a so-called join-semilattice and the merge of two states forms their least upper bound (the join), then the copies converge inevitably. Concretely, the merge function must satisfy three properties:

• Commutativity: merge(a, b) = merge(b, a). The order in which two states are merged does not matter. This dispatches the message-ordering problem.
• Associativity: merge(merge(a, b), c) = merge(a, merge(b, c)). It does not matter how states are grouped. This dispatches the problem that different copies receive updates in different bundles.
• Idempotence: merge(a, a) = a. Merging the same state twice changes nothing. This dispatches the problem of duplicated messages.

These three properties together are exactly what makes a semilattice. And because they hold, the merged state is invariant under reordering, regrouping, and duplication of messages. That is the whole magic trick: you no longer demand that the network behave properly. You build the data structure so that the network's bad behavior cannot touch it.

An image for this: think of the maximum of two numbers. max(3, 5) = max(5, 3) (commutative), max(max(3,5),2) = max(3,max(5,2)) (associative), max(5,5) = 5 (idempotent). No matter in what order or how often you throw numbers into the maximum—the result is always the same largest number. A CRDT is, at its core, nothing but a carefully constructed generalization of this principle to richer data types: counters, sets, registers, lists, entire text documents.

The simplest conceivable CRDT illustrates this perfectly: an event flag that can only flip from false to true. "True" means the event has occurred at least once. An event that has occurred cannot un-occur. The merge is simply "true wins." No matter which copy saw the event and which did not, no matter in what order you merge—the result is always the same. One bit, one lattice, guaranteed convergence.

Two Roads to the Same Goal: State and Operation

There are two fundamental ways to build CRDTs, and they differ in what is sent across the network between copies.

State-Based CRDTs (CvRDTs)

State-based CRDTs—also called convergent replicated data types or CvRDTs—send their complete local state to other copies on every synchronization. The receiver merges the received state into its own via merge. For this to converge, merge must satisfy the three lattice properties above, and the local update function must grow the state monotonically with respect to the lattice order.

The great advantage: the demands on the network are minimal. A simple gossip protocol suffices—copies occasionally exchange their state, messages may be lost, arrive twice, arrive in any order. Because merge is associative, merging with one copy's state automatically includes all changes ever made on that copy. The drawback: you may transmit large states even though little has changed.

Operation-Based CRDTs (CmRDTs)

Operation-based CRDTs—commutative replicated data types or CmRDTs—have no merge function at all. Instead of states, they transmit the operations themselves and apply them at each copy. Instead of "my counter now stands at 42," you send "add 10." The operations must be commutative; idempotence is not required, but in exchange a stronger assumption about the network is: every operation must arrive exactly once and in causal order at every copy—not lost, not duplicated.

The advantage: operations are usually tiny compared to the whole state, so you save bandwidth—especially when many copies change little. The price: you need a reliable, causally ordering delivery infrastructure. Causal order means that an operation that logically depends on another never arrives before it—a concept closely related to the logical time that Spanner's TrueTime masters in another way (see the vault article).

The two approaches are theoretically equivalent in power—each can emulate the other. In practice you choose according to network and data type. State-based is more robust and simpler to implement; operation-based is more economical.

Delta CRDTs: The Best of Both Worlds

The obvious weakness of state-based CRDTs—constantly shipping the complete state—was mitigated with delta-state CRDTs, introduced by Almeida, Shoker, and Baquero (2015/2018). The idea: instead of the whole state, you send only the recent changes as small delta fragments, which are themselves valid lattice elements and merged in via merge. This achieves the bandwidth thrift of the operation-based variant with the robust semantics of the state-based one. Most production systems—Riak and Automerge among them—use delta techniques internally.

The Toolbox: Concrete CRDTs

The theory becomes tangible once you see how individual data types are built. A recurring design pattern is: compose complex CRDTs from simpler ones.

Counters

A naive distributed counter does not work: if two copies both go "from 5 to 6" and you take their states, increments are lost. The G-Counter (grow-only counter) solves this by giving each of the n nodes its own slot in an array. Node i increments only P[i]. The value is the sum of all slots. The merge takes the maximum slot by slot—and because each node only counts up its own slot, no increment is lost. Commutative, associative, idempotent: satisfied.

A G-Counter can only grow. To also decrement, you combine two G-Counters into a PN-Counter: one for increments (P), one for decrements (N). The visible value is P minus N. Important—and instructive—is the observation: the internal state always grows monotonically (both sub-counters only rise), even though the externally visible value falls. This separation between a monotonically growing interior and an arbitrarily fluctuating exterior value is a core principle of many CRDTs.

Sets

Sets get more interesting because adding and removing can compete. The simplest variant, the G-Set, allows only adds; the merge is the union. Clean, but you can never delete anything.

The 2P-Set (two-phase set) adds a second set—a "tombstone" set for removed elements. An element counts as present if it is in the add set but not in the remove set. Drawback: once removed, an element stays removed forever—you cannot re-add it. "Remove wins."

The LWW-Element-Set (last-write-wins) attaches a timestamp to each add and remove. An element is present if its latest add is newer than its latest remove. Advantage over the 2P-Set: elements can be re-added after removal. Drawback: you depend on synchronized clocks and a bias rule for ties.

The semantically cleanest widespread variant is the OR-Set (observed-remove set). Instead of timestamps it uses unique tags: every add generates a new, unique tag. A remove deletes only exactly the tags it observed at that moment. An element is present as long as at least one non-removed add tag exists. The decisive advantage: if one copy removes an element and another concurrently re-adds it, the add wins—because the new add tag never "saw" the removal. This matches most users' intuition far better than "remove wins." It is exactly this "add wins" semantics that, for instance, the bookmaker bet365 uses in its Riak-based storage.

The following table summarizes the toolbox:

From registers (LWW register or multi-value register) and these sets you then compose maps and finally whole object trees—the basis for document databases like Riak or for JSON-like structures in Automerge.

The Hard Parts: Text and Order

Counters and sets are the easy part. The hard one—and historically the actual engine of CRDT research, since CRDTs grew out of collaborative editing—is the ordered sequence: a list into which you insert and delete at arbitrary positions while several authors work simultaneously. This is exactly what a text editor needs.

The problem: positions as indices (character 5, character 6 …) do not work, because a concurrent insertion at an earlier position shifts all subsequent indices. The CRDT answer is to give each character an immutable, unique position that can lie between two existing positions—a dense, totally ordered set of identifiers. Well-known sequence CRDTs are called Treedoc, RGA (Replicated Growable Array), WOOT, Logoot, LSEQ, and YATA. They differ in how they generate these position identifiers: as paths in a tree, as fractional numbers between neighbors, as chained predecessor references.

A deletion is usually realized not as an actual removal but as a tombstone—the character is kept, marked as "deleted," so that concurrent references to it do not reach into the void. This is correct, but it costs memory, which is why sophisticated implementations clean up tombstones later or encode them more compactly from the start.

The Interleaving Anomaly

That a CRDT converges does not mean the result is meaningful. Martin Kleppmann and colleagues (Gomes, Mulligan, Beresford) described in 2019 a subtle but important class of errors: the interleaving anomaly. When two authors concurrently insert a word at the same position—say "Alice" and "Charlie"—a naive sequence CRDT can interleave the characters and produce "Al Ciharcliee" instead of "Alice Charlie" or "Charlie Alice." Both copies converge to this gibberish—consistent, but useless.

The research showed: Logoot, LSEQ, Treedoc, and WOOT are susceptible to this anomaly; RGA shows a weaker form only when typing backwards. Weidner and Kleppmann later even proved that there can be no list CRDTs that avoid every form of interleaving, and with Fugue proposed a CRDT that at least minimizes it. This is a fine example of the fact that mathematical convergence is only half the battle—the semantics must also match human expectation.

The Race for Speed

For a long time, CRDTs for text were considered theoretically elegant but too slow and memory-hungry in practice. That has flipped. Industrial implementations clearly beat academic ones, because they optimize aggressively and test more realistically. The pioneer is Yjs by Kevin Jahns, which uses a flat, doubly linked list instead of a tree and thereby reaches enormous throughputs (on the order of tens to hundreds of thousands of operations per second). Seph's famous blog series "CRDTs go brrr" and the modern Automerge 2.0 version showed that a quarter-million keystrokes can be processed in under a second. This has made CRDTs for text conclusively production-ready.

From Practice: Where CRDTs Already Work

CRDTs are long past being a lab idea. A selection:

Riak is a distributed NoSQL database that offers CRDTs (Riak Data Types) as first-class citizens. The most prominent example: League of Legends uses Riak's CRDTs for its in-game chat, which handles 7.5 million concurrent users and around 11,000 messages per second. The bookmaker bet365 stores hundreds of megabytes in Riak's OR-Set implementation.

Redis offers, with "CRDT-enabled databases" (active-active geo-replication), CRDT data types for globally distributed writes. SoundCloud open-sourced Roshi, an LWW-Element-Set CRDT built on Redis for the activity stream. Azure Cosmos DB also has CRDT data types.

Apple uses CRDTs in the Notes app to sync offline edits between devices—the internal class is tellingly named TTMergeableString. TomTom syncs navigation data between a user's devices via CRDT. Microsoft's Fluid Framework and Teletype for the Atom editor build real-time collaborative editing on CRDTs.

An interesting borderline case is Figma: it uses not a pure CRDT but a server-authoritative last-writer-wins scheme per property and fractional indexing for ordered sequences—a deliberate design decision that shows CRDT ideas (LWW register, dense position identifiers) are formative even outside pure CRDT systems.

Perhaps the most important trend is local-first software—a term coined by Kleppmann's group for applications whose data lives primarily on the local device and for which synchronization is an add-on, not a prerequisite. CRDTs are the technical foundation of this movement, because they enable offline work, instant responsiveness, and later conflict-free merging. Libraries like Yjs, Automerge, and the newer Loro are driving this idea into ever more applications in 2026.

Limits and Misconceptions

As elegant as CRDTs are, they are no panacea, and a few misconceptions persist stubbornly.

CRDTs do not "resolve" conflicts, they define them away. A CRDT guarantees that all copies converge to the same state. It does not guarantee that this state is the one a user would have wanted. "Add wins" or "last write wins" are design decisions with semantic consequences. With two concurrent changes to the same account balance, for example, "last write wins" simply leads to the loss of one entry. CRDTs shift the problem from "technical divergence" to "semantic appropriateness"—but do not solve it per se.

CRDTs cannot enforce global invariants. Because every copy writes without coordination, no CRDT can guarantee a condition like "the balance must never go negative" or "this username may exist only once." Such uniqueness and bound conditions need coordination—so, again, consensus. CRDTs and consensus are not competitors but two tools for two different classes of problem.

Metadata grows. Tombstones, unique tags, position identifiers, version vectors—all of this costs memory, often more than the actual payload. A large part of CRDT research is about limiting this overhead (optimized OR-Sets, delta techniques, tombstone cleanup). I am of the opinion that it is exactly this metadata overhead—not compute time—that is the true limiting factor for the broad adoption of CRDTs, even though modern implementations have reduced it substantially.

Causal delivery is a real requirement. Operation-based CRDTs presuppose a network that delivers operations exactly once and in causal order. This is not free; it requires sequence numbers, version vectors, or middleware that supplies these guarantees.

Despite these limits, the conceptual gain remains enormous: for the large class of problems where every copy should be able to write and semantic "mergeability" is acceptable, CRDTs turn an ugly operational problem into a clean mathematical one.

The Central Takeaway

The real lesson of CRDTs reaches beyond distributed systems. It is: you can translate a difficult runtime guarantee into a simple structural property. Instead of laboriously ensuring at runtime that messages arrive in the right order, without duplicates and without loss, you build the data structure once so that order, duplicates, and loss do not matter to it. The hard work moves from operations into design—and is done there once and for all.

In practice this means: the next time you face a synchronization problem—two caches, two devices, two data centers holding the same value—ask first whether your data can be modeled as a lattice. Is the merge commutative, associative, and idempotent? If yes, you need neither locks nor a leader nor conflict resolution—you only need a merge that is a join. If no, you know at once that you need real coordination and can afford the cost of consensus deliberately, instead of accidentally circumventing it.

CRDTs are thus less a technology than a way of thinking: look for the algebraic structure that makes your problem harmless.

The Reflection Question

Which data in your own systems do you handle today with locks, transactions, or "last write wins," even though it could in truth be modeled as a conflict-free mergeable lattice—and which really needs the coordination, because a global invariant is at stake?

Cross-References in the Vault

• How Machines Come to Agree: Distributed Consensus from FLP to Paxos to Raft – the counterpart to CRDTs: when coordination is unavoidable.
• The Ring That Shares the Load: Consistent Hashing and the Art of Moving Gracefully – how data gets distributed across many copies in the first place.
• Clocks That Know Their Own Uncertainty: Google Spanner, TrueTime, and Mastering Time in the Cloud – time and causal order in distributed systems.
• The Logbook of Truth: Understanding Event Sourcing and CQRS – state as the result of a sequence of operations, kin to operation-based CRDTs.

Sources

• Shapiro, Preguiça, Baquero, Zawirski (2011): Conflict-Free Replicated Data Types, SSS 2011 – the formal definition and the SEC proof. https://hal.inria.fr/hal-00932836/file/CRDTs_SSS-2011.pdf
• Shapiro et al. (2011): A Comprehensive Study of Convergent and Commutative Replicated Data Types, INRIA RR-7506 – the detailed technical report with all data types.
• Wikipedia: Conflict-free replicated data type – current overview of construction styles, data types, and practice. https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type
• Almeida, Shoker, Baquero (2018): Delta State Replicated Data Types, Journal of Parallel and Distributed Computing. https://arxiv.org/abs/1603.01529
• Kleppmann, Gomes, Mulligan, Beresford (2019): Interleaving anomalies in collaborative text editors, PaPoC 2019. https://martin.kleppmann.com/papers/interleaving-papoc19.pdf
• crdt.tech – curated collection of papers and implementations (Yjs, Automerge, et al.). https://crdt.tech/

← All articles