Chord Paper Review

This paper reports on Chord, which is a decentralized protocol for key look-up in a peer-to-peer system. The authors introduces Chord model as a potential underlying framework in peer-to-peer system which can be used by other applications such as distributed file-sharing applications , etc. Then, they provide proofs on its efficient behaviour under different challenging conditions, like the concurrent node failures state.

The work use consistent hashing to map the keys into nodes on a Chord "ring", however, they extend it in way that nodes do not nee to know about every other node, rather they should know a small amount of routing information about other nodes. The routing tables designated for each node makes Chord capable to halve the distance of the current node to the destination node (containing the object) after each routing step. This will guarantee that any lookup query will at traverse at most O(lg_n) nodes in the Chord ring before arriving at the destination. One other interesting contribution of the paper is that Chord handles failures of nodes by having each node maintaining a successor list of size $r$, so that each node can move into its next successor, in the case that the current successor fails to respond. Authors give theoretically strong results on the impact of choosing $r$ on the fault-tolerance of the lookup system.

While studying the impact of latency on the performance of the lookup system, authors model of the world is assumed to an Euclidean 3-d space, which is far from reality at least for now. Different Routing policies and poor connectivity of some regions in the world, make the result obtained in the paper (based on their simplistic model) less true for real-world experiments. I think a good alternative is to use Internet trace-driven latency for experiments rather than assuming Euclidean coordinates for hosts.
Received on Mon Nov 07 2005 - 10:41:48 EST