International Journal of Advanced Research in Computer Science and Software Engineering (IJARCSSE)
The authors quantify the effectiveness of random walks for searching and construction of unstructured Peer-To-Peer (P2P) networks. For searching, they argue that random walks achieve improvement over loading in the case of clustered overlay topologies and in the case of re-issuing the same request several times. For construction, they argue that an expander can be maintained dynamically with constant operations per addition. The key technical ingredient of their approach is a deep result of stochastic processes indicating that samples taken from consecutive steps of a random walk can achieve statistical properties similar to independent sampling.