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

This paper sparked a lot of research on distributed hashtables and other forms of structured P2P systems by introducing Chord, a simple DHT which provides fast lookups and redundancy while requiring little communication and few neighbors per node. The basic idea of Chord is to identify your data items by hashes and view the space of hashes as a ring. Each node then chooses a random position on the ring and makes pointers to nodes 1, 2, 4, 8, etc identifiers away, or O(log n) pointers. This is enough to be able to find any item in O(log n) time. In addition, with some redundancy, you can replicate items at several nodes and you can have multiple pointers to route around nodes that disconnect.

The most interesting thing about this paper is the solid mathematical grounding for claims about convergence, load balance, etc, and the harsh simulation environment with high churn. Chord is shown to deal gracefully with failures and maintain short paths to most nodes. This is important to motivate the work as really practical, because P2P systems tend to have these harsh environments where most nodes are only in the system for minutes, and very few nodes are in for more than a day or so.

The main criticism I have is that the implementation was only using 10 physical sites and ~200 nodes. Today it would be possible to test such systems at larger scales (1000+ nodes) using services like Amazon Elastic Compute Cloud.