## Distributed Verification and Hardness of Distributed Approximation

Author: Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, Roger Wattenhofer

Conference: STOC 2011

Journal:

Abstract:

We study the verification problem in distributed networks, stated as follows. Let $H$ be a subgraph of a network $G$ where each vertex of $G$ knows which edges incident on it are in $H$. We would like to verify whether $H$ has some properties, e.g., if it is a tree or if it is connected. We would like to perform this verification in a decentralized fashion via a distributed algorithm. The time complexity of verification is measured as the number of rounds of distributed communication.
In this paper we initiate a systematic study of distributed verification, and give almost tight lower bounds on the running time of distributed verification algorithms for many fundamental problems such as connectivity, spanning connected subgraph, and $s-t$ cut verification. We then show applications of these results in deriving strong unconditional time lower bounds on the hardness of distributed approximation for many classical optimization problems including minimum spanning tree, shortest paths, and minimum cut. Many of these results are the first non-trivial lower bounds for both exact and approximate distributed computation and they resolve previous open questions. Moreover, our unconditional lower bound of approximating minimum spanning tree (MST) subsumes and improves upon the previous hardness of approximation bound of Elkin [STOC 2004] as well as the lower bound for (exact) MST computation of Peleg and Rubinovich [FOCS 1999]. Our result implies that there can be no distributed approximation algorithm for MST that is significantly faster than the current exact algorithm, for any approximation factor.
Our lower bound proofs show an interesting connection between communication complexity and distributed computing which turns out to be useful in establishing the time complexity of exact and approximate distributed computation of many problems.

Update History

## Efficient Distributed Random Walks with Applications

Author: Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan, Prasad Tetali

Conference: PODC 2010

Journal: Journal of the ACM 2013

Abstract:

We  focus on  the problem of performing random walks efficiently in a distributed network. Given bandwidth constraints, the goal is to minimize the number of rounds required to obtain a random walk sample. We first present a fast 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 $\ell$  in $\tilde{O}(\sqrt{\ell D})$  rounds (with high probability) on an undirected  network, where $D$ is the diameter of the network. This improves over the previous best algorithm that ran in $\tilde{O}(\ell^{2/3}D^{1/3})$ rounds (Das Sarma et al., PODC 2009). We further extend our algorithms to efficiently perform $k$ independent random walks in   $\tilde{O}(\sqrt{k\ell D} + k)$ rounds. We then show that there is a fundamental difficulty in improving the dependence on $\ell$ any further by proving a lower bound of $\Omega(\sqrt{\frac{\ell}{\log \ell}} + D)$ under a general model of distributed random walk algorithms. Our random walk algorithms are useful in speeding up distributed algorithms for a variety of 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) network which runs in $\tilde{O}(\sqrt{m}D)$ rounds (with high probability; here $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.

Update History

Mar 03, 2009 (New version posted on ArXiv)
Nov 06, 2009 (Link to arXiv posted)
Feb 18, 2010 (New version posted)
Feb 18, 2013 (Journal version posted)

## Fast Distributed Random Walks (PODC’09)

Authors: Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan

Journal: Journal of the ACM 2013

Conference: PODC 2009: 28th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computin[wiki]

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 paper, we focus on the problem of performing random walks efficiently in a distributed network. Given bandwidth constraints, the goal is to minimize the number of rounds required to obtain a random walk sample.

All previous algorithms that compute a random walk sample of length $\ell$ as a subroutine always do so naively, i.e., in $O(\ell)$ rounds. The main contribution of this paper is a fast distributed
algorithm for performing random walks. We show that  a random walk sample of length $\ell$ can be computed in $\tilde{O}(\ell^{2/3}D^{1/3})$ rounds on an undirected unweighted network, where $D$ is the diameter of the network. ($\tilde{O}$ hides $\frac{log{n}}{\delta}$ factors where $n$ is the number of nodes in the network and $\delta$ is the minimum degree.) For small diameter graphs, this is a significant improvement over the naive $O(\ell)$ bound. We also show that our algorithm  can be applied to speedup the more general Metropolis-Hastings sampling.

We extend our algorithms to perform a large number, $k$, of random walks efficiently. We show how $k$ destinations can be sampled in $\tilde{O}((k\ell)^{2/3}D^{1/3})$ rounds if $k\leq \ell^2$ and $\tilde{O}((k\ell)^{1/2})$ rounds otherwise. We  also present faster algorithms for performing random walks of length larger than (or equal to) the mixing time of the underlying graph. Our techniques can be useful in speeding up distributed algorithms for a variety of applications that use random walks as a subroutine.

Keywords: Random walks, Random sampling, Distributed algorithm, Metropolis-Hastings sampling.

Update History

[v1] May 31, 2009 (Conference version)
[v2] Feb 18, 2013 (Journal version posted)

## Detecting and cleaning intruders in sensor networks (NCSEC’04)

Author: Poona Yospanya, Bundit Lekhanukit, Danupon Nanongkai, Jittat Fakcharoenphol
(Author names are NOT in an alphabetical order.)

Journal:

Conference: NCSEC 2004: The 8th National Computer Science and Engineering Conference [link]

Abstract:

We view the problem of detecting and cleaning intrud-
ers in sensor networks using mobile agents as a ver-
sion of the graph searching problem. The goal is to
minimize the number of agents running at the same
time. Three scenarios are considered, each differs in
the relative power of the agents and the intruders. Our
main idea is to use breadth-ﬁrst-search (BFS) trees to
organize the search. In the case where the intruder
is most powerful, we search the graph by levels of
the nodes on the BFS tree. However, in the second
case where the network is conﬁgurable, the number of
agents could be improved signiﬁcantly if a good sub-
graph can be found. This motivates us to deﬁne the
Minimum Search Number Spanning Tree problem, of
which we also prove its hardness. We however show
that one can still use a BFS tree to get a good result. In
the last scenario where the intruder has no information
on the status of the agents, random walks are used. In
each case, we prove upper bounds on the number of
agents and provide experiment results.

We view the problem of detecting and cleaning intruders in sensor networks using mobile agents as a version of the graph searching problem. The goal is to minimize the number of agents running at the same time. Three scenarios are considered, each differs in the relative power of the agents and the intruders. Our main idea is to use breadth-ﬁrst-search (BFS) trees to organize the search. In the case where the intruder is most powerful, we search the graph by levels of the nodes on the BFS tree. However, in the second case where the network is conﬁgurable, the number of agents could be improved signiﬁcantly if a good subgraph can be found. This motivates us to deﬁne the Minimum Search Number Spanning Tree problem, of which we also prove its hardness. We however show that one can still use a BFS tree to get a good result. In the last scenario where the intruder has no information on the status of the agents, random walks are used. In each case, we prove upper bounds on the number of agents and provide experiment results.

Update history:

[v1] October 2004