Chord Protocol: Mermaid Flowchart Diagram

About Source

Chord is a scalable distributed lookup protocol that maps keys to responsible nodes in an N-node ring using consistent hashing, guaranteeing that any key can be resolved in O(log N) hops by each node maintaining a routing table (finger table) of only O(log N) entries.

Chord assigns both nodes and keys an m-bit identifier (typically m = 160 using SHA-1). Nodes are arranged in a logical ring ordered by their identifiers. Each key is stored on the first node whose identifier is greater than or equal to the key's hash — called the key's successor.

Finger Table: Each node n maintains m finger table entries. The i-th finger of node n is the first node that succeeds n + 2^(i−1) in the ring. This table allows each routing step to skip roughly half the remaining arc, converging in O(log N) hops rather than the O(N) hops of a simple predecessor/successor chain.

Lookup: To find the node responsible for key k, a node checks its finger table for the largest predecessor of k and forwards the query there. The receiving node repeats the process until a node's successor owns k.

Stabilization: Chord uses a periodic stabilization protocol to maintain correct successor and predecessor pointers as nodes join and leave. A joining node locates its successor, copies the relevant key range, and notifies its neighbors. The fix_fingers routine repairs stale finger table entries in the background.

Replication and Failure: Chord itself is a lookup layer; replication is handled at the application level by storing keys on the successor list (the next r nodes in the ring). If a node fails, its successor takes over its key range. See Distributed Hash Table for the general DHT model, and Gossip Protocol for how membership changes propagate efficiently across the ring.

Frequently asked questions

Chord is a scalable distributed lookup protocol that maps keys to responsible nodes on a consistent-hashing ring. Each node maintains a compact finger table of O(log N) entries that allow any key to be located in O(log N) network hops, making Chord efficient and decentralised with no central directory.

The i-th entry in node `n`'s finger table points to the first node that succeeds `n + 2^(i−1)` in the identifier ring. When looking up a key `k`, the node finds the largest finger table entry that precedes `k` and forwards the request there, halving the remaining arc at each hop and converging in O(log N) steps.

Chord is a good fit when you need a theoretically clean, decentralised lookup substrate for a peer-to-peer application. It is well-suited to academic prototypes and systems where you want provable O(log N) routing with a minimal routing table. For production workloads Kademlia (used by BitTorrent and IPFS) is more common due to its resilience to concurrent churn.

The stabilisation protocol is eventually consistent, meaning stale finger table entries can temporarily route lookups via longer paths. High churn rates (many simultaneous joins and departures) can cause lookup failures before stabilisation catches up. Applications must implement their own replication strategy on top of Chord, since the protocol itself only provides a lookup primitive.

mermaid

flowchart TD
    subgraph ChordRing ["Chord Ring — m=6 bits, identifier space 0–63"]
        N0["Node 0"]
        N8["Node 8"]
        N15["Node 15"]
        N21["Node 21"]
        N32["Node 32"]
        N45["Node 45"]
        N56["Node 56"]
        N0 --> N8 --> N15 --> N21 --> N32 --> N45 --> N56 --> N0
    end

    subgraph FingerTable ["Finger Table for Node 0"]
        FT1["finger[1]: successor(0+1=1) → Node 8"]
        FT2["finger[2]: successor(0+2=2) → Node 8"]
        FT3["finger[3]: successor(0+4=4) → Node 8"]
        FT4["finger[4]: successor(0+8=8) → Node 15"]
        FT5["finger[5]: successor(0+16=16) → Node 21"]
        FT6["finger[6]: successor(0+32=32) → Node 32"]
    end

    subgraph Lookup ["Lookup: find key hash = 43"]
        L1["Query starts at Node 0"] --> L2["finger[6]=Node 32\nlargest predecessor of 43"]
        L2 --> L3["Forward to Node 32"]
        L3 --> L4["Node 32: finger[4] = Node 45\nlargest predecessor of 43"]
        L4 --> L5["Forward to Node 45"]
        L5 --> L6["Node 45 owns range 33–56\n43 is in range — key found!"]
    end

    subgraph Join ["Node Join: New Node 26"]
        J1["New node ID = 26"] --> J2["Contact any node\nfind successor of 26"]
        J2 --> J3["Successor = Node 32\nPredecessor = Node 21"]
        J3 --> J4["Copy keys 22–26 from Node 32"]
        J4 --> J5["Run stabilize to update\nNode 21 predecessor pointer"]
        J5 --> J6["Schedule fix_fingers\nfor background repair"]
    end

    style L6 fill:#d1fae5,stroke:#10b981
    style ChordRing fill:#eff6ff,stroke:#3b82f6