PAPER 5 Niranjan Sivakumar

Search and Replication in Unstructured Peer-to-Peer Networks
Beehive:  O(1) Lookup Performance for Power-Law Query Distributions in 
Peer-to-Peer Overlays

The paper regarding search and replication in unstructured p2p networks 
considers the idea of improving performance in generally unstructured 
networks such as Gnutella.  Through a series of simulations they illustrate 
the drawbacks of two popular search methods, flooding and expanding ring, and 
provide some analysis of two variants of a random walk search.  The random 
walk algorithm that would check back to the originating node to terminate 
generally performed better than the other approaches in their tests.  They 
also considered replication, and considered two somewhat intuitive 
approaches, uniform and proportional replication, as well as square-root 
replication.  Although they admit that implementing a square-root replication 
method is not trivial, their tests show that this method may be more "fair" 
and a better solution than the others.

Beehive does not do away with the idea of structured p2p networks, and instead 
seeks to exploit the underlying mechanism of a ring-based architecture like 
that of Pastry to implement a relatively simple method of proactive 
replication that could lead to sub-one hop routing.  An analytical solution 
that is provided in the paper allows for designers to tune the system for 
some desired level of performance.  The system uses prefix-matching and the 
idea that the number of hops can be reduced by progressively replicating 
files at nodes that share one less prefix than the current node that is 
holding the object.  However, Beehive does not require a great deal of 
coordination between nodes when making replication decisions, even as objects 
fan out.  The system also has a mechanism to evaluate the popularity of a 
node in order to determine what level an object should be replicated out to.

One of the drawbacks in the Search and Replication paper seems to be their 
very premise as to why they are focusing on unstructured networks instead of 
structured networks.  One of their main reasons seems to simply be that few 
currently available networks are structured.  Furthermore, while their 
theoretical results are interesting, they themselves indicate that it is 
quite basic and the take away from the paper seems to be generally applicable 
"good ideas" for selecting or developing search and replication algorithms.  
They also did not really provide an exhaustive analysis of algorithms, as 
they just selected a small sample to test.  

One issue that I noted in the Beehive paper is related to incentives for 
maintaining cached copies of objects.  Although there is an alternate to hold 
links instead of an object itself, if the goal is to avoid a "slashdot 
effect" as is stated in the paper, then it seems that maintaining actual 
copies would be quite important.  Since the system seems to be pushing copies 
on to nodes that may not actually have any relationship with the content, 
this could create some issues with getting willing participants in such a 
network.

