@INPROCEEDINGS{Gkantsidis_04,
    AUTHOR      = {C. Gkantsidis and M. Mihail and A. Saberi},
    TITLE       = {{Random Walks in Peer-to-Peer Networks}},
    BOOKTITLE   = {{Proceedings of IEEE INFOCOM}},
    YEAR        = {2004},
    EDITOR      = {},
    PAGES       = {},
    PUBLISHER   = {},
    VOLUME      = {},
    NUMBER      = {},
    SERIES      = {},
    ADDRESS     = {},
    MONTH       = {},
    NOTE        = {},
    KEY         = {},
    KEYWORDS    = {},
    ISBN        = {},
    URL         = {http://www.ieee-infocom.org/2004/Papers/03_4.PDF},
    ABSTRACT    = {We quantify the effectiveness of random walks for
searching and construction of unstructured peer-to-peer (P2P)
networks. We have identified two cases where the use of random
walks for searching achieves better results than flooding: a) when
the overlay topology is clustered, and b) when a client re-issues
the same query while its horizon does not change much. 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.}, }