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)