Looking Up Data in P2P Systems

Summary:

This paper gives a survey of recent DHT-based solutions to look-up problem proposed for P2p systems. Scalable and robust look-up mechanisms is a major challenge/requirement for large scale P2P systems which needs to be addressed.

Purely structured (each node has a well defined information about other nodes) lookup or symmetric (nodes are of equal importance from the point of view of lookup) lookup mechanisms are either too sensitive to failures or can't give guarantees and are inefficient. The more recent proposals (CAN, Chord, Kademlia, Pastry and Tapestry) are all structured and symmetric enabling them to be resilient and offer guarantees at the same time.

Interestingly, DHT is the key technology that has enabled all these new systems. When an entity wants to access a file (for example), it needs to calculate the hash key and call the lookup(key) function. Every file is stored at the node with the "closest" ID (usually chosen randomly) to the key (the definition of closeness depends on the scheme).

The difference among the proposed DHT based lookup services is mainly weather they route in a single dimension or more and the used data structures. For example Chord routes in a single dimension and uses a skiplist like data structure to store the potential next hops at every node achieving O(logN) expected similar to other 1-dimensional routing schemes.

Critique:

This paper gives a very educational and concrete overview of the proposed DHT-based lookup algorithms and further gives some insight into the trade-offs and choices of design parameters (specially in the discussion section). It would have been interesting if there were additional simulation or experimentation results comparing these mechanisms in an actual setting beyond the big O notation comparisons; even though this level of comparison is probably not expected from a survey paper. Great paper to be kept in the syllabus indeed.