This is a survey paper (by the authors of Chord) discussing the various schemes available for lookup. This is a sweet and short paper with a nice flow introducing the problem, discussing the solutions and talking about open issues.
Some of the approaches like a central database and broadcast are obviously out of the window for the scale that is being aimed for p2p systems. But given this is a survey paper, I would have wished the authors gave it a little more credit – these approaches do work in many limited but useful settings. The dismissal of the “superpeer” idea irked me. I think in practice, this approach should work very well and might actually provide better “guarantees” if superpeers were maintained by some commercial entity. To me, the p2p era became a “bubble” mainly because such un-sexy approaches weren’t given much importance (fair enough, you can’t get them published!).
The lookup problem has been addressed using ring-based approaches (Chord) and tree data structures (Pastry, Tapestry and Kademlia). Differences between them include distance functions that are combination of being symmetric and unidirectional, cost of node join/failure operations and topology-aware routing.
This whole space seemed a little disconnected from reality – who really is the customer for such smart and sophisticated lookup schemes? At some point, it comes across as over-optimization and complexity that we can do without. That said, I think there were quite a few positives and overall an interesting area.
I would like this paper to be substituted with some paper that shows a real system based on any of these schemes. If a survey paper is a must, my vote is for “The impact of DHT routing geometry on resilience and proximity” at SIGCOMM 2003.