Anisur Rahaman Molla
Postdoc Researcher (2014 - 2016)
Research interests
My research focuses on distributed graph algorithms. Generally, I am interested in designing and analysis of algorithms, randomized algorithms and probabilistic analysis of algorithms. Recently, I am more involved with problems in distributed dynamic graphs.
Please visit my detailed and regularly updated homepage here!
Publications
Years: 2017 |
2015 | show all Conference papers Karl Bringmann, Ralph Keusch, Johannes Lengler, Yannic Maus, Anisur Rahaman MollaGreedy Routing and the Algorithmic Small-World Phenomenon 2017 Principles of Distributed Computing (PODC), July 25-27, 2017, Washington, DC, USA » 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. Conference papers Fabian Kuhn, Anisur Rahaman MollaDistributed Sparse Cut Approximation 2015 19th Int. Conf. on Principles of Distributed Systems (OPODIS), Rennes, France Mohamad Ahmadi, Abdolhamid Ghodselahi, Fabian Kuhn, Anisur Rahaman MollaThe 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 PanduranganDistributed 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. Journal Papers Atish Das Sarma, Anisur Rahaman Molla, Gopal PanduranganDistributed 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 PanduranganEfficient 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 UpfalFast 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.