NDLI: Distributed Random Walks

Content Provider	ACM Digital Library
Author	Das Sarma, Atish Nanongkai, Danupon Pandurangan, Gopal Tetali, Prasad
Copyright Year	2013
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.
Starting Page	1
Ending Page	31
Page Count	31
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/2432622.2432624
Journal	Journal of the ACM (JACM)
Volume Number	60
Issue Number	1
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-02-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Random walks Decentralized computation Distributed algorithms Mixing time Random sampling Random spanning tree
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Efficient distributed random walks with applications

Continuous sampling from distributed streams

An optimal minimum spanning tree algorithm

Solving convex programs by random walks

Optimal maintenance of a spanning tree

A random polynomial-time algorithm for approximating the volume of convex bodies

Estimating PageRank on graph streams

The complexity of restricted spanning tree problems

A randomized linear-time algorithm to find minimum spanning trees

Distributed Random Walks

Similar Documents

Efficient distributed random walks with applications

Continuous sampling from distributed streams

An optimal minimum spanning tree algorithm

Solving convex programs by random walks

Optimal maintenance of a spanning tree

A random polynomial-time algorithm for approximating the volume of convex bodies

Estimating PageRank on graph streams

The complexity of restricted spanning tree problems

A randomized linear-time algorithm to find minimum spanning trees

Distributed Random Walks