# Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications - Stanford, 2001

• [Paper] [Mirror]

• Provides O(log(N)) lookups (N = # nodes)
• Fully decentralized
• An interesting application I hadn’t though of is “Large Scale Combinatorial Search”

“In this case keys are candidate solutions to the problem (such as cryptographic keys); Chord maps these keys to the machines responsible for testing them as solutions.”

• Uses consistent hashing for the ring
• No v-nodes
• Nodes are assigned a key based on a hash of their IP
• This makes it difficult for an attacker to choose their place on the ring
• This also makes it hard to rebalance the ring
• Though, nodes can come and go and will resume their previous location
• Finger Table
• This is what makes Chord scale
• Each node has a table of O(log(N)) entries
• Each row in the table hold the location of successor[n + 2^(i-1)]
• For example, the first three rows hold the 1st, 2nd and 4th successor of the node
• We use the table to find a node close to the node that contains a requested key
• To facilitate joining and leaving, each node has a pointer to it’s predecessor on the ring
• To deal with failures, each node has a list of it’s k nearest successors
• This optimized search while the ring stabilizes
• Future Work
• They discuss some of the issues with partitioned rings and provide some ideas for how to detect partitions (i.e. have each node query for itself)