Gopal Pandurangan

Prof. Dr. Gopal Pandurangan

Department of Computer Science, University of Houston, Houston, TX 77204, USA

Research Focus & Metrics

Academic Career Length

18Years (2009-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
28 January 2012 in Distributed Computing
Verified
Journal Article
Closed access
PDF file
MKMaleq Khan
Maleq Khan
FKFabian Kuhn
Fabian Kuhn
DMDahlia Malkhi
Dahlia Malkhi
GPGopal Pandurangan
Gopal Pandurangan
KTKunal Talwar
Kunal Talwar

1 May 2015 in Theoretical Computer Science
Verified
Journal Article
Closed access
ASAtish Das Sarma
Atish Das Sarma
AMAnisur Rahaman Molla
Anisur Rahaman Molla
GPGopal Pandurangan
Gopal Pandurangan

5 November 2015
Verified
Book Chapter
Closed access
PDF file
JAJohn Augustine
John Augustine
GPGopal Pandurangan
Gopal Pandurangan
PRPeter Robinson
Peter Robinson

16 June 2013 in Distributed Computing
Verified
Journal Article
Closed access
PDF file
GPGopal Pandurangan
Gopal Pandurangan
ATAmitabh Trehan
Amitabh Trehan

28 August 2009 in IEEE Journal on Selected Areas in Communications
Verified
Journal Article
Closed access
YCYongwook Choi
Yongwook Choi
MKMaleq Khan
Maleq Khan
VKVikas Kumar
Vikas Kumar
GPGopal Pandurangan
Gopal Pandurangan
Traditionally, the performance of distributed algorithms has been measured in terms of time and message complexity.Message complexity concerns the number of messages transmitted over all the edges during the course of the algorithm. However, in energy-constrained ad hoc wireless networks (e.g., sensor networks), energy is a critical factor in measuring the efficiency of a distributed algorithm. Transmitting a message between two nodes has an associated cost (energy) and moreover this cost can depend on the two nodes (e.g., the distance between them among other things). Thus in addition to the time and message complexity, it is important to consider energy complexity that accounts for the total energy associated with the messages exchanged among the nodes in a distributed algorithm. This paper addresses the minimum spanning tree (MST) problem, a fundamental problem in distributed computing and communication networks. We study energy-efficient distributed algorithms for the Euclidean MST problem assuming random distribution of nodes. We show a non-trivial lower bound of Omega(log n) on the energy complexity of any distributed MST algorithm. We then give an energy-optimal distributed algorithm that constructs an optimal MST with energy complexity O(log n) on average and O(log n log log n) with high probability. This is an improvement over the previous best known bound on the average energy complexity of Omega(log2 n). Our energy-optimal algorithm exploits a novel property of the giant component of sparse random geometric graphs. All of the above results assume that nodes do not know their geometric coordinates. If the nodes know their own coordinates, then we give an algorithm with O(1) energy complexity (which is the best possible) that gives an O(1) approximation to the MST.

16 June 2023
Verified
Conference Paper
Open access
FDFabien Dufoulon
Fabien Dufoulon
WMWilliam K. Moses
William K. Moses
GPGopal Pandurangan
Gopal Pandurangan
Maximal Independent Set (MIS) is one of the fundamental and most well-studied problems in distributed graph algorithms. Even after four decades of intensive research, the best known (randomized) MIS algorithms have O(log n) round complexity on general graphs [Luby, STOC 1986] (where n is the number of nodes), while the best known lower bound is [EQUATION] [Kuhn, Moscibroda, Wattenhofer, JACM 2016]. Breaking past the O(log n) round complexity upper bound or showing stronger lower bounds have been longstanding open problems. Energy is a premium resource in various settings such as battery-powered wireless networks and sensor networks. The bulk of the energy is used by nodes when they are awake, i.e., when they are sending, receiving, and even just listening for messages. On the other hand, when a node is sleeping, it does not perform any communication and thus spends very little energy. Several recent works have addressed the problem of designing energy-efficient distributed algorithms for various fundamental problems. These algorithms operate by minimizing the number of rounds in which any node is awake, also called the (worst-case) awake complexity. An intriguing open question is whether one can design a distributed MIS algorithm that has significantly smaller awake complexity compared to existing algorithms. In particular, the question of obtaining a distributed MIS algorithm with o(log n) awake complexity was left open in [Chatterjee, Gmyr, Pandurangan, PODC 2020]. Our main contribution is to show that MIS can be computed in awake complexity that is exponentially better compared to the best known round complexity of O(log n) and also bypassing its fundamental [EQUATION] round complexity lower bound exponentially. Specifically, we show that MIS can be computed by a randomized distributed (Monte Carlo) algorithm in O(log log n) awake complexity with high probability.1 However, this algorithm has a round complexity that is O(poly(n)). We then show how to drastically improve the round complexity at the cost of a slight increase in awake complexity by presenting a randomized distributed (Monte Carlo) algorithm for MIS that, with high probability computes an MIS in O((log log n) log* n) awake complexity and O((log3 n)(log log n) log* n) round complexity. Our algorithms work in the CONGEST model where messages of size O(log n) bits can be sent per edge per round.