Search and Replication in Unstructured Peer-to-Peer systems

Problems

Peer-to-Peer systems like Gnutella use a flooding algorithm to resolve
queries--this mechanism induces a lot of traffic on the links and does not
scale. This paper explores different alternatives to Gnutella's query 
algorithm. It also discuess data replication strategies that might help
in improved search performance.

Strengths and New Ideas

(1) They propose a random k-walker algorithm that reduces the load generated
by Gnutella's flooding algorithm by a order of magnitude of two in most cases
while resolving the queries almost as fast as Gnutella.

(2) The paper discusses the expanding-ring algorithm which is TTL based and show
that this too has the inherent flooding problem prevalent in Gnutella's algorithm. 

(3) They discuss the walker strategy at a conceptual level in a fair amount of detail.
A walker forwards the query to a randomly chosen node until the object
is found. While this approach reduces message overhead greatly, it results in a 
significant delay in returning results. They then modify the approach where instead
of one, multiple walkers are deployed. This improves the search time significantly
while still keeping message overhead under control. Thus they show that the random
walk is a much more scalable approach than the flooding method.

(4) The paper also mentions the characteristics that a scalable search method should
have, namely-- 1.they should minimize message duplication and 2. granularity of coverage 
should be small(each forwarded message should not result in a significant increase
in the number of nodes visited).

(5) They briefly mention how replication of data along the path or at randomly chosen
nodes results in performance benefits in the entire network.

Weaknesses and Extensions

(1) The paper only succeeds at a conceptual level. It introduces good concepts but 
does not delve deep into them. A more detailed and thorough discussion and analysis
of the random walk search method would have been highly beneficial. 

(2) Anonymity: The random walk algorithm reports back to the requesting node at certain intervals during
the search. We do not know whether anonymity is maintained if such a method is used.
Anonymity is a major characteristic of a peer to peer system such as Gnutella and since
the discussion of the random walk algorith is so brief we do not know whether it is maintained.

(3) Poor discussion of Data Replication stratgies: While data replication is a part of the title
of the paper, the authors have written only a few lines about it. They mention that data replication
along the search path or at random nodes in the network results outperform owner-replication. However,
data replication has a space cost associated with it. The space cost has been totally neglected
in the discussion.