Looking Up Data in P2P Systems

Summary

This paper outlines the key challenges in distributed, P2P data lookup and compares current solutions.

To motivate the work, this paper lists three reasons P2P systems are attractive:

1. Low barriers to starting and growing the system
2. Allows pooling of resources
3. Robustness and fault-tolerance

Finding data is the central problem in P2P systems because nodes can join, leave, or crash at any time. The lookup mechanism must be both scalable and fault-tolerant. So simple solution such as a centralized database are not applicable because they are not scalable and create single point of failure. Other approaches include broadcasting requests to all nodes as done in the Gnutella and preforming lookups hierarchically as done in DNS. Unfortunately, the broadcast method suffers from a lack of scalability and the hierarchical approach is not robust against failures of top level nodes. DHTs are a method to perform lookups with both both scalability and fault-tolderance.

The paper describes three DHT algorithms in detail: Coord, Pastry and CAN. In general they all have three features:

1. Assigning keys to nodes in a load-balanced way
2. Forwarding a lookup to a closer node as defined by a distance function
3. Building routing tables adaptively

For example, in Coord keys are assigned based on proximity in a ring, forwarding happens using a skiplist of pointers to nodes at specific distances in the ring, and routing tables are updated by periodically checking liveness and updating broken entries from neighbors.

There are several key differences between the DHT algorithms. For example, the chosen distance function is symmetric (d(x, y) = d (y, x)) then a stabilization protocol is not necessary

Thoughts

This paper takes a big picture view of all the work on DHTs and provides concise summaries. The key contribution is the comparison the the different algorithms. I thought the distance function example was quite neat.