### Distributed Random WalksDistributed Random Walks

Access Restriction
Subscribed

 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

Source: ACM Digital Library