Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications
📜 Abstract
A fundamental problem that confronts peer-to-peer applications is to efficiently locate the node that stores a particular data item. This paper presents Chord, a distributed lookup protocol that addresses this problem. Chord provides support for just one operation: given a key, it maps the key onto a node. Data location can be easily implemented on top of Chord by associating a key with each data item, and storing the key/data item pair at the node to which the key maps. Chord adapts efficiently as nodes join and leave the system, and can answer queries even if the system is continuously changing. Results from theoretical analysis, simulations, and experiments show that Chord is scalable, with communication cost and the state maintained by each node scaling logarithmically with the number of Chord nodes.
✨ Summary
Summary
Chord presents a decentralized lookup protocol for dynamic peer-to-peer systems. It maps keys and nodes into a circular identifier space using consistent hashing; a key is assigned to the first node encountered clockwise from that key. This arrangement balances responsibility among nodes and limits the amount of data that must move when nodes join or leave.
To avoid requiring every node to know the complete membership list, Chord augments each node’s immediate successor pointer with a logarithmic-size finger table. Finger entries point to nodes at exponentially increasing distances around the identifier circle. Lookup follows the closest preceding finger toward the target and requires (O(\log N)) messages with high probability, while each node maintains (O(\log N)) routing state. Node joins and departures require approximately (O(\log^2 N)) messages to update routing state in the protocol described by the paper.
Correctness depends primarily on maintaining successor pointers. Finger tables improve performance but may temporarily be stale. A stabilization protocol periodically repairs successor and predecessor relationships and refreshes fingers, allowing the system to tolerate concurrent joins. Successor lists provide additional failure resilience: after node failures, a node can select the first live successor in its list and continue routing while the rest of the overlay repairs itself. The paper also describes how successor lists can support replication at higher layers.
The evaluation combines theoretical analysis, simulation, and an Internet prototype. The experiments show logarithmic growth in lookup path length, approximately half of (\log_2 N) hops on average in the simulated model, and relatively slow growth in measured lookup latency as the number of nodes increases. The experiments also show that virtual nodes substantially improve load balance, at the cost of additional routing state. Under simultaneous failures, lookup failures were close to the fraction of keys whose responsible nodes had failed, suggesting that the overlay itself generally recovered without widespread routing failure. During continuous churn, state inconsistency caused additional failures, with the rate depending on the relationship between node churn and stabilization frequency.
The paper’s main limitations include weak exploitation of network locality, no dedicated mechanism for healing partitioned rings, reliance on assumptions about identifier distribution and hash hardness, and limited protection against malicious participants. Authentication, caching, replication, naming, and application-level data consistency are intentionally left to systems built above Chord.
Influence
Chord became a foundational design for distributed hash tables and structured peer-to-peer overlays. The Cooperative File System used DHash on top of Chord to locate and distribute storage blocks, demonstrating a concrete distributed-storage application of the lookup substrate. (pdos.csail.mit.edu) CoralCDN initially used Chord as its routing layer before replacing it because of requirements involving network-aware clustering, illustrating both the applicability and the limitations of a basic Chord overlay for locality-sensitive content distribution. (usenix.org) Later work on deployed DHTs explicitly analyzed Chord implementations alongside other systems and identified practical problems arising from non-transitive Internet connectivity, extending the paper’s failure and maintenance concerns into real-world deployment. (cs.princeton.edu)