Paper #: 5.1.6
Title: Search and Replication in Unstructured Peer-to-Peer Networks

(1) Problems

This paper attempts to analyze a newly proposed query algorithm for searches in peer-to-peer networks, as well as examine the idea of replication as it pertains to increasing system performance. More specifically, it challenges the idea that the current search method employed by Gnutella, flooding, is not scaleable (or at least not nearly as scaleable as their proposed query algorithm).

(2) New Idea and Strengths

The idea of a random walker as a search method is a good one. It¡¯s not much slower of a search, but the load on the system is decreased by 2 orders of magnitude (according to their simulation results). 

(3) Weaknesses and Extensions

This idea doesn¡¯t seem particularly clever, and I am surprised that Gnutella decided against this method after viewing the test results. Although it is slightly slower, performance wise, the scalability is a big problem. Their discussion of replication only talked briefly about the benefits to random or path replication, with no mention of the drawbacks, which are significant- extra storage per node, as well as the increased bandwidth resulting from the extra passing of files.

I do like the idea of a walker algorithm, but perhaps a combination of the walker and the flooding could be interesting. A walker that pauses for a small flooding of queries to all a node¡¯s neighbors on a random basis could prove to be scalable, yet with a better response time / shorter number of hops.