Introduction

Imagine you share a file across a million computers with no central server to ask "who has what." How does any node find what it needs? The naive answer is to ask everyone — flooding the network. The clever answer is Chord, published by Ion Stoica and colleagues at MIT in 2001.

Chord maps every node and every key to a point on a circular number line — a ring of IDs from 0 to 2ᵐ − 1 (typically m = 160 bits). Each key is owned by the node whose ID comes next clockwise, its successor. That rule alone means every key has exactly one responsible node, even as machines join and leave.

The genius is in the lookup. A naive ring would forward each query one step at a time — O(N)O(N) hops. Chord adds a finger table: each node stores shortcuts to nodes at distances 202^{0}, 212^{1}, 222^{2}, 
 2m−12^{m-1} ahead on the ring. Those exponentially growing jumps halve the remaining distance with every hop, reaching any key in O(log⁡N)O(\log N) hops — a provable guarantee that holds even as the network churns.

Like consistent hashing, Chord belongs to the class of solved problems: the algorithm is known, its correctness is proven, and its worst-case complexity is tight.

Try It: The Chord Ring

Below is a Chord ring with IDs 0–15 (4-bit, so m = 4). Active nodes are shown as filled circles on the ring. Each node's finger table points to the successor of ID + 2i2^{i} for i = 0 
 3.

<div class="hint">A 4-bit Chord ring (IDs 0–15). Click a ring slot to toggle a node on/off. Then pick a lookup key and route it hop by hop.</div>
<div class="ring-wrap">
  <canvas id="ring" width="300" height="300"></canvas>
</div>
<div class="controls">
  <label>Lookup key: <input id="keyInput" type="number" min="0" max="15" value="7"></label>
  <button id="routeBtn" type="button">Route lookup</button>
  <button id="resetBtn" type="button" class="ghost">Reset ring</button>
</div>
<div id="log" class="log"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.ring-wrap { display: flex; justify-content: center; margin: .4rem 0; }
canvas { cursor: pointer; border-radius: 50%; }
.controls { display: flex; gap: .5rem; align-items: center; flex-wrap: wrap; margin: .5rem 0; }
label { font-size: .9rem; }
input[type=number] { width: 52px; padding: .3rem .4rem; border: 1px solid #adb1b8; border-radius: 6px; font-size: .9rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.log { font-size: .82rem; line-height: 1.6; color: #333; min-height: 3.5em; border-top: 1px solid #e0e4e8; padding-top: .4rem; margin-top: .3rem; white-space: pre-wrap; }
.log .ok { color: #0a7d33; font-weight: 600; }
.log .err { color: #c92f3c; font-weight: 600; }
.log .step { color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Chord ring simulation: 4-bit ring (m=4, IDs 0..15).
// Each active node maintains a finger table:
//   finger[i] = successor( (node + 2^i) mod 16 )  for i = 0..3
// Lookup from start node to key k:
//   While current node != successor(k):
//     jump to the largest finger that does NOT overshoot k (clockwise).

const M = 4;
const N = 1 << M; // 16 slots
const CX = 150, CY = 150, R = 110, DOT = 11;

// Initial active nodes
let active = new Set([0, 3, 6, 9, 12]);
let highlightPath = []; // [{node, finger}] for animation
let animStep = -1;

const canvas = document.getElementById('ring');
const ctx = canvas.getContext('2d');

// ── Chord helpers ────────────────────────────────────────────────────────────
// Clockwise distance from a to b on ring of size N
function cwDist(a, b) { return (b - a + N) % N; }

// Successor of id: smallest active node >= id (clockwise)
function successor(id) {
  if (active.size === 0) return null;
  // search clockwise
  for (let d = 0; d < N; d++) {
    if (active.has((id + d) % N)) return (id + d) % N;
  }
  return null;
}

// Build finger table for a node
function fingerTable(node) {
  const fingers = [];
  for (let i = 0; i < M; i++) {
    const start = (node + (1 << i)) % N;
    fingers.push({ i, start, node: successor(start) });
  }
  return fingers;
}

// Simulate lookup of key k starting from any active node (pick the lowest)
// Returns array of {from, to, fingerIdx} steps, plus final owner
function lookup(key) {
  if (active.size === 0) return { steps: [], owner: null, error: 'No nodes on ring.' };
  const owner = successor(key);
  const startNode = [...active].sort((a, b) => a - b)[0];
  let cur = startNode;
  const steps = [];
  const visited = new Set();

  while (cur !== owner) {
    if (visited.has(cur)) return { steps, owner, error: 'Routing loop detected.' };
    visited.add(cur);

    const fingers = fingerTable(cur);
    // Find the finger that gets us closest to key without overshooting
    // "Closest without overshooting": finger node f where cwDist(cur, f) <= cwDist(cur, owner) and cwDist(f, owner) is minimized.
    const ownerDist = cwDist(cur, owner);
    let best = null, bestDist = Infinity, bestFinger = -1;
    for (let i = M - 1; i >= 0; i--) {
      const f = fingers[i].node;
      if (f === null) continue;
      const fd = cwDist(cur, f);
      if (fd <= ownerDist && (ownerDist - fd) < bestDist) {
        bestDist = ownerDist - fd;
        best = f;
        bestFinger = i;
      }
    }
    if (best === null || best === cur) {
      // fallback: step to successor
      const s = successor((cur + 1) % N);
      steps.push({ from: cur, to: s, fingerIdx: 0, type: 'successor' });
      cur = s;
    } else {
      steps.push({ from: cur, to: best, fingerIdx: bestFinger, type: 'finger' });
      cur = best;
    }
    if (steps.length > N) return { steps, owner, error: 'Too many hops.' };
  }
  return { steps, owner, error: null };
}

// ── Drawing ──────────────────────────────────────────────────────────────────
function pos(id) {
  const angle = (id / N) * 2 * Math.PI - Math.PI / 2;
  return { x: CX + R * Math.cos(angle), y: CY + R * Math.sin(angle) };
}

function draw() {
  ctx.clearRect(0, 0, 300, 300);

  // Ring base
  ctx.beginPath(); ctx.arc(CX, CY, R, 0, 2 * Math.PI);
  ctx.strokeStyle = '#c9ccd1'; ctx.lineWidth = 1.5; ctx.stroke();

  // Highlight path arcs
  for (let s = 0; s < highlightPath.length; s++) {
    const { from, to } = highlightPath[s];
    const pf = pos(from), pt = pos(to);
    const active_step = animStep < 0 || s <= animStep;
    if (!active_step) continue;
    ctx.beginPath();
    ctx.moveTo(pf.x, pf.y);
    // Draw curved arc
    const mx = (pf.x + pt.x) / 2, my = (pf.y + pt.y) / 2;
    const dx = pt.x - pf.x, dy = pt.y - pf.y;
    const cx2 = mx - dy * 0.25, cy2 = my + dx * 0.25;
    ctx.quadraticCurveTo(cx2, cy2, pt.x, pt.y);
    ctx.strokeStyle = s === animStep ? '#e63946' : '#1d7aed';
    ctx.lineWidth = 2; ctx.stroke();
    // Arrow head
    const angle = Math.atan2(pt.y - cy2, pt.x - cx2);
    ctx.beginPath();
    ctx.moveTo(pt.x, pt.y);
    ctx.lineTo(pt.x - 8 * Math.cos(angle - 0.4), pt.y - 8 * Math.sin(angle - 0.4));
    ctx.lineTo(pt.x - 8 * Math.cos(angle + 0.4), pt.y - 8 * Math.sin(angle + 0.4));
    ctx.closePath(); ctx.fillStyle = s === animStep ? '#e63946' : '#1d7aed'; ctx.fill();
  }

  // Slots (all 16)
  for (let id = 0; id < N; id++) {
    const p = pos(id);
    ctx.beginPath(); ctx.arc(p.x, p.y, DOT, 0, 2 * Math.PI);
    if (active.has(id)) {
      ctx.fillStyle = '#1d3557'; ctx.fill();
      ctx.strokeStyle = '#fff'; ctx.lineWidth = 1.5; ctx.stroke();
    } else {
      ctx.fillStyle = '#fff'; ctx.fill();
      ctx.strokeStyle = '#adb1b8'; ctx.lineWidth = 1; ctx.stroke();
    }
    // Label
    ctx.fillStyle = active.has(id) ? '#fff' : '#888';
    ctx.font = `bold ${id < 10 ? 9 : 8}px ui-monospace, monospace`;
    ctx.textAlign = 'center'; ctx.textBaseline = 'middle';
    ctx.fillText(id, p.x, p.y);
  }

  // Lookup key marker
  const keyVal = parseInt(document.getElementById('keyInput').value, 10);
  if (!isNaN(keyVal) && keyVal >= 0 && keyVal < N) {
    const p = pos(keyVal);
    ctx.beginPath(); ctx.arc(p.x, p.y, DOT + 4, 0, 2 * Math.PI);
    ctx.strokeStyle = '#f4a261'; ctx.lineWidth = 2.5; ctx.stroke();
  }
}

// ── Interaction ─────────────────────────────────────────────────────────────
canvas.addEventListener('click', e => {
  const rect = canvas.getBoundingClientRect();
  const mx = e.clientX - rect.left, my = e.clientY - rect.top;
  // Scale for hi-DPI
  const sx = mx * (canvas.width / rect.width);
  const sy = my * (canvas.height / rect.height);
  let closest = -1, minD = Infinity;
  for (let id = 0; id < N; id++) {
    const p = pos(id);
    const d = Math.hypot(sx - p.x, sy - p.y);
    if (d < minD) { minD = d; closest = id; }
  }
  if (minD < DOT + 8) {
    if (active.has(closest)) active.delete(closest);
    else active.add(closest);
    highlightPath = []; animStep = -1;
    setLog('');
    draw();
  }
});

document.getElementById('keyInput').addEventListener('input', () => {
  highlightPath = []; animStep = -1; setLog(''); draw();
});

function setLog(html) { document.getElementById('log').innerHTML = html; }

document.getElementById('routeBtn').addEventListener('click', () => {
  const keyVal = parseInt(document.getElementById('keyInput').value, 10);
  if (isNaN(keyVal) || keyVal < 0 || keyVal >= N) { setLog('<span class="err">Key must be 0–15.</span>'); return; }
  const { steps, owner, error } = lookup(keyVal);
  highlightPath = steps;
  animStep = -1;

  if (error && !owner) { setLog(`<span class="err">${error}</span>`); draw(); return; }

  let lines = [];
  if (steps.length === 0) {
    lines.push(fmt('<span class="ok">Key %keyVal% is owned by node %owner% — already there (0 hops).</span>', { keyVal: keyVal, owner: owner }));
  } else {
    lines.push(fmt('<span class="step">Routing key %keyVal% → owner is node %owner%:</span>', { keyVal: keyVal, owner: owner }));
    steps.forEach((s, i) => {
      lines.push("  " + fmt('Hop %v%: node %from% → node %to%  (finger[%fingerIdx%], start=%v2%)', { v: i + 1, from: s.from, to: s.to, fingerIdx: s.fingerIdx, v2: (s.from + (1 << s.fingerIdx)) % N }));
    });
    lines.push(fmt('<span class="ok">✓ Reached node %owner% in %length% Hop%v%.</span>', { owner: owner, length: steps.length, v: steps.length !== 1 ? 's' : '' }));
    if (error) lines.push(`<span class="err">${error}</span>`);
  }
  setLog(lines.join('\n'));

  // Animate hops
  animStep = 0;
  draw();
  function nextStep() {
    if (animStep < steps.length - 1) {
      animStep++;
      draw();
      setTimeout(nextStep, 600);
    }
  }
  if (steps.length > 1) setTimeout(nextStep, 600);
});

document.getElementById('resetBtn').addEventListener('click', () => {
  active = new Set([0, 3, 6, 9, 12]);
  highlightPath = []; animStep = -1; setLog(''); draw();
});

draw();

// Log finger table for the first active node on load
(function() {
  const first = [...active].sort((a,b)=>a-b)[0];
  const ft = fingerTable(first);
  const lines = [fmt('Finger table for node %first%:', { first: first })];
  ft.forEach(f => lines.push("  " + fmt('finger[%i%]: start=%start% → node %node%', { i: f.i, start: f.start, node: f.node })));
  console.log(lines.join('\n'));
})();
Result
Console

Add or remove nodes by clicking ring slots. Then choose a lookup key and press Route lookup to watch Chord forward the query hop by hop, each time jumping to the finger closest to but not past the target. Notice how the number of hops stays small even when many nodes are active — the doubling trick cuts the remaining gap in half each step.

The Real Complexity

Chord's guarantees are unusually clean for a distributed system:

  • Lookup correctness: if every node maintains an accurate successor pointer, Chord always finds the responsible node for any key. This holds even during joins and leaves, as long as the ring stays connected.
  • O(log⁡N)O(\log N) hops: the finger table entry at position i points roughly 2i2^{i} ahead. When routing to target t, Chord always picks the largest finger that does not overshoot t. Each hop at least halves the clockwise distance remaining, so ⌈log⁡2\log_{2} N⌉ hops suffice.
  • O(log⁡N)O(\log N) state per node: each node stores only m fingers plus a successor list — logarithmic in the number of nodes, not linear.
  • O(log⁡2N)O(\log ^{2} N) join/leave cost: when a node joins, it must fix its own fingers and notify O(log⁡N)O(\log N) other nodes, each of which may need O(log⁡N)O(\log N) hops to locate the right position — total O(log⁡2N)O(\log ^{2} N) messages.
  • Status: solved. Stoica et al. proved these bounds in 2001 and subsequent work (e.g., the Chord/DHash paper, 2003) verified them on live deployments of thousands of nodes.

The key insight behind the O(log⁡N)O(\log N) bound is the same one behind binary search: doubling your jump distance each step compresses an exponential search space into a linear number of steps. Chord applies it to a circle instead of a sorted array.

One subtlety: the O(log⁡N)O(\log N) guarantee is expected under a random, uniform hash function (SHA-1 in the original paper). Adversarial key distributions can create hot spots, motivating variants like Kademlia, which uses XOR distance for more even load spreading in practice.

Where It Matters

The finger-table idea pioneered by Chord now underlies a surprising range of real systems:

  • BitTorrent DHT (Mainline DHT): uses Kademlia, a Chord variant with XOR distance metric, to locate peers for any torrent without a central tracker. Hundreds of millions of nodes participate.
  • Ethereum peer discovery: nodes use a Kademlia-based DHT to find each other across the global Ethereum network without any central bootstrap beyond a few well-known entry points.
  • Distributed storage (DynamoDB, Cassandra): Amazon DynamoDB and Apache Cassandra use consistent hashing — the same ring idea — to partition data across nodes and rebalance with minimal data movement when a node is added or removed.
  • Content-addressable storage: systems like IPFS hash file content to a key and store it at the responsible node, making retrieval location-independent and censorship-resistant.
  • Decentralized naming: projects building serverless DNS alternatives use DHT lookups to resolve names to IP addresses without a root server.

Whenever you download a torrent, sync a blockchain wallet, or fetch a file from IPFS, a descendant of Chord's finger table is routing your request. The P vs NP boundary does not apply here — the algorithm is efficient and proven — but the distributed engineering challenges of churn, failure, and security remain active research.

Conclusion

Chord answered a question that seemed messy by nature — how do millions of independent nodes agree on who owns what, with no central authority? — with a beautifully clean algorithm: map everything to a ring, jump by powers of two.

The result is provably O(log⁡N)O(\log N) hops to find any key, O(log⁡N)O(\log N) state per node, and graceful handling of joins and leaves. That combination made Chord foundational. Its descendants power the DHTs inside BitTorrent, Ethereum, and distributed databases used by millions every day.

The next time your torrent client finds peers without contacting any central server, remember: it is doing a sequence of finger-table jumps on a virtual ring — Chord's idea, proven correct in 2001, still routing the internet two decades later.

Share this article

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

Comments

Loading comments...

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