Chord: A Scalable Peer-to-Peer Lookup Protocol

Chord is a Distributed Hash Table (DHT) protocol that organizes nodes into a circular identifier ring of size $2^n$, where each node and each key is assigned an n-bit identifier. This article provides a comprehensive guide to understanding how Chord works, from basic concepts to advanced operations like node joins and lookups.

Overview

Distributed Hash Tables (DHTs) are peer-to-peer (P2P) algorithms that store key-value pairs across a network of nodes without any central coordinator. Each node in the network can efficiently store and retrieve data by distributing keys across the participating nodes.

Peer-to-peer (P2P) systems often involve thousands or millions of nodes, and we want to distribute key–value pairs without any central coordinator. But this leads to a core question:

How do we efficiently find the node responsible for storing a particular key?

A Distributed Hash Table (DHT) like Chord solves this by hashing keys into an identifier space and distributing those keys across nodes. Chord guarantees that any node can locate the owner of any key in O(log N) messages—even if nodes frequently join and leave.

Chord Network

A Chord network is a distributed hash table (DHT) that organizes nodes in a circular ID ring so they can store and find key–value data efficiently and without any central server.

Key Concepts:

🔢 1. Identifier Space

All node IDs and key IDs lie in the range:

$0 \leq ID < 2^n$

The numbers wrap around to form a ring.

Example from the figure above:

• Identifier Space = 4 bits
• Maximum possible nodes = $2^4 = 16$ (IDs from 0 to 15)
• Active nodes in the diagram: 7 (nodes 0, 1, 3, 6, 7, 11, 14)

🔐 2. Key Placement Rule (Successor Rule)

To store a key-value pair:

• A key is stored at the first node whose ID is ≥ keyID when walking clockwise around the ring.
• This node is called the successor of the key.
• If no node has a greater ID (i.e., wrap-around case), the successor is the first node in the ring.

Examples from the figure above:

• Key 1 stored at node 1 (as 1 is the first active node ≥ 1)
• Keys 2, 3 stored at node 3 (as 3 is the first active node ≥ 2 and ≥ 3)
• Keys 4, 5, 6 stored at node 6 (as 6 is the first active node ≥ 4, 5, 6)
• Key 7 stored at node 7 (as 7 is the first active node ≥ 7)
• Keys 8, 9, 10, 11 stored at node 11 (as 11 is the first active node ≥ 8, 9, 10, 11)
• Keys 12, 13, 14 stored at node 14 (as 14 is the first active node ≥ 12, 13, 14)
• Key 15 (wrap-around case): No node ≥ 15, so wraps to node 0

🧭 3. Successor & Predecessor

Each node maintains:

• a successor (next clockwise node)
• a predecessor (previous counter-clockwise node)

These alone ensure correctness but make lookups slow (O(N)).

Example from the diagram above:

Successor:

• Successor of 0 → 1
• Successor of 1 → 3
• Successor of 3 → 6
• Successor of 6 → 7
• Successor of 7 → 11
• Successor of 11 → 14
• Successor of 14 → wraps → 0

Predecessor:

The predecessor of a node is the previous active node counter-clockwise.

• Predecessor of 1 → 0
• Predecessor of 3 → 1
• Predecessor of 6 → 3
• Predecessor of 7 → 6
• Predecessor of 11 → 7
• Predecessor of 14 → 11
• Predecessor of 0 → 14

⚡ 4. Finger Table (Speeding Up Lookups)

To accelerate lookups, each node maintains a table of shortcuts:

For a node N, finger i points to:

$N + 2^i \pmod{2^n}$, for $0 \leq i < n$

This reduces lookup time to:

O(log N)

We will learn how finger tables work clearly with a detailed example below.

🔄 5. Node Join

When a node joins:

1. It contacts an existing node.
2. Finds its correct position (successor and predecessor).
3. Takes responsibility for a part of the ID range previously held by its successor.
4. Keys within that range are migrated to it.
5. The finger tables eventually stabilize.

We will learn how node joins work clearly with a detailed example below.

👋 6. Node Departure

When a node leaves:

1. It transfers its keys to its successor.
2. Its predecessor points to its successor.
3. Stabilization fixes the ring structure over time.

🔧 7. Stabilization

Since finger tables can become outdated:

• Nodes periodically run stabilization protocols.
• Fix successor/predecessor pointers.
• Update finger table entries.

The slides mention that lookup() always undershoots, meaning lookups may initially find an earlier node, then require successor corrections.

Example

PART 1 — Identifier Space and Where Keys Are Stored

Identifier Space:

Let:

• n = 6 bits
• $2^6 = 64$ possible identifiers
• Node IDs range from 0 to 63

Example active node IDs:

N1, N8, N14, N21, N32, N38, N42, N48, N51, N56

These 10 nodes form the Chord ring.

Example Keys:

Multiple keys can map to the same ID:

Since:

$ID = H(key) \bmod 2^n$,

different strings may hash to the same identifier.

Example:

H("user123") mod 64 = 30
H("session-token-abc") mod 64 = 30

Both keys → ID 30 → stored at N32 in our ring.

Rule for Storing Keys:

A key is stored at the first node whose ID is ≥ keyID when moving clockwise on the ring.

If nothing is ≥ keyID, we wrap around to N1.

Let's assign each key:

• key1 → 10 → stored at N14
• key2 → 54 → stored at N56
• key3 → 24 → stored at N32
• key4 → 38 → stored at N38
• key5 → 30 → stored at N32
• key6 → 58 → wrap → N1
• key7 → 15 → stored at N21
• key8 → 1 → stored at N1

Final Table:

PART 2 — Constructing the Finger Table (Example: Node N8)

A node with n = 6 bits has 6 finger entries, indexed 0–5.

Finger i points to:

the successor of $(N + 2^i) \bmod 2^n$

Let's compute for N8.

Entry i = 0:

Start = $8 + 2^0 = 9$

First node ≥ 9 = N14

→ FT[0] = N14

Entry i = 1:

Start = $8 + 2^1 = 10$

First node ≥ 10 = N14

→ FT[1] = N14

Entry i = 2:

Start = $8 + 2^2 = 12$

First node ≥ 12 = N14

→ FT[2] = N14

Entry i = 3:

Start = $8 + 2^3 = 16$

First node ≥ 16 = N21

→ FT[3] = N21

Entry i = 4:

Start = $8 + 2^4 = 24$

First node ≥ 24 = N32

→ FT[4] = N32

Entry i = 5:

Start = $8 + 2^5 = 40$

First node ≥ 40 = N42

→ FT[5] = N42

Final Finger Table of N8:

Why Finger Tables Matter:

Finger entries make exponentially increasing jumps:

1 step → 2 → 4 → 8 → 16 → 32 …

🟦 finger[0] = N14

Meaning:

“If you need to move 1 step forward, the next responsible node is N14.”

This is essentially your successor.

🟩 finger[1] = N14

Meaning:

“If you need to move 2 steps forward, the closest node at or after 10 is N14.”

It’s still the same because there are no nodes between 8 and 14.

🟧 finger[2] = N14

Meaning:

“If you need to move 4 steps forward, go to N14.”

Again no nodes between 8 and 14.

🟨 finger[3] = N21

Meaning:

“For jumps of 8 positions, the responsible node is N21.”

This is the first significantly bigger shortcut.

🟥 finger[4] = N32

Meaning:

“For jumps of 16 positions, the correct next hop is N32.”

This is a mid-range shortcut.

🟪 finger[5] = N42

Meaning:

“For jumps of 32 positions, go to N42.”

This is a large jump.

Thus a lookup takes O(log N) messages instead of walking around the whole ring.

PART 3 — Lookup Example

Find successor(24) starting from N8:

We know beforehand that successor(24) = N32, but let's see how Chord finds it.

Step 1 — Check the simple case:

Is 24 in the interval (8, 14] ?

Values in that interval: 9–14.

24 is not in that range.

So we must use the finger table.

Step 2 — closest_preceding_finger(24):

From N8's finger entries:

• N14 (14)
• N14 (14)
• N14 (14)
• N21 (21) ← best candidate ($<24$, largest)
• N32 (32)
• N42 (42)

Largest ID $< 24$ is 21, so:

→ closest_preceding_finger = N21

N8 forwards the lookup to N21.

Step 3 — N21 Processes the Lookup:

Check if 24 ∈ (21, successor(N21)]

Is 24 in the interval (21, 32] ?

successor(N21) = N32

Interval = 22–32

24 ∈ this range → match!

Thus:

successor(24) = N32

Lookup is finished.

Final Lookup Path

N8  →  N21  →  N32

Instead of the longer hop-by-hop path:

N8 → N14 → N21 → N32

This is why Chord achieves O(log N) performance.

PART 4 — Node Join Example (N26 Joins the Chord Ring)

When a new node enters a Chord DHT, the system must update pointers and migrate keys so that the ring remains consistent. Chord's mechanisms ensure that everything happens efficiently and automatically, even if the joining node only knows one other random node.

PART 4.1 — Goal:

A new node N26 joins the system.

Correct position in the ring:

… N21 → N26 → N32 …

But we will analyze two cases:

1. Simple version: N26 already knows N21
2. Realistic version: N26 knows only N14 (not its actual predecessor)

The second version demonstrates the full Chord lookup mechanism.

PART 4 — SIMPLE VERSION (N26 knows N21)

Step 1 — N26 contacts N21:

Chord requires a joining node to know at least one node.

Assume N26 knows N21.

N26 → JOIN → N21

Step 2 — N21 determines N26's successor:

N21 runs:

successor(26)

Check if 26 is in the interval:

(21, 32]

Since 26 falls in that range:

✔ successor(26) = N32

Step 3 — Initial pointer setup:

N26 now sets:

• N26.successor = N32
• N26.predecessor = N21

Temporary chain:

N21 → N26 → N32

But N21 still thinks its successor is N32.

This will be fixed by stabilization.

Step 4 — N32 transfers keys to N26:

N26 is responsible for keys in:

(predecessor(N26), N26] = (21, 26]

Keys in this range:

• K24 → 24

So N32 transfers K24 to N26.

After migration:

• N26 stores: K24
• N32 stores: K30, K38, … (anything ≥27)

Step 5 — Stabilization begins:

Nodes periodically run stabilize().

N21 runs stabilization and identifies N26 as its true successor.

Step 6 — Stabilization fixes pointers:

N21 performs:

x = successor.predecessor
x = N32.predecessor = N26

Since:

26 ∈ (21, 32]

N21 updates:

N21.successor = N26

The ring is updated.

Final State (after stabilization):

Successor pointers:

• N21 → N26
• N26 → N32
• N32 → N38

Predecessor pointers:

• N26 ← N21
• N32 ← N26

Keys:

• N26 stores: K24
• N32 stores: K30, …

N26 is now fully integrated.

PART 4 — REALISTIC VERSION: N26 Knows Only N14

This version demonstrates the full power of Chord's logarithmic lookup.

Setup:

Identifier space: 0–63 (6-bit)

Active nodes:

N1, N8, N14, N21, N32, N38, N42, N48, N51, N56

Correct position of N26:

… N21 → N26 → N32 …

But N26 only knows N14.

PART A — Step 1: N26 asks N14 to locate successor(26):

N26 sends:

find_successor(26)

to N14.

N14 now performs a Chord lookup for ID = 26.

PART B — Step 2: N14 starts the lookup:

First, N14 checks the simple case:

Is 26 in:

(14, successor(N14)=21] ?

14 < 26 ≤ 21 ?

→ NO

So N14 cannot determine the successor directly.

It must use its finger table.

A typical finger table for N14 contains entries like:

FT[0] = N21
FT[1] = N21
FT[*] eventually points to N32, N38, …

Now N14 finds the:

closest_preceding_finger(26)

Candidates < 26:

• N21 (21)

This is the closest ID to 26 without passing it.

Thus N14 forwards the lookup to:

→ N21

PART C — Step 3: N21 completes the lookup:

N21 receives the lookup request for ID 26.

N21 checks:

Is 26 in (21, successor(N21)=32] ?

21 < 26 ≤ 32 ?

→ YES ✔

Therefore:

successor(26) = N32

N21 responds to N14, which forwards the answer to N26.

PART D — Step 4: N26 joins using N32:

N26 now knows:

• Its successor: N32
• Its predecessor: Initially unknown (will be set via stabilization)

N26 sets:

N26.successor = N32

N26 notifies N32 of its presence.

PART E — Step 5: Key migration:

N26 is responsible for keys in the range:

(predecessor(N26), N26] = (21, 26]

Since N32 was previously responsible for keys ≥ 22 (up to 32), N32 transfers:

• K24 (ID = 24) → to N26

After migration:

• N26 stores: K24
• N32 stores: K30, K38, … (keys with ID ≥ 27)

PART F — Step 6: Stabilization:

N32's stabilization:

N32 periodically runs stabilize():

1. N32 asks its successor (N38) for its predecessor.
2. If that predecessor is between N32 and N38, N32 updates its successor.
3. N32 notifies its successor (N38) about N32's existence.

But more importantly, N26 also runs stabilization:

N26's stabilization:

1. N26 asks N32: "Who is your predecessor?"
2. N32 responds: Initially, N32's predecessor might be N21 (before N26 joined).
3. N26 checks: Is N21 between N26 and N32? No, because 21 < 26.
4. However, N26 also notifies N32: "I am N26, and I think you are my successor."
5. N32 receives this notification and checks: Is N26 between N32's predecessor and N32?
   • If N32's predecessor was N21, then: 21 < 26 < 32 → YES
   • N32 updates: N32.predecessor = N26

N21's stabilization:

1. N21 asks its successor (initially N32) for its predecessor.
2. N32 responds: "My predecessor is N26."
3. N21 checks: Is N26 between N21 and N32?
   • 21 < 26 < 32 → YES
4. N21 updates: N21.successor = N26
5. N21 notifies N26: "I am N21, and I think you are my successor."
6. N26 checks: Is N21 between N26's predecessor and N26?
   • If N26's predecessor is not set yet, or if N21 is closer, N26 updates: N26.predecessor = N21

Final State (Realistic Version):

After stabilization completes:

Successor pointers:

• N21 → N26
• N26 → N32
• N32 → N38

Predecessor pointers:

• N21 ← N8 (or previous node)
• N26 ← N21
• N32 ← N26

Keys:

• N26 stores: K24
• N32 stores: K30, K38, …

Finger tables:

All nodes eventually update their finger tables to include shortcuts to N26 where appropriate.

Summary

• ✅ Chord distributes keys using consistent hashing.
• ✅ Each key is stored at the first node >= keyID.
• ✅ Finger tables let nodes jump exponentially around the ring.
• ✅ Lookups become fast: O(log N).
• ✅ Even with node churn, Chord remains scalable and fault-tolerant.

Chord is a powerful protocol that enables efficient distributed storage and retrieval in peer-to-peer systems, making it ideal for applications like distributed file systems, content delivery networks, and decentralized applications.