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

The paper discusses Chord, a network protocol that looks up nodes in a distributed network. Given a key, the Chord algorithm searches for the node storing the key's value. A good quality of Chord is that it can quickly adapt to nodes that enter and leave the system. The lookup service will still work even if the nodes change frequently.
Chord uses a distributed hash function in assigning specific hash keys to nodes, and each node maintains a small routing table. In this way, the keys are balanced among the nodes and key assignments do not change much when nodes join or leave the system. Because Chord is distributed and all nodes are equal to each other, it is robust and is fit for supporting loosely-organized peer-to-peer applications. Chord is scalable, and the cost of Chord only grows in proportion to the log of the number of nodes, which makes large systems feasible. Keys that are looked up using Chord can also be structured in any way -- making the naming of keys flexible. Among its potential uses are cooperative mirroring, time-shared storage, distibuted indices, and large scale combinatorial searches.

There are many applications that can use Chord. Cooperative mirroring can allow developers to balance the load of the distributions they want published. Time-shared storage allows for a computer's data to be distributed and available to the network even if that computer is not connected to the network. When a computer joins the network, it can offer to distribute other computer's data when it is connected, so that other computers will also distribute its data when it is offline. Distributed indices allow for keyword searches in a database, as in P2P file transfer clients. Large scale combinatorial searches works by having keys as the candidate solutions, and these keys in turn point to the node that should evaluate if it is a solution or not.

The Chord algorithm is different from other peer-to-peer lookup protocols because of its simplicity, provable correctness, and provable performance. During queries, the node which initiates the lookup will search its finger table for the closest finger f preceding the key. Node n will send a request to f, asking for the closest entry preceding k and f will send back the result to n. This process will continue and results to n learning about nodes that bring it closer and closer to its target ID/ destination.

In general, the system needs to stabilize and continuously do the following in order to ensure that lookups yield correct results: (1) initialize the predecessor and fingers; (2) update the fingers and predecessors of existing nodes to reflect the change in network topology caused by the addition of n; and (3) copy all keys for which node n has become their successor to n. (http://www.inf.ed.ac.uk/teaching/courses/ip/chord-desc.html)

The authors of the paper continued by discussing in detail tests that were performed to evaluate how Chord fares in aspects of load balance, number of nodes traversed during lookup, simulateous node failures, performance of lookups when the network nodes are stabilizing, and lookup latency on an internet prototype. The test show satisfactory results, and assert that the Chord protocol is scalable.

Future work for Chord include the recommendation to create a mechanism for healing partitioned rings during stabilization. This mechanism can also help identify malicious or buggy Chord participants. Another recommendation is to change the distances of fingers from powers of 2 to powers of 1 + 1/d in order to decrease the number of messages per lookup from log N to log(base 1+d)N hops. However, this will increase the needed number of nodes to O(dlogN). Lookup latency may also be improved by server selection, wherein lookups are forwarded to nodes with the lowest delay.


References:
Stoica,I. et. al. 2001. Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications. MIT Laboratory for Computer Science
http://en.wikipedia.org/wiki/Chord_(peer-to-peer)
http://www.inf.ed.ac.uk/teaching/courses/ip/chord-desc.html