Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications

[paper]

This paper presents Chord, a distributed lookup protocol. (Their routing algorithm was described as "skiplist-like routing" by the previous paper.) They use "consistent hashing" to assign IDs to nodes, in an attempt to load balance key assignments over nodes. One of their goals is scalability: each node should only need to know about a small number of other nodes. Also, they need to handle nodes leaving and entering the network without complete degradation of performance.

Each key has a "successor node", which is the node whose ID is equal to or most closely follows the key's ID. When a node joins the network, keys previously assigned to other nodes now become assigned to n if the new node's ID is closer to theirs. When a node leaves the network, its keys are reassigned to the next closest. Nodes maintain the ID of the next successor as well as a routing table that helps find a node closer to the key during a lookup propagation operation.