2020

• Mohamad Ahmadi, Abdolhamid Ghodselahi, Fabian Kuhn, Anisur Rahaman Molla
  The Cost of Global Broadcast in Dynamic Radio Networks
  2020 Theor Comput Sci, volume: 806, pages: 363 - 387
  » show abstract« hide abstract
  Abstract

  We study the time complexity of single and multi token broadcast in adversarial dynamic radio networks. Initially, k tokens (which are k pieces of information) are distributed among the n nodes of a network and all the tokens need to be disseminated to all the nodes in the network. We first consider the single-token broadcast problem (i.e., the case k=1). By presenting upper and lower bounds, we show that the time complexity of single-token broadcast depends on the amount of stability and connectivity of the dynamic network topology and on the adaptiveness of the adversary providing the dynamic topology. Then, we give two generic algorithms which allow to transform generalized forms of single-token broadcast algorithms into multi-token broadcast (k-token broadcast) algorithms. Based on these generic algorithms, we obtain k-token broadcast algorithms for a number of different dynamic network settings. For one of the modeling assumptions, our algorithm is complemented by a lower bound which shows that the upper bound is close to optimal.

2019

• Mohamad Ahmadi, Fabian Kuhn, Shay Kutten, Anisur Rahaman Molla, Gopal Pandurangan
  The Communication Cost of Information Spreading in Dynamic Networks
  2019 39th IEEE Int. Conf. on Distributed Computing Systems (ICDCS), Dallas, USA
  » show abstract« hide abstract
  Abstract

  This paper investigates the message complexity of distributed information spreading in adversarial dynamic net- works. While distributed computations in dynamic networks have been studied intensively over the last years, almost all of the existing work solely focuses on the time complexity of distributed algorithms. In information spreading, the goal is to spread k tokens of information to every node on an n-node network. We consider the amortized (average) message complexity of spreading a token, assuming that the number of tokens is large. In a static network, this basic problem can be solved using (asymptotically optimal) O(n) amortized messages per token. Our focus is on token-forwarding algorithms, which do not manipulate tokens in any way other than storing, copying, and forwarding them. We present two sets of results depending on how nodes send messages to their neighbors: 1. Local broadcast: We show a tight lower bound of \tilde{Ω}(n^2) on the number of amortized local broadcasts, which is matched by the naive flooding algorithm. The lower bound holds for randomized algorithms against a strongly adaptive adversary. 2. Unicast: We study the message complexity as a function of the number of dynamic changes in the network. To facilitate this, we introduce adversary-competitive message complexity as a natural complexity measure for analyzing dynamic networks: The adversary pays a unit cost for every topological change and the message cost of an algorithm is determined as the actual number of messages sent minus the total cost of the adversary. Under this model, we give a deterministic algorithm that obtains an optimal amortized message complexity of O(n) if the number of tokens k is sufficiently large. We also present a randomized algorithm that achieves subquadratic amortized message complexity for much smaller k under an oblivious adversary.

2017

• Karl Bringmann, Ralph Keusch, Johannes Lengler, Yannic Maus, Anisur Rahaman Molla
  Greedy Routing and the Algorithmic Small-World Phenomenon
  2017 36th ACM Symposium on Principles of Distributed Computing (PODC)
  » show abstract« hide abstract
  Abstract

  The algorithmic small-world phenomenon, empirically established by Milgram's letter forwarding experiments from the 60s~\cite{milgram1967small}, was theoretically explained by Kleinberg in 2000~\cite{KleinbergModel}. However, from today's perspective his model has several severe shortcomings %drawbacks that limit the applicability to real-world networks. In order to give a more convincing explanation of the algorithmic small-world phenomenon, we study decentralized greedy routing in a more flexible random graph model (geometric inhomogeneous random graphs) which overcomes all previous shortcomings. %has not only theoretically good properties, Apart from exhibiting good properties in theory, it has also been extensively experimentally validated that this model reasonably captures real-world networks. In this model, the greedy routing protocol is purely distributed as each vertex only needs to know information about its direct neighbors. We prove that it succeeds with constant probability, and in case of success almost surely finds an almost shortest path of length $\Theta(\log\log n)$, where our bound is tight including the leading constant. Moreover, we study natural local patching methods which augment greedy routing by backtracking and which do not require any global knowledge. We show that such methods can ensure success probability 1 in an asymptotically tight number of steps. These results also address the question of Krioukov et al.~\cite{krioukov2007compact} whether there are efficient local routing protocols for the internet graph. There were promising experimental studies, but the question remained unsolved theoretically. Our results give for the first time a rigorous and analytical affirmative answer.

2015

• Fabian Kuhn, Anisur Rahaman Molla
  Distributed Sparse Cut Approximation
  2015 19th Int. Conf. on Principles of Distributed Systems (OPODIS), Rennes, France
• Mohamad Ahmadi, Abdolhamid Ghodselahi, Fabian Kuhn, Anisur Rahaman Molla
  The Cost of Global Broadcast in Dynamic Radio Networks
  2015 19th Int. Conf. on Principles of Distributed Systems (OPODIS), Rennes, France
  » show abstract« hide abstract
  Abstract

  We study the single-message broadcast problem in dynamic radio networks. We show that the time complexity of the problem depends on the amount of stability and connectivity of the dynamic network topology and on the adaptiveness of the adversary providing the dynamic topology. More formally, we model communication using the standard graph-based radio network model. To model the dynamic network, we use a variant of the synchronous dynamic graph model introduced in [Kuhn et al., STOC 2010]. For integer parameters $T\geq 1$ and $k\geq 1$, we call a dynamic graph $T$-interval $k$-connected if for every interval of $T$ consecutive rounds, there exists a $k$-vertex-connected stable subgraph. Further, for an integer parameter $\tau\geq 0$, we say that the adversary providing the dynamic network is $\tau$-oblivious if for constructing the graph of some round $t$, the adversary has access to all the randomness (and states) of the algorithm up to round $t-\tau$. As our main result, we show that for any $T\geq 1$, any $k\geq 1$, and any $\tau\geq 1$, for a $\tau$-oblivious adversary, there is a distributed algorithm to broadcast a single message in time $O\big(\big(1+\frac{n}{k\cdot \min \set{\tau,T}} \big ) \cdot n \log^3 n \big)$. We further show that even for large interval $k$-connectivity, efficient broadcast is not possible for the usual adaptive adversaries. For a $1$-oblivious adversary, we show that even for any $T\leq (n/k)^{1-\eps}$ (for any constant $\eps > 0$) and for any $k\geq 1$, global broadcast in $T$-interval $k$-connected networks requires at least $\Omega(n^2/k^2\log n)$ time. Further, for a $0$-oblivious adversary, broadcast cannot be solved in $T$-interval $k$-connected networks as long as $T<n-k$.
• Atish Das Sarma, Anisur Rahaman Molla, Gopal Pandurangan
  Distributed Computation of Sparse Cuts via Random Walks
  2015 16th International Conference on Distributed Computing and Networking (ICDCN), Goa, India
  » show abstract« hide abstract
  Abstract

  A sparse cut of a graph is a partition of the vertices into two disjoint subsets such that the ratio of the number of edges across the two subsets divided by the sum of degrees of vertices in the smaller side is minimum. Finding sparse cuts is an important tool in analyzing large-scale distributed networks such as the Internet and Peer-to-Peer networks, as well as large-scale graphs such as the web graph, online social communities, and VLSI circuits. Sparse cuts are useful in graph clustering and partitioning among numerous other applications. In distributed communication networks, they are useful for topology maintenance and for designing better search and routing algorithms. In this paper, we focus on developing a fast distributed algorithm for computing sparse cuts in networks. Given an undirected n-node network G with conductance &phis;, the goal is to find a cut set whose conductance is close to &phis;. We present a distributed algorithm that finds a cut set with sparsity Õ(√&phis;) (Õ hides polylog n factors). Our algorithm works in the CONGEST distributed computing model and outputs a cut of conductance at most Õ (√&phis;) with high probability, in Õ(1/b(1/&phis; + n)log2) rounds, where b is balance of the cut of given conductance. In particular, to find a sparse cut of constant balance, our algorithm takes O((1/&phis; + n)log2 n) rounds. Our algorithm can also be used to output a local cluster, i.e., a subset of vertices near a given source node, and whose conductance is within a quadratic factor of the best possible cluster around the specified node. Our distributed algorithm can work without knowledge of the optimal &phis; value (with only a log n factor slowdown) and hence can be used to find approximate conductance values both globally and with respect to a given source node. Our algorithm uses random walks as a key subroutine and is fully decentralized and uses lightweight local computations. We also give a lower bound on the time needed for any distributed algorithm to compute any non-trivial sparse cut --- any distributed approximation algorithm (for any nontrivial approximation ratio) for computing sparsest cut will take Ω (√n + D) rounds, where D is the diameter of the graph. Our algorithm can be used to find sparse cuts (and their conductance values) and to identify well-connected clusters and critical edges in distributed networks. This in turn can be helpful in the design, analysis, and maintenance of topologically-aware networks.

• Atish Das Sarma, Anisur Rahaman Molla, Gopal Pandurangan
  Distributed computation in dynamic networks via random walks.
  2015 Theor Comput Sci, volume: 581, pages: 45 - 66
  » show abstract« hide abstract
  Abstract

  The paper investigates efficient distributed computation in dynamic networks in which the network topology changes (arbitrarily) from round to round. Our first contribution is a rigorous framework for design and analysis of distributed random walk algorithms in dynamic networks. We then develop a fast distributed random walk based algorithm that runs in O~(τΦ−−−√) rounds (with high probability), where τ is the dynamic mixing time and Φ is the dynamic diameter of the network respectively, and returns a sample close to a suitably defined stationary distribution of the dynamic network. We also apply our fast random walk algorithm to devise fast distributed algorithms for two key problems, namely, information dissemination and decentralized computation of spectral properties in a dynamic network. Our next contribution is a fast distributed algorithm for the fundamental problem of information dissemination (also called as gossip) in a dynamic network. In gossip, or more generally, k-gossip, there are k pieces of information (or tokens) that are initially present in some nodes and the problem is to disseminate the k tokens to all nodes. We present a random-walk based algorithm that runs in O~(min{n1/3k2/3(τΦ)1/3,nk}) rounds (with high probability). To the best of our knowledge, this is the first o(nk)-time fully-distributed token forwarding algorithm that improves over the previous-best O(nk) round distributed algorithm [Kuhn et al., STOC 2010], although in an oblivious adversary model. Our final contribution is a simple and fast distributed algorithm for estimating the dynamic mixing time and related spectral properties of the underlying dynamic network.

• Atish Das Sarma, Anisur Rahaman Molla, Gopal Pandurangan
  Efficient random walk sampling in distributed networks.
  2015 J Parallel Distr Com, volume: 77, pages: 84 - 94
  » show abstract« hide abstract
  Abstract

  Performing random walks in networks is a fundamental primitive that has found numerous applications in communication networks such as token management, load balancing, network topology discovery and construction, search, and peer-to-peer membership management. While several such algorithms are ubiquitous, and use numerous random walk samples, the walks themselves have always been performed naively. In this paper, we focus on the problem of performing random walk sampling efficiently in a distributed network. Given bandwidth constraints, the goal is to minimize the number of rounds and messages required to obtain several random walk samples in a continuous online fashion. We present the first round and message optimal distributed algorithms that present a significant improvement on all previous approaches. The theoretical analysis and comprehensive simulations of our algorithms show that they perform very well in different types of networks of differing topologies. In particular, our results show how several random walks can be performed continuously (when source nodes are provided only at runtime, i.e., online), such that each walk of length ℓℓ can be performed exactly in just View the MathML sourceÕ(ℓD) rounds1 (where DD is the diameter of the network), and O(ℓ)O(ℓ) messages. This significantly improves upon both, the naive technique that requires O(ℓ)O(ℓ) rounds and O(ℓ)O(ℓ) messages, and the sophisticated algorithm of Das Sarma et al. (2013) that has the same round complexity as this paper but requires View the MathML sourceΩ(mℓ) messages (where mm is the number of edges in the network). Our theoretical results are corroborated through extensive simulations on various topological data sets. Our algorithms are fully decentralized, lightweight, and easily implementable, and can serve as building blocks in the design of topologically-aware networks.

• Atish Das Sarma, Anisur Rahaman Molla, Gopal Pandurangan, Eli Upfal
  Fast distributed PageRank computation.
  2015 Theor Comput Sci, volume: 561, pages: 113 - 121
  » show abstract« hide abstract
  Abstract

  Over the last decade, PageRank has gained importance in a wide range of applications and domains, ever since it first proved to be effective in determining node importance in large graphs (and was a pioneering idea behind Google's search engine). In distributed computing alone, PageRank vectors, or more generally random walk based quantities have been used for several different applications ranging from determining important nodes, load balancing, search, and identifying connectivity structures. Surprisingly, however, there has been little work towards designing provably efficient fully-distributed algorithms for computing PageRank. The difficulty is that traditional matrix-vector multiplication style iterative methods may not always adapt well to the distributed setting owing to communication bandwidth restrictions and convergence rates. In this paper, we present fast random walk-based distributed algorithms for computing PageRank in general graphs and prove strong bounds on the round complexity. We first present an algorithm that takes $O(\log n/\eps)$ rounds with high probability on any graph (directed or undirected), where n is the network size and $\eps$ is the reset probability used in the PageRank computation. We then present a faster algorithm that takes $O(\sqrt{\log n}/\eps)$ rounds in undirected graphs. Both of the above algorithms are scalable, as each node processes and sends only small (polylogarithmic in n, the network size) number of bits per round and hence work in the {\sc CONGEST} distributed computing model. For directed graphs, we present an algorithm that has a running time of $O(\sqrt{\log n/\eps})$, but it requires a polynomial number of bits to processed and sent per node in a round. To the best of our knowledge, these are the first fully distributed algorithms for computing PageRank vectors with provably efficient running time.