Conflict-Free Replicated Data Types

Imagine two people editing the same shared list while offline on a plane. When they land and reconnect, who wins? In most systems you get a conflict — one person's changes overwrite the other's. Someone loses their work.

Conflict-free Replicated Data Types (CRDTs) are a family of data structures, introduced by Marc Shapiro, Nuno Preguiça, Carlos Baquero and Marek Zawirski in 2011, that make this problem disappear mathematically. Each replica can accept any local edit without asking permission. When replicas sync, the merge is automatic, deterministic, and always produces the same result — no matter what order messages arrive, no matter how long replicas were offline.

The secret is not clever conflict resolution. It is choosing data structures whose mathematical properties make conflicts impossible in the first place. The merge function must be commutative (order does not matter), associative (grouping does not matter), and idempotent (applying the same update twice has no extra effect). Any structure satisfying these three laws is a CRDT, and two replicas running a CRDT are mathematically guaranteed to converge.

Below are two independent replicas of a collaborative to-do list — a simple CRDT called an OR-Set (Observed-Remove Set). Each replica lets you add or remove items while "offline." When you click Merge, both replicas sync and instantly converge to the same state.

<p class="hint">{{hint}}</p>
<div class="replicas">
  <div class="replica" id="replicaA">
    <div class="replica-label">Replica A <span class="badge">{{offline}}</span></div>
    <ul id="listA" class="item-list"></ul>
    <div class="add-row">
      <input id="inputA" type="text" placeholder="{{add_placeholder}}" maxlength="30">
      <button id="addA" type="button">{{add_btn}}</button>
    </div>
  </div>
  <div class="merge-col">
    <button id="mergeBtn" type="button" class="merge-btn">{{merge_btn}}</button>
    <div class="merge-note" id="mergeNote"></div>
  </div>
  <div class="replica" id="replicaB">
    <div class="replica-label">Replica B <span class="badge">{{offline}}</span></div>
    <ul id="listB" class="item-list"></ul>
    <div class="add-row">
      <input id="inputB" type="text" placeholder="{{add_placeholder}}" maxlength="30">
      <button id="addB" type="button">{{add_btn}}</button>
    </div>
  </div>
</div>
<div class="merged-view" id="mergedView" style="display:none">
  <div class="merged-label">{{merged_label}}</div>
  <ul id="mergedList" class="item-list merged"></ul>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.replicas { display: flex; gap: .5rem; align-items: flex-start; }
.replica { flex: 1; border: 1.5px solid #cdd9e3; border-radius: 10px; padding: .6rem .7rem; background: #f8fafc; }
.replica-label { font-weight: 700; font-size: .82rem; color: #1d3557; margin-bottom: .4rem; display: flex; align-items: center; gap: .4rem; }
.badge { font-size: .7rem; font-weight: 600; background: #e63946; color: #fff; border-radius: 999px; padding: .1rem .45rem; }
.badge.synced { background: #0a7d33; }
.item-list { list-style: none; margin: 0 0 .5rem; padding: 0; min-height: 60px; }
.item-list li { display: flex; align-items: center; gap: .4rem; padding: .25rem 0; border-bottom: 1px solid #e8eef3; font-size: .88rem; }
.item-list li:last-child { border-bottom: none; }
.item-list li .item-text { flex: 1; }
.item-list li.removed .item-text { text-decoration: line-through; color: #999; }
.item-list.merged li { background: #f0fdf4; border-radius: 4px; padding: .25rem .4rem; margin-bottom: .15rem; border: none; }
.item-list.merged li.removed { display: none; }
.item-toggle { cursor: pointer; font-size: 1rem; background: none; border: none; padding: 0; line-height: 1; color: #1d3557; }
.item-toggle:hover { color: #e63946; }
.add-row { display: flex; gap: .35rem; }
.add-row input { flex: 1; padding: .3rem .5rem; border: 1px solid #cdd9e3; border-radius: 6px; font-size: .82rem; }
.add-row button { padding: .3rem .6rem; background: #1d3557; color: #fff; border: none; border-radius: 6px; cursor: pointer; font-size: .82rem; }
.merge-col { display: flex; flex-direction: column; align-items: center; justify-content: flex-start; padding-top: 2.2rem; gap: .4rem; min-width: 70px; }
.merge-btn { padding: .5rem .7rem; background: #457b9d; color: #fff; border: none; border-radius: 8px; cursor: pointer; font-size: .9rem; font-weight: 700; white-space: nowrap; }
.merge-btn:hover { background: #1d3557; }
.merge-note { font-size: .75rem; color: #555; text-align: center; max-width: 70px; line-height: 1.3; }
.merged-view { margin-top: .8rem; border: 1.5px solid #0a7d33; border-radius: 10px; padding: .6rem .7rem; background: #f0fdf4; }
.merged-label { font-weight: 700; font-size: .82rem; color: #0a7d33; margin-bottom: .3rem; }

// Code not found

Notice: it does not matter which replica you edited first, or how many times you toggled items. The merge is always the same. This is the commutativity and idempotency guarantee at work. Related: the same idea powers the distributed consensus behind P vs NP and Nash equilibrium games where agents must reach agreement.

CRDTs are not magic — they make a precise mathematical trade.

The lattice structure. Every CRDT state lives in a join-semilattice: a partially ordered set where any two elements have a unique least upper bound (the join). Merging two replicas is simply computing the join. Because joins are commutative, associative, and idempotent by definition, convergence is automatic and provable.

State-based vs. operation-based. There are two flavors:

• State CRDTs (CvRDTs): replicas broadcast their full state; the merge is the join. Easy to reason about, but can be verbose for large states.
• Operation CRDTs (CmRDTs): replicas broadcast only the operation (e.g., "add item X"). Smaller messages, but the network must deliver operations exactly once and in causal order.

The CAP theorem shadow. CRDTs live at the AP corner of the CAP theorem (Available + Partition-tolerant). You give up strong consistency — at any moment, two replicas can disagree — but you get the eventual consistency guarantee: once all updates are delivered, every replica holds the same value.

What you pay. CRDTs can only represent operations that never need to be "undone" in a conflicting way. A grow-only counter is trivial. A last-writer-wins register is easy. A set that lets you add and remove the same element — the OR-Set — needs tombstones (records of deletions) that grow forever unless you run a garbage-collection protocol. More expressive CRDTs (like collaborative text sequences used by distributed systems) require metadata per character that can dwarf the actual content.

The status of CRDTs is solved and deployed — the mathematical foundations were established by Shapiro et al. (2011). Engineering trade-offs around metadata growth remain active research.

CRDTs are not an academic curiosity — they run inside some of the most used software on Earth:

• Collaborative text editors: Figma, Notion, and many multiplayer document tools use sequence CRDTs (like RGA or LSEQ) to let multiple people type simultaneously without locks or servers deciding who wins.
• Distributed databases: Amazon DynamoDB's shopping-cart merging, Redis CRDT mode, and Riak's data types all use CRDT semantics to allow write availability across data centers during network partitions.
• Mobile and offline-first apps: apps that need to work on a plane or subway — note-taking, task managers, health trackers — use CRDTs to sync cleanly when connectivity returns.
• Multiplayer games: game state (scores, inventories, position histories) can be represented as CRDTs so that lag spikes and disconnects don't cause rollback conflicts.
• Version control intuition: Git's merge algorithm is not a CRDT (it can produce conflicts), but the ideal of "always converge" is the CRDT promise. Some research systems build CRDT-based version control.

Whenever you need availability (the system keeps working offline) combined with automatic sync (no human resolves conflicts), a CRDT is the right tool. The cost is extra metadata and the restriction that your operations form a lattice — but for the right problems, that trade is absolutely worth it.

CRDTs answer a question that sounds impossible: can many replicas edit the same data independently and always end up agreeing? The answer is yes — but only if you design your data structure so that every merge is a join in a lattice.

The price is real: you give up strong consistency and accept that at any moment different nodes may see different values. You also accept that some operations (especially deletion) carry extra bookkeeping. But the reward is a system where network partitions become a latency problem, not a correctness problem — and offline editing just works.

In a world of phones that go underground and data centers that lose connectivity, that guarantee is extraordinarily valuable. CRDTs are one of the clearest examples in computer science where the right mathematical structure — a join-semilattice — makes a seemingly hard coordination problem disappear entirely.