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 flooding
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
