Introduction

In a distributed database, multiple replicas hold copies of the same data. Network partitions, slow nodes, and concurrent writes mean those copies diverge — one replica gets an update that another misses.

The naive fix is a central coordinator that serializes every write. But centralization is a single point of failure, and it limits throughput to one machine. Real systems instead let replicas gossip: each node periodically picks a random peer and exchanges a summary of what it knows. Updates propagate like a rumor — exponentially fast, with no coordinator at all.

Gossiping alone doesn't guarantee which differences exist. That's where anti-entropy comes in. Each replica organizes its data into a Merkle tree — a binary tree of hashes where each parent covers the hash of its children. Two replicas compare Merkle roots: if the roots match, they're identical. If not, they walk the tree together, narrowing the mismatch to exactly the changed leaves in O(log⁡n)O(\log n) steps, then ship only those diffs. The result is eventual consistency: given enough rounds, all replicas converge to the same state.

This article is about a solved problem with a beautiful structure: gossip-based anti-entropy powers Apache Cassandra, DynamoDB, Riak, and the epidemic protocols studied by Alan Demers, Srinivasan Keshav, and their colleagues at Xerox PARC in 1987.

Try It

Below are two replicas, each holding eight key-value pairs. The replicas have drifted: some values differ. Both sides build a Merkle tree over their data; each leaf hashes one key-value pair, and each internal node hashes its two children.

<!-- Two-replica Merkle anti-entropy demo -->
<div class="layout">
  <div class="replica-col">
    <div class="replica-label">Replica A</div>
    <div id="treeA" class="tree"></div>
    <div id="storeA" class="store"></div>
  </div>
  <div class="mid-col">
    <div class="mid-status" id="midStatus">Click Step to begin anti-entropy.</div>
    <div class="mid-arrows" id="midArrows"></div>
    <div class="btns">
      <button id="btnStep" type="button">Step</button>
      <button id="btnReset" type="button" class="ghost">Reset</button>
    </div>
  </div>
  <div class="replica-col">
    <div class="replica-label">Replica B</div>
    <div id="treeB" class="tree"></div>
    <div id="storeB" class="store"></div>
  </div>
</div>

/* Merkle anti-entropy demo styles */
* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; color: #222; font-size: 13px; }
.layout { display: flex; gap: 8px; align-items: flex-start; padding: 8px; }
.replica-col { flex: 1; min-width: 0; }
.mid-col { width: 110px; flex-shrink: 0; display: flex; flex-direction: column; align-items: center; gap: 6px; padding-top: 22px; }
.replica-label { font-weight: 700; font-size: .85rem; text-align: center; margin-bottom: 4px; color: #1d3557; }
.tree { margin-bottom: 6px; }
.tree-row { display: flex; justify-content: center; gap: 4px; margin-bottom: 3px; }
.node { display: flex; align-items: center; justify-content: center; border-radius: 6px; font: 600 10px ui-monospace, monospace; border: 1.5px solid #adb1b8; background: #e8eef3; color: #1d3557; transition: background .25s, border-color .25s; }
.node.leaf { width: 30px; height: 26px; }
.node.inner { width: 42px; height: 22px; font-size: 9px; }
.node.root { width: 62px; height: 22px; font-size: 9px; }
.node.match { background: #d4edda; border-color: #28a745; color: #155724; }
.node.diff { background: #f8d7da; border-color: #dc3545; color: #721c24; }
.node.synced { background: #cfe2ff; border-color: #0d6efd; }
.store { display: grid; grid-template-columns: 1fr 1fr; gap: 3px; }
.kv { background: #f0f4f8; border: 1px solid #cdd9e3; border-radius: 5px; padding: 2px 4px; font: 500 11px ui-monospace, monospace; color: #333; transition: background .25s, border-color .25s; }
.kv.dirty { background: #fff3cd; border-color: #ffc107; }
.kv.synced { background: #cfe2ff; border-color: #0d6efd; }
.mid-status { font-size: .8rem; font-weight: 600; text-align: center; color: #444; min-height: 2.4em; line-height: 1.4; }
.mid-status.ok { color: #0a7d33; }
.mid-status.diff { color: #c92f3c; }
.mid-arrows { font-size: 1.4rem; color: #6c757d; min-height: 1.4em; text-align: center; }
.btns { display: flex; flex-direction: column; gap: 5px; width: 100%; }
button { font: 600 12px system-ui; padding: .4rem .6rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; width: 100%; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// 8 shared keys — both replicas start with these
const KEYS = ['alpha','beta','gamma','delta','epsilon','zeta','eta','theta'];
// Replica A values (the canonical state)
const INIT_A = { alpha: 'v1', beta: 'v2', gamma: 'v3', delta: 'v4', epsilon: 'v5', zeta: 'v6', eta: 'v7', theta: 'v8' };
// Replica B has drifted: gamma and eta differ
const INIT_B = { alpha: 'v1', beta: 'v2', gamma: 'v9', delta: 'v4', epsilon: 'v5', zeta: 'v6', eta: 'v11', theta: 'v8' };

// FNV-1a 32-bit hash truncated to 4 hex digits
function hashStr(s) {
  let h = 0x811c9dc5;
  for (let i = 0; i < s.length; i++) { h ^= s.charCodeAt(i); h = (h * 0x01000193) >>> 0; }
  return h.toString(16).slice(0, 4);
}
// Build a Merkle tree bottom-up over 8 leaves
function buildTree(store) {
  const n = KEYS.length;
  // leaf hash = hash of "key=value"
  const leaves = KEYS.map(k => hashStr(k + '=' + store[k]));
  const inner = [];
  let level = leaves;
  const levels = [leaves];
  while (level.length > 1) {
    const next = [];
    for (let i = 0; i < level.length; i += 2) {
      next.push(hashStr(level[i] + (level[i + 1] || '')));
    }
    levels.push(next);
    level = next;
  }
  return { levels, root: level[0] };
}

let storeA, storeB, treeA, treeB;
let phase = 0;
// Three-phase reconciliation
// phase 0: compare Merkle trees and highlight diffs
// phase 1: ship the differing key-value pairs
// phase 2: reset to initial diverged state

function init() {
  storeA = Object.assign({}, INIT_A);
  storeB = Object.assign({}, INIT_B);
  treeA = buildTree(storeA);
  treeB = buildTree(storeB);
  phase = 0;
  document.getElementById('btnStep').disabled = false;
  setStatus('Click Step to begin anti-entropy.', '');
  document.getElementById('midArrows').textContent = '';
  renderAll(null, null);
}

function setStatus(t, cls) {
  const s = document.getElementById('midStatus');
  s.textContent = t;
  s.className = 'mid-status ' + cls;
}

// Render one Merkle tree from bottom (leaves) to top (root)
function renderTree(el, tree, highlights) {
  el.innerHTML = '';
  const revLevels = [...tree.levels].reverse();
  for (let li = 0; li < revLevels.length; li++) {
    const row = document.createElement('div'); row.className = 'tree-row';
    revLevels[li].forEach((h, i) => {
      const nd = document.createElement('div');
      const isRoot = li === revLevels.length - 1;
      const isLeaf = li === 0;
      nd.className = 'node ' + (isRoot ? 'root' : isLeaf ? 'leaf' : 'inner');
      nd.textContent = h;
      if (highlights) {
        const key = li + ',' + i;
        if (highlights.match && highlights.match.has(key)) nd.classList.add('match');
        else if (highlights.diff && highlights.diff.has(key)) nd.classList.add('diff');
        else if (highlights.synced && highlights.synced.has(key)) nd.classList.add('synced');
      }
      row.appendChild(nd);
    });
    el.appendChild(row);
  }
}

function renderStore(el, store, dirtyKeys, syncedKeys) {
  el.innerHTML = '';
  KEYS.forEach(k => {
    const d = document.createElement('div'); d.className = 'kv';
    if (syncedKeys && syncedKeys.has(k)) d.classList.add('synced');
    else if (dirtyKeys && dirtyKeys.has(k)) d.classList.add('dirty');
    d.textContent = k + ': ' + store[k];
    el.appendChild(d);
  });
}

function renderAll(hlA, hlB, dirtyKeys, syncedKeys) {
  renderTree(document.getElementById('treeA'), treeA, hlA);
  renderTree(document.getElementById('treeB'), treeB, hlB);
  renderStore(document.getElementById('storeA'), storeA, dirtyKeys, syncedKeys);
  renderStore(document.getElementById('storeB'), storeB, dirtyKeys, syncedKeys);
}

// Walk both trees simultaneously to find divergent leaf indices
function findDiffLeaves() {
  const n = KEYS.length;
  const diffLeafIdx = [];
  const hlA = { diff: new Set(), match: new Set() };
  const hlB = { diff: new Set(), match: new Set() };

  // Start at the root and recurse into divergent subtrees
  const rootLevel = treeA.levels.length - 1;
  function walk(levelIdx, idx) {
    const hA = treeA.levels[levelIdx][idx];
    const hB = treeB.levels[levelIdx][idx];
    const key = levelIdx + ',' + idx;
    if (hA === hB) {
      hlA.match.add(key); hlB.match.add(key); return;
    }
    hlA.diff.add(key); hlB.diff.add(key);
    if (levelIdx === 0) { diffLeafIdx.push(idx); return; }
    // Recurse into both children of a divergent internal node
    walk(levelIdx - 1, idx * 2);
    if (treeA.levels[levelIdx - 1][idx * 2 + 1] !== undefined) walk(levelIdx - 1, idx * 2 + 1);
  }
  walk(rootLevel, 0);
  return { diffLeafIdx, hlA, hlB };
}

function step() {
  if (phase === 0) {
    // Phase 0 — compare trees and highlight diffs
    const { diffLeafIdx, hlA, hlB } = findDiffLeaves();
    if (diffLeafIdx.length === 0) {
      setStatus('Replicas are already in sync.', 'ok');
      document.getElementById('midArrows').textContent = '';
      renderAll(null, null);
      document.getElementById('btnStep').disabled = true;
      return;
    }
    const diffKeys = new Set(diffLeafIdx.map(i => KEYS[i]));
    renderAll(hlA, hlB, diffKeys, null);
    document.getElementById('midArrows').textContent = '⇄';
    setStatus(i18nFmt('Found %n% divergent leaf/leaves. Click Step to sync.', { n: diffLeafIdx.length }), 'diff');
    phase = 1;
  } else if (phase === 1) {
    // Phase 1 — sync the differing keys (A wins as canonical)
    const { diffLeafIdx } = findDiffLeaves();
    const syncedKeys = new Set(diffLeafIdx.map(i => KEYS[i]));
    syncedKeys.forEach(k => { storeA[k] = storeB[k] = INIT_A[k]; });
    treeA = buildTree(storeA);
    treeB = buildTree(storeB);
    renderAll(null, null, null, syncedKeys);
    document.getElementById('midArrows').textContent = '✓';
    setStatus(i18nFmt('Synced %n% key(s). Replicas now agree!', { n: syncedKeys.size }), 'ok');
    phase = 2;
  } else {
    // Phase 2 — reset for another round
    init();
  }
}

document.getElementById('btnStep').addEventListener('click', step);
document.getElementById('btnReset').addEventListener('click', init);
init();
Result
Console

Click Step to run one round of anti-entropy: the replicas compare their Merkle roots, walk down to the divergent subtrees, and identify exactly which leaves differ. Then they exchange only those key-value pairs. Notice how a tree of height h=log⁡2nh = \log_{2} n finds all differences in at most 2h2h comparisons — far cheaper than sending the entire dataset.

The Real Complexity

Unlike most problems on this site, anti-entropy is solved — the algorithm is known and efficient.

  • Gossip convergence: if each round every node contacts one random peer and the network has nn nodes, a single update reaches all nodes in O(log⁡n)O(\log n) rounds in expectation. Each round doubles the number of informed nodes, so convergence is exponentially fast.
  • Merkle comparison: two replicas holding nn key-value pairs build trees of height ⌈log⁡2n⌉\lceil \log_{2} n \rceil. Comparing roots and walking divergent branches finds all differing leaves in O(d⋅log⁡n)O(d \cdot \log n) messages, where dd is the number of differing leaves. When d≪nd \ll n this is vastly cheaper than a full data transfer.
  • The hidden cost: building and maintaining the Merkle tree is O(n)O(n) space and O(log⁡n)O(\log n) time per update (re-hashing ancestors). For write-heavy workloads this overhead matters.
  • CAP theorem context: anti-entropy is a tool for eventual consistency (the "E" in BASE). It does not give linearizability — replicas can serve stale reads between sync rounds. Systems that need strong consistency pay in availability or partition-tolerance.

The fascinating twist: gossip and anti-entropy look simple, but proving convergence under realistic failure models draws on ideas from epidemic theory, information theory, and the same probabilistic tools that appear in randomized algorithms.

Where It Matters

"Reconcile divergent replicas efficiently" is a fundamental need in any distributed system, and gossip + anti-entropy is the standard answer:

  • NoSQL databases: Apache Cassandra's repair command runs Merkle-tree anti-entropy across all replicas. DynamoDB and Riak use similar mechanisms.
  • Version control: Git's pack-protocol negotiation is structurally anti-entropy — two peers exchange commit hashes (a DAG-shaped Merkle structure) and transfer only the missing objects.
  • Blockchain: Bitcoin's inventory messages propagate new blocks via gossip; block headers form a Merkle chain.
  • Distributed caches: Redis Cluster gossips slot-ownership changes; memcached consistent-hashing rings use similar ideas.
  • Epidemic protocols: the 1987 Demers et al. paper modeled update propagation as an epidemic, showing that "rumor mongering" reaches all nodes before the rumor goes "cold" with high probability.

Understand gossip and anti-entropy and you've grasped the engine beneath eventual consistency, conflict-free replicated data types (CRDTs), and the CAP theorem's practical escape hatch.

Conclusion

Gossip and anti-entropy together answer a fundamental question: how do you keep copies of data consistent across an unreliable network, without any central authority? The answer is elegant — spread updates like a rumor, and use a Merkle tree to pinpoint exactly what is out of sync before sending anything.

The guarantees are real but bounded: convergence is exponentially fast in expectation, and Merkle comparison is logarithmic in the dataset size. What you give up is immediacy — replicas can disagree between rounds, which is the price of availability and partition tolerance in a CAP world.

That trade-off, and the beautiful tree structure that makes it cheap, is why gossip-based anti-entropy remains the workhorse of every large-scale distributed database built in the last three decades.

Share this article

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

Comments

Loading comments...

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