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

Summary:

This paper introduces Chord, a distributed lookup protocol which is designed based on DHT technology. Even though the function this system supports sounds very simple (given a key maps it onto a node) quite a bit of intelligence is required to design a system which can accomplish this task in an efficient, scalable and further resilient fashion.

As mentioned in the survey paper Chord lookup is symmetric and structured meaning nodes are of equal importance while data items can be deterministically mapped to nodes. To achieve this task, Chord uses a variant of consistent hashing which would not require global awareness at every node; Instead proposes usage of a distributed routing table requiring O(logN) state size and O(logN) messages to resolve a query and therefore it is much more scalable.

In simple terms, each node has a finger table which has pointers to other nodes with roughly different power 2 distances in node identifier circle. Every key is stored at the immediate following node ID and therefore with each message we halve the distance to the node responsible for target key. The important operations which need to be further supported are join and leave operations which authors show with high probability will take O(log^2(N)) message to update all the states.

An important requirement for the correctness of this protocol is the the validity of the pointer which each node has to the next node on the identifier circle (successor). These pointers will guarantee that at each step a positive move will be made towards the target and further ensures correctness. For this reason every node periodically runs an stabilization algorithm ensuring the validity of the pointer. The Chord will further a successor list instead of a single pointer to achieve a better performance against simultaneous pointers.

Critique:

Authors test Chord against different pressure scenarios to demonstrate its true characteristics. A special point which was made in the simulation part was that random uniform id assignment will cause too much load variance across nodes and virtual nodes should be used at each node to alleviate this problem and this would increase the finger table size but not too much. I wonder how important is this variance in reality and if it really needs to be accounted for?

Another point of discussion can be weather Chord can tuned for exploiting asymmetric underlying structure meaning not giving as much load to nodes which are less reliable, etc. Chord is definitely a great paper for this class.