We quantify the effectiveness of random

walks for searching and construction of unstructured

peer-to-peer (P2P) networks. For searching, we argue

that random walks achieve improvement over ï¬‚ooding

in the case of clustered overlay topologies and in the

case of re-issuing the same request several times. For

construction, we argue that an expander can be maintained

dynamically with constant operations per addition. The

key technical ingredient of our 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 (if the second

eigenvalue of the transition matrix is bounded away from

1, which translates to good expansion of the network;

such connectivity is desired, and believed to hold, in every

reasonable network and network model). This property has

been previously used in complexity theory for construction

of pseudorandom number generators. We reveal another

facet of this theory and translate savings in random bits

to savings in processing overhead.

www.cc.gatech.edu