In this paper Chawathe et al describe a scalable method to perform searches in a p2p network. Previous methods use flooding to search for content and thereby generate a large load on the network. The paper introduces four new concepts (dynamic topology adaptation, active flow control, one-hop replication, and a search protocol) that achieve their main performance increase by doing "informed" random walks. The advantages and differences to other methods are very well described. Simulations are performed to compare the performance to other approaches and a prototype was implemented to test their method in the real world. Simulations showed a performance increase of three to five orders of magnitude. In the beginning of the paper a short discussion took place to inform the reader why an alternative search method (distributed hash tables) is not as suitable for searching as widely believed.

The paper was conceived by most of us as very well written. The argumentation was clear, precise, and easy to understand even with limited background knowledge. Graphs were used to display important simulation results but unfortunately some were overloaded. At the beginning of the discussion almost all of the discussion participants would have rated the paper as being in the top 5.

During the discussion the question of how the quality of the search result is influenced was raised. It was pointed out that in general p2p file sharing programs benefit from receiving as many as possible results to download concurrently from multiple resources. Therefore receiving fewer results would not be of advantage. It was also suspected that long search paths could negatively influence the search time and the reliability of the search.

At the end of the discussion the paper was still rated very well. However the conclusion was that the proposed search method would perform even better if it would be combined with for example "limited" flooding. That would improve some of the disadvantages while keeping the generated traffic low. All in all a very good paper.

Christoph Jechlitschek