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

I. Stoica, R. Morris, D. Karger, F. Kaashoek, H. Balakrishnan, "Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications," ACM SIGCOMM Conference, 2001.

This paper talked about Chord, a distributed lookup protocol that tries to address the lookup problem (finding the node that has a particular key mapped to it) in a simple and provably correct manner.


Chord Protocol Design

• Consistent Hashing: The hash function assigns each node and key  an m-bit identifier using SHA-1 by hashing the node's IP address and key value respectively. An interesting issue that the authors analyzed here was what if any malicious node keep on producing keys that hash to a particular node thereby overloading it? However, the authors claim that producing such a set of keys that collide under SHA-1 is equivalent to inverting or decrypting the SHA-1 function and is considered NP-hard.
• Scalable Key Location: Every node maintains something which is called the finger table. The ith entry in the table at node n corresponds to the tuple < n+2^(i-1), successor(n+2^(i-1)), IP Address>. Now whenever a query to a particular key k is made, the node searches for i and j in the finger table such that n+2^(i-1) <= k < n+2^(j-1) and routes it to successor (n+2^(i-1)). The requests are made in this iterative fashion until the node with the key is found. The authors highlighted that this takes O(log N) lookups in the worst case.
• Node Joins: To ensure concurrent node joins, chord makes 2 invariants, each node's successor is correctly maintained and for every key k, the node successor (k) is responsible for k. These invariants help in ensuring success of each node join operating. The new node must update its successor with the help of any node that it knows of and fetch its key responsibilities. This takes O(log N*log N) messages.
• Stabilization: This helps in stabilizing the system in case of frequent disconnects. It works to update predecessor entries, periodically verify a node's immediate successor and periodically refreshes finger table entries. An interesting result was that as long as updating fingers take less time than it takes the network to double its size, lookups will continue to be O(log N) hops.

Finally, the authors evaluated the protocol on an iterative simulator and analyzed numbers for load balancing, path lengths, system behavior in terms of node failures and lookups during stabilization phases. The results matched the design expectations and were encouraging. Apart from a slight mismatch in graph numberings at quite some places, the graphs were pretty easy to read.


Comments

This paper definitely deserves to be one of the highly cited papers in computer science. It was well written, presented a novel solution, the protocol was very simple and yet had strong mathematical backing to prove its correctness. However, there were few issues that Chord was unable to tackle:

1. Anonymity: Chord doesn't provide anonymity. Its lookup operation runs in predictable time and always results in success or definitive failure.
2. Network Locality: The node IDs are assigned randomly. This has the disadvantage of chord being unable to utilize network locality in its design.
3. May result in temporary failures: In case of node joins, it may occur that nodes in an affected region may have incorrect successor pointers, or keys may not have migrated to newly joined nodes resulting in lookup-fail temporarily till the stabilization protocol fixes it.