Week 1/24-1/28

¡°Search and Replication in Unstructured Peer-to-Peer Networks¡±

	Gnutella¡¯s search method through TTL-based flooding introduces many duplicate messages, especially in high connectivity networks. As a result, it is frequently not easy to choose an appropriate TTL. This paper introduces the notion of random walker. A walker message is randomly sent to a neighbor from the source and any other subsequent nodes. This greatly reduces the message overhead. In order to reduce search delay, multiple walkers should be used. Random Walker scheme demonstrates that it can message overhead and, yet, still locate the query data in a timely manner.

	In order to terminate walkers, each walker periodically checks with the requesting node to decide whether it should keep searching. Nodes can also keep states so the different walkers for the same query can be sent to different neighbors. However, the paper fails to address the message and node overhead of the above statements. A walker with hop of 7 would have incurred an extra 28 messages (1+2+3+4+5+6+7) from each node back to the source node. The resources required to keep state of each walker at individual nodes could also be too expensive.

	In scalable search algorithms, attention should be paid to the following properties: adaptive termination, minimizing message duplication, and small granularity of coverage. I will keep these three properties in mind should there be any search algorithms in my project.