I'm interested in designing new distributed and parallel algorithms, the distributed processing of big data, achieving fault-tolerance in networks, and secure distributed computing in dynamic environments such as peer-to-peer networks and mobile ad-hoc networks.

## Publications tagged with "Graph Algorithm" (Show all)

2017
• A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees
Gopal Pandurangan, Peter Robinson, Michele Scquizzato. 49th ACM Symposium on Theory of Computing (STOC 2017).
Abstract...
This paper presents a randomized (Las Vegas) distributed algorithm that constructs a minimum spanning tree (MST) in weighted networks with optimal (up to polylogarithmic factors) time and message complexity. This algorithm runs in $\tilde{O}(D + \sqrt{n})$ time and exchanges $\tilde{O}(m)$ messages (both with high probability), where $n$ is the number of nodes of the network, $D$ is the diameter, and $m$ is the number of edges. This is the first distributed MST algorithm that matches simultaneously the time lower bound of $\tilde{\Omega}(D + \sqrt{n})$ [Elkin, SIAM J. Comput. 2006] and the message lower bound of $\Omega(m)$ [Kutten et al., JACM 2015], which both apply to randomized Monte Carlo algorithms. The prior time and message lower bounds are derived using two completely different graph constructions; the existing lower bound construction that shows one lower bound does not work for the other. To complement our algorithm, we present a new lower bound graph construction for which any distributed MST algorithm requires both $\tilde{\Omega}(D + \sqrt{n})$ rounds and $\Omega(m)$ messages.
• Symmetry Breaking in the Congest Model: Message- and Time-Efficient Algorithms for Ruling Sets.
Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, Talal Riaz, Peter Robinson. (under review)
Abstract...
We study local symmetry breaking problems in the Congest model, focusing on ruling set problems, which generalize the fundamental Maximal Independent Set (MIS) problem. The time (round) complexity of MIS (and ruling sets) have attracted much attention in the Local model. Indeed, recent results (Barenboim et al., FOCS 2012, Ghaffari SODA 2016) for the MIS problem have tried to break the long-standing $O(\log n)$-round barrier'' achieved by Luby's algorithm, but these yield $o(\log n)$-round complexity only when the maximum degree $\Delta$ is somewhat small relative to $n$. More importantly, these results apply only in the Local model. In fact, the best known time bound in the Congest model is still $O(\log n)$ (via Luby's algorithm) even for somewhat small $\Delta$. Furthermore, message complexity has been largely ignored in the context of local symmetry breaking. Luby's algorithm takes $O(m)$ messages on $m$-edge graphs and this is the best known bound with respect to messages. Our work is motivated by the following central question: can we break the $\Theta(m)$ message bound and the $\Theta(\log n)$ time bound in the Congest model for MIS or closely-related symmetry breaking problems? This paper presents progress towards this question for the distributed ruling set problem in the Congest model. A $\beta$-ruling set is an independent set such that every node in the graph is at most $\beta$ hops from a node in the independent set. We present the following results: 1. Time Complexity: We show that we can break the $O(\log n)$ barrier'' for 2- and 3-ruling sets. We compute 3-ruling sets in $O\left(\log n/\log \log n\right)$ rounds with high probability (whp). More generally we show that 2-ruling sets can be computed in $O\left(\log \Delta \cdot (\log n)^{1/2 + \varepsilon} + \log n/\log\log n\right)$ rounds for any $\varepsilon > 0$, which is $o(\log n)$ for a wide range of $\Delta$ values (e.g., $\Delta = 2^{(\log n)^{1/2-\varepsilon}}$). These are the first 2- and 3-ruling set algorithms to improve over the $O(\log n)$-round complexity of Luby's algorithm in the Congest model. 2. Message Complexity: We show an $\Omega(n^2)$ lower bound on the message complexity of computing an MIS (i.e., 1-ruling set) which holds also for randomized algorithms and present a contrast to this by showing a randomized algorithm for 2-ruling sets that, whp, uses only $O(n \log^2 n)$ messages and runs in $O(\Delta \log n)$ rounds. This is the first message-efficient algorithm known for ruling sets, which takes near-linear message complexity (which is optimal up to a polylogarithmic factor). Our results are a step toward understanding the time and message complexity of symmetry breaking problems in the Congest model.
2016
• Fast Distributed Algorithms for Connectivity and MST in Large Graphs DOI
Gopal Pandurangan, Peter Robinson, Michele Scquizzato. 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2016).
Abstract...
Motivated by the increasing need to understand the algorithmic foundations of distributed large-scale graph computations, we study a number of fundamental graph problems in a message-passing model for distributed computing where $k \geq 2$ machines jointly perform computations on graphs with $n$ nodes (typically, $n \gg k$). The input graph is assumed to be initially randomly partitioned among the $k$ machines, a common implementation in many real-world systems. Communication is point-to-point, and the goal is to minimize the number of communication rounds of the computation. Our main result is an (almost) optimal distributed randomized algorithm for graph connectivity. Our algorithm runs in $\tilde{O}(n/k^2)$ rounds ($\tilde{O}$ notation hides a $\text{polylog}(n)$ factor and an additive $\text{polylog}(n)$ term). This improves over the best previously known bound of $\tilde{O}(n/k)$ [Klauck et al., SODA 2015], and is optimal (up to a polylogarithmic factor) in view of an existing lower bound of $\tilde{\Omega}(n/k^2)$. Our improved algorithm uses a bunch of techniques, including linear graph sketching, that prove useful in the design of efficient distributed graph algorithms. We then present fast randomized algorithms for computing minimum spanning trees, (approximate) min-cuts, and for many graph verification problems. All these algorithms take $\tilde{O}(n/k^2)$ rounds, and are optimal up to polylogarithmic factors. We also show an almost matching lower bound of $\tilde{\Omega}(n/k^2)$ for many graph verification problems using lower bounds in random-partition communication complexity.
• Efficient Computation of Sparse Structures DOI
David G. Harris, Ehab Morsy, Gopal Pandurangan, Peter Robinson, Aravind Srinivasan. Random Structures & Algorithms (RSA).
Abstract...
Basic graph structures such as maximal independent sets (MIS's) have spurred much theoretical research in randomized and distributed algorithms, and have several applications in networking and distributed computing as well. However, the extant (distributed) algorithms for these problems do not necessarily guarantee fault-tolerance or load-balance properties. We propose and study ''low-average degree'' or sparse'' versions of such structures. Interestingly, in sharp contrast to, say, MIS's, it can be shown that checking whether a structure is sparse, will take substantial time. Nevertheless, we are able to develop good sequential/distributed (randomized) algorithms for such sparse versions. We also complement our algorithms with several lower bounds. Randomization plays a key role in our upper and lower bound results.
• DEX: Self-Healing Expanders DOI
Gopal Pandurangan, Peter Robinson, Amitabh Trehan. Distributed Computing (DC).
Abstract...
We present a fully-distributed self-healing algorithm DEX, that maintains a constant degree expander network in a dynamic setting. To the best of our knowledge, our algorithm provides the first efficient distributed construction of expanders --- whose expansion properties hold deterministically --- that works even under an all-powerful adaptive adversary that controls the dynamic changes to the network (the adversary has unlimited computational power and knowledge of the entire network state, can decide which nodes join and leave and at what time, and knows the past random choices made by the algorithm). Previous distributed expander constructions typically provide only probabilistic guarantees on the network expansion which rapidly degrade in a dynamic setting; in particular, the expansion properties can degrade even more rapidly under adversarial insertions and deletions. Our algorithm provides efficient maintenance and incurs a low overhead per insertion/deletion by an adaptive adversary: only $O(\log n)$ rounds and $O(\log n)$ messages are needed with high probability ($n$ is the number of nodes currently in the network). The algorithm requires only a constant number of topology changes. Moreover, our algorithm allows for an efficient implementation and maintenance of a distributed hash table (DHT) on top of DEX, with only a constant additional overhead. Our results are a step towards implementing efficient self-healing networks that have guaranteed properties (constant bounded degree and expansion) despite dynamic changes.
2015
• Distributed Computation of Large-scale Graph Problems PDF DOI
Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan, Peter Robinson. 26th ACM-SIAM Symposium on Discrete Algorithms (SODA 2015).
Abstract...
Motivated by the increasing need for fast distributed processing of large-scale graphs such as the Web graph and various social networks, we study a number of fundamental graph problems in the message-passing model, where we have $k$ machines that jointly perform computation on an arbitrary $n$-node (typically, $n \gg k$) input graph. The graph is assumed to be randomly partitioned among the $k \geq 2$ machines (a common implementation in many real world systems). The communication is point-to-point, and the goal is to minimize the time complexity, i.e., the number of communication rounds, of solving various fundamental graph problems. We present lower bounds that quantify the fundamental time limitations of distributively solving graph problems. We first show a lower bound of $\Omega(n/k)$ rounds for computing a spanning tree (ST) of the input graph. This result also implies the same bound for other fundamental problems such as computing a minimum spanning tree (MST), breadth-first tree (BFS), and shortest paths tree (SPT). We also show an $\Omega(n/k^2)$ lower bound for connectivity, ST verification and other related problems. Our lower bounds develop and use new bounds in random-partition communication complexity. To complement our lower bounds, we also give algorithms for various fundamental graph problems, e.g., PageRank, MST, connectivity, ST verification, shortest paths, cuts, spanners, covering problems, densest subgraph, subgraph isomorphism, finding triangles, etc. We show that problems such as PageRank, MST, connectivity, and graph covering can be solved in $\tilde{O}(n/k)$ time (the notation $\tilde O$ hides $\text{polylog}(n)$ factors and an additive $\text{polylog}(n)$ term); this shows that one can achieve almost linear (in $k$) speedup, whereas for shortest paths, we present algorithms that run in $\tilde{O}(n/\sqrt{k})$ time (for $(1+\epsilon)$-factor approximation) and in $\tilde{O}(n/k)$ time (for $O(\log n)$-factor approximation) respectively. Our results are a step towards understanding the complexity of distributively solving large-scale graph problems.
2014
• DEX: Self-Healing Expanders PDF DOI
Gopal Pandurangan, Peter Robinson, Amitabh Trehan. 28th IEEE International Parallel Distributed Processing Symposium (IPDPS 2014).
Abstract...
We present a fully-distributed self-healing algorithm DEX, that maintains a constant degree expander network in a dynamic setting. To the best of our knowledge, our algorithm provides the first efficient distributed construction of expanders --- whose expansion properties hold deterministically --- that works even under an all-powerful adaptive adversary that controls the dynamic changes to the network (the adversary has unlimited computational power and knowledge of the entire network state, can decide which nodes join and leave and at what time, and knows the past random choices made by the algorithm). Previous distributed expander constructions typically provide only probabilistic guarantees on the network expansion which rapidly degrade in a dynamic setting; in particular, the expansion properties can degrade even more rapidly under adversarial insertions and deletions. Our algorithm provides efficient maintenance and incurs a low overhead per insertion/deletion by an adaptive adversary: only $O(\log n)$ rounds and $O(\log n)$ messages are needed with high probability ($n$ is the number of nodes currently in the network). The algorithm requires only a constant number of topology changes. Moreover, our algorithm allows for an efficient implementation and maintenance of a distributed hash table (DHT) on top of DEX, with only a constant additional overhead. Our results are a step towards implementing efficient self-healing networks that have guaranteed properties (constant bounded degree and expansion) despite dynamic changes.
• Distributed Symmetry Breaking in Hypergraphs PDF DOI
Shay Kutten, Danupon Nanongkai, Gopal Pandurangan, Peter Robinson. 28th International Symposium on Distributed Computing (DISC 2014).
Abstract...
Fundamental local symmetry breaking problems such as Maximal Independent Set (MIS) and coloring have been recognized as important by the community, and studied extensively in (standard) graphs. In particular, fast (i.e., logarithmic run time) randomized algorithms are well-established for MIS and $\Delta +1$-coloring in both the LOCAL and CONGEST distributed computing models. On the other hand, comparatively much less is known on the complexity of distributed symmetry breaking in hypergraphs. In particular, a key question is whether a fast (randomized) algorithm for MIS exists for hypergraphs. In this paper, we study the distributed complexity of symmetry breaking in hypergraphs by presenting distributed randomized algorithms for a variety of fundamental problems under a natural distributed computing model for hypergraphs. We first show that MIS in hypergraphs (of arbitrary dimension) can be solved in $O(\log^2 n)$ rounds ($n$ is the number of nodes of the hypergraph) in the LOCAL model. We then present a key result of this paper --- an $O(\Delta^{\epsilon}\text{poly} \log n)$-round hypergraph MIS algorithm in the CONGEST model where $\Delta$ is the maximum node degree of the hypergraph and $\epsilon > 0$ is any arbitrarily small constant. To demonstrate the usefulness of hypergraph MIS, we present applications of our hypergraph algorithm to solving problems in (standard) graphs. In particular, the hypergraph MIS yields fast distributed algorithms for the balanced minimal dominating set problem (left open in Harris et al. [ICALP 2013]) and the minimal connected dominating set problem. We also present distributed algorithms for coloring, maximal matching, and maximal clique in hypergraphs. Our work shows that while some local symmetry breaking problems such as coloring can be solved in polylogarithmic rounds in both the LOCAL and CONGEST models, for many other hypergraph problems such as MIS, hitting set, and maximal clique, it remains challenging to obtain polylogarithmic time algorithms in the CONGEST model. This work is a step towards understanding this dichotomy in the complexity of hypergraph problems as well as using hypergraphs to design fast distributed algorithms for problems in (standard) graphs.
2013
• Efficient Computation of Balanced Structures PDF DOI
David G. Harris, Ehab Morsy, Gopal Pandurangan, Peter Robinson, Aravind Srinivasan. 40th International Colloquium on Automata, Languages and Programming (ICALP 2013).
Abstract...
Basic graph structures such as maximal independent sets (MIS’s) have spurred much theoretical research in distributed algorithms, and have several applications in networking and distributed computing as well. However, the extant (distributed) algorithms for these problems do not necessarily guarantee fault-tolerance or load-balance properties: For example, in a star-graph, the central vertex, as well as the set of leaves, are both MIS’s, with the latter being much more fault-tolerant and balanced - existing distributed algorithms do not handle this distinction. We propose and study "low-average degree" or "balanced" versions of such structures. Interestingly, in sharp contrast to, say, MIS’s, it can be shown that checking whether a structure is balanced, will take substantial time. Nevertheless, we are able to develop good sequential and distributed algorithms for such "balanced" versions. We also complement our algorithms with lower bounds.

## Code

I'm interested in parallel and distributed programming and related technologies such as software transactional memory. Below is a (non-comprehensive) list of software that I have written.
• I extended Cabal, for using a "world" file to keep track of installed packages. (Now part of the main distribution.)
• data dispersal: an implementation of an (m,n)-threshold information dispersal scheme that is space-optimal.
• secret sharing: an implementation of a secret sharing scheme that provides information-theoretic security.
• dice-entropy: a library that provides cryptographically secure dice rolls implemented by bit-efficient rejection sampling.
• TSkipList: a data structure with range-query support for software transactional memory.
• stm-io-hooks: An extension of Haskell's Software Transactional Memory (STM) monad with commit and retry IO hooks.
• Mathgenealogy: Visualize your (academic) genealogy! A program for extracting data from the Mathematics Genealogy project.
• In my master thesis I developed a system for automatically constructing events out of log files produced by various system programs. One of the core components of my work was a part-of-speech (POS) tagger, which assigns word classes (e.g. noun, verb) to the previously parsed tokens of the log file. To cope with noisy input data, I modeled the POS tagger as a hidden Markov model. I developed (and proved the correctness of) a variant of the maximum likelihood estimation algorithm for training the Markov model and smoothing the state transition distributions.

## Misc

• Conferences that I attended so far: PODC 2008 (Toronto, Canada); SSS 2008 (Detroit, USA); OPODIS 2009 (Nimes, France); ALGOSENSORS 2010 (Bordeaux, France); DISC 2010; (Boston, USA) IPDPS 2011 (Anchorage, USA); FOMC 2011 (San Jose, USA); SODA 2012 (Kyoto, Japan); SIROCCO 2012 (Reykjavik, Iceland); ICDCN 2013 (Mumbai, India); ICALP 2013 (Riga, Latvia); SPAA 2013 (Montreal, Canada); PODC 2013 (Montreal, Canada); Shonan Workshop (Shonan Village, Japan); DISC 2015 (Tokyo, Japan); ICDCN 2016 (Singapore); SPAA 2016 (Monterey, California); DISC 2016 (Paris, France).
• Program committee membership: BGP 2017, ICDCN 2016, SPAA 2016, SIROCCO 2016, ICDCN 2015, SIROCCO 2014, FOMC 2014
• DBLP entry.