Introduction

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.

Merge Two Replicas

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">Each column is an independent replica of a shared to-do list (an <b>OR-Set CRDT</b>).
    Toggle items in either replica while “offline,” then click <b>Merge</b> to sync.
    No matter what order you make changes, both replicas always converge to the same state.</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 item…" maxlength="30">
      <button id="addA" type="button">Add</button>
    </div>
  </div>
  <div class="merge-col">
    <button id="mergeBtn" type="button" class="merge-btn">⇄ Merge</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 item…" maxlength="30">
      <button id="addB" type="button">Add</button>
    </div>
  </div>
</div>
<div class="merged-view" id="mergedView" style="display:none">
  <div class="merged-label">Merged state (identical on both replicas)</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; }

// OR-Set CRDT: each item has a unique ID. Adding gives it a fresh "add-tag" per
    // replica; removing tombstones all known add-tags. Merge = union of add-sets +
    // union of tombstones. An item is present iff it has at least one add-tag NOT in
    // the tombstone set. Commutativity, associativity and idempotency follow from set
    // union — so any two replicas always converge to the same state.
let nextId = 0;
function uid() { return 'id' + (nextId++); }

// Replica state: Map<itemText, {addTags: Set<string>, tombstones: Set<string>}>
function freshReplica() { return new Map(); }

function addItem(replica, text) {
  const key = text.trim().toLowerCase();
  if (!key) return;
  if (!replica.has(key)) replica.set(key, { addTags: new Set(), tombstones: new Set(), display: text.trim() });
  replica.get(key).addTags.add(uid());
}

function removeItem(replica, key) {
  if (!replica.has(key)) return;
  const entry = replica.get(key);
  // tombstone all current add-tags (OR-Set remove)
  entry.addTags.forEach(t => entry.tombstones.add(t));
}

function isPresent(entry) {
  for (const t of entry.addTags) { if (!entry.tombstones.has(t)) return true; }
  return false;
}

function mergeReplicas(a, b) {
  const result = new Map();
  const allKeys = new Set([...a.keys(), ...b.keys()]);
  allKeys.forEach(key => {
    const ea = a.get(key) || { addTags: new Set(), tombstones: new Set(), display: key };
    const eb = b.get(key) || { addTags: new Set(), tombstones: new Set(), display: key };
    const addTags = new Set([...ea.addTags, ...eb.addTags]);
    const tombstones = new Set([...ea.tombstones, ...eb.tombstones]);
    result.set(key, { addTags, tombstones, display: ea.display || eb.display });
  });
  return result;
}

// seed initial items in both replicas
const stateA = freshReplica();
const stateB = freshReplica();
['Buy groceries', 'Call dentist', 'Read CRDT paper'].forEach(t => { addItem(stateA, t); addItem(stateB, t); });

function renderReplica(listEl, replica) {
  listEl.innerHTML = '';
  replica.forEach((entry, key) => {
    const li = document.createElement('li');
    const present = isPresent(entry);
    if (!present) li.classList.add('removed');
    const span = document.createElement('span');
    span.className = 'item-text';
    span.textContent = entry.display || key;
    const btn = document.createElement('button');
    btn.className = 'item-toggle';
    btn.title = present ? 'Remove' : 'Add back not supported in OR-Set (use Add)';
    btn.textContent = present ? '✕' : '✓';
    btn.addEventListener('click', () => {
      if (present) removeItem(replica, key);
      render();
    });
    li.appendChild(span);
    li.appendChild(btn);
    listEl.appendChild(li);
  });
}

function renderMerged(merged) {
  const listEl = document.getElementById('mergedList');
  listEl.innerHTML = '';
  merged.forEach((entry, key) => {
    if (!isPresent(entry)) return;
    const li = document.createElement('li');
    const span = document.createElement('span');
    span.className = 'item-text';
    span.textContent = entry.display || key;
    li.appendChild(span);
    listEl.appendChild(li);
  });
}

let merged = null;

function render() {
  renderReplica(document.getElementById('listA'), stateA);
  renderReplica(document.getElementById('listB'), stateB);
  if (merged !== null) {
    merged = mergeReplicas(stateA, stateB);
    renderMerged(merged);
  }
  // reset badges to offline after any edit
  document.querySelectorAll('.badge').forEach(b => { b.textContent = 'offline'; b.classList.remove('synced'); });
  if (merged !== null) {
    document.querySelectorAll('.badge').forEach(b => { b.textContent = 'synced'; b.classList.add('synced'); });
  }
}

function addFromInput(replica, inputId) {
  const inp = document.getElementById(inputId);
  const text = inp.value.trim();
  if (!text) return;
  addItem(replica, text);
  inp.value = '';
  merged = null; // mark as diverged again
  render();
}

document.getElementById('addA').addEventListener('click', () => addFromInput(stateA, 'inputA'));
document.getElementById('addB').addEventListener('click', () => addFromInput(stateB, 'inputB'));
document.getElementById('inputA').addEventListener('keydown', e => { if (e.key === 'Enter') addFromInput(stateA, 'inputA'); });
document.getElementById('inputB').addEventListener('keydown', e => { if (e.key === 'Enter') addFromInput(stateB, 'inputB'); });

document.getElementById('mergeBtn').addEventListener('click', () => {
  merged = mergeReplicas(stateA, stateB);
  // write merged state back to both replicas so they are identical
  stateA.clear(); merged.forEach((v, k) => stateA.set(k, { addTags: new Set(v.addTags), tombstones: new Set(v.tombstones), display: v.display }));
  stateB.clear(); merged.forEach((v, k) => stateB.set(k, { addTags: new Set(v.addTags), tombstones: new Set(v.tombstones), display: v.display }));
  document.getElementById('mergedView').style.display = '';
  const note = document.getElementById('mergeNote');
  const count = [...merged.values()].filter(isPresent).length;
  note.textContent = count + ' ' + (count !== 1 ? 'items converged' : 'item converged');
  renderMerged(merged);
  render();
  console.log('Merged OR-Set:', [...merged.entries()].map(([k,e]) => k + ':' + (isPresent(e)?'present':'removed')).join(', '));
});

render();
Result
Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/crdt/Content licensed under CC BY-NC 4.0.