The Convergence-Guaranteed Random Walk
and Its Applications in Peer-to-Peer Networks
Ming Zhong, Kai Shen, and Joel Seiferas
Department of Computer Science, University of Rochester
Network structure construction and global state maintenance are expensive in
large-scale, dynamic peer-to-peer (p2p) networks. With inherent topology
independence and low state maintenance overhead, random walk is an excellent
tool in such network environments. However, the current uses are limited to
unguided or heuristic random walks with no guarantee on their converged node
visitation probability distribution. Such a convergence guarantee is
essential for strong analytical properties and high performance of many p2p
applications. In this paper, we investigate an approach for random walks to
converge to application-desired node visitation probability distributions
while only requiring information about direct neighbors of each peer. Our
approach is guided by the Metropolis-Hastings algorithm for Monte Carlo
Markov Chain sampling. Our contributions are three-fold. First, we analyze
the convergence time of the random walk node visitation probability
distribution on common p2p network topologies. Second, we analyze the fault
tolerance of our random walks in dynamic networks with potential walker
losses. Third, we present the effectiveness of random walks in assisting
three realistic network applications: random membership subset management,
search, and load balancing. Both search and load balancing desire random
walks with biased node visitation distributions to achieve
application-specific goals. Our analysis, simulations, and Internet
experiment demonstrate the advantage of our random walks compared with
alternative topology-independent index-free approaches.