Access Restriction

Author Das Sarma, Atish ♦ Nanongkai, Danupon ♦ Pandurangan, Gopal ♦ Tetali, Prasad
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2013
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Random walks ♦ Decentralized computation ♦ Distributed algorithms ♦ Mixing time ♦ Random sampling ♦ Random spanning tree
Abstract Performing random walks in networks is a fundamental primitive that has found applications in many areas of computer science, including distributed computing. In this article, we focus on the problem of sampling random walks efficiently in a distributed network and its applications. Given bandwidth constraints, the goal is to minimize the number of rounds required to obtain random walk samples. All previous algorithms that compute a random walk sample of length ℓ as a subroutine always do so naively, that is, in $\textit{O}(ℓ)$ rounds. The main contribution of this article is a fast distributed algorithm for performing random walks. We present a sublinear time distributed algorithm for performing random walks whose time complexity is sublinear in the length of the walk. Our algorithm performs a random walk of length ℓ in $\textit{Õ}(√ℓ\textit{D})$ rounds $(\textit{Õ}$ hides polylog $\textit{n}$ factors where $\textit{n}$ is the number of nodes in the network) with high probability on an undirected network, where $\textit{D}$ is the diameter of the network. For small diameter graphs, this is a significant improvement over the naive $\textit{O}(ℓ)$ bound. Furthermore, our algorithm is optimal within a poly-logarithmic factor as there exists a matching lower bound [Nanongkai et al. 2011]. We further extend our algorithms to efficiently perform $\textit{k}$ independent random walks in $\textit{Õ}(√\textit{k}ℓ\textit{D}$ + $\textit{k})$ rounds. We also show that our algorithm can be applied to speedup the more general Metropolis-Hastings sampling. Our random-walk algorithms can be used to speed up distributed algorithms in applications that use random walks as a subroutine. We present two main applications. First, we give a fast distributed algorithm for computing a random spanning tree (RST) in an arbitrary (undirected unweighted) network which runs in $\textit{Õ}(√\textit{mD})$ rounds with high probability $(\textit{m}$ is the number of edges). Our second application is a fast decentralized algorithm for estimating mixing time and related parameters of the underlying network. Our algorithm is fully decentralized and can serve as a building block in the design of topologically-aware networks.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2013-02-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 60
Issue Number 1
Page Count 31
Starting Page 1
Ending Page 31

Open content in new tab

   Open content in new tab
Source: ACM Digital Library