6.2.1 Requirements

You are to design and implement Chord505, a simplified Distributed Hash Table based on Chord. You have been provided with a version of DHT simulator and one of the simplest DHT lookup algorithm implementation, the Ring. This way you can concentrate on designing and implementing your protocol rather than framework issues.

A DHT lookup algorithm is the foundation of all structured peer-to-peer systems. It provides support for one operation: given a key, it maps the key onto a node. Your goal is to design a scalable lookup algorithm and implement it in the given simulator.

Your main reference should be chord, which provides a relatively simple lookup algorithm. It has the provable scalable property: A lookup only traverses O(log N) nodes. Your design is suggested to be based on chord.

Even with such a reference, a real DHT implementation could be complicated: The nodes can join and leave simultaneously or fail silently; The network could be partitioned. In general, handling byzantine faults is hard. In this project, you do not have to deal with those ``churning'' effects. In particular, you only have to handle sequential node join and leave. When a node leaves the DHT, it will have the opportunity to notify other relevant nodes about the event.

You can download our implementation of the simulator from here: chord505-0.3.tar.gz or chord505-0.3.zip.

The tarball contains two packages, algorithm and simulator. Your main focus is to implement a Chord505 class that implements the interface algorithm.Protocol. The algorithm.Protocol has following methods:

join

a new node joins the DHT

leave

a node currently in DHT leaves

update

notify events between nodes

stablize

fix broken/inefficient pointers/fingers

lookup

find a node that is closer to the one that is responsible for the given key

Notice that you do not need to implement the actual hash table and insertion operations - these are provided for you in within the simulator already.

There is already a working implementation of a DHT, algorithm.Ring. It is an example of implementing the DHT and using the whole simulator. The algorithm is extremely simple: each node maintains a pointer to its successor in the virtual ring. If the node does not have the responsibility to the key, it will point to its successor for further lookup. The lookup complexity is O(N) in the virtual network. simulator.SimpleTest contains an example of using the Ring implementation and the simulator. The real get and put hash table interfaces are implemented by the class simulator.Node. It will call the underlying lookup protocol to find the correct node and get/put key, value pairs. Please read the doc and the source code for details.

An elegant Chord505 basic implementation do not have to modify the existing source code (much). Subclassing algorithm.Protocol and simulator.TestCase should suffice.

You should have a look at the Chord paper for the full details of the protocol.

The version of the protocol you should implement should be the following:

1. The range covered by a node stretches from its predecessor to itself.
2. The join method should locate the successor node, and transfer the table covering the previous predecessor to itself.
3. The leave method should transfer the table to the successor node, and inform the successor node that its predecessor is now the leaving node's predecessor.
4. The stablize method should do the following:
   • Check that this node is still the predecessor of what it believes is its successor. If not, update the successor pointer.
   • Create the finger table, assuming this node has identifier n, and id.size returns the length of the key in bits.

     for(int i = 0;i<id.size;i++) {
        finger[i] = findSuccessor(n + 2^i)
     }
     

A real implementation of Chord would use a timer to ensure that the stabilization routines are run at regular^6.1 intervals. In the simulation, you should make a call to stablizeAll each time a node joins or leaves the simulation, which will ensure that each node runs its stablize methods.