67 citations · 140 across the 37 of their papers we have counts for
49 papers
An Almost Singularly Optimal Asynchronous Distributed MST Algorithm
Fabien Dufoulon, Shay Kutten, William K. Moses +2
A singularly (near) optimal distributed algorithm is one that is (near) optimal in \emph{two} criteria, namely, its time and message complexities. For \emph{synchronous} CONGEST ne…
Byzantine-Resilient Counting in Networks
Soumyottam Chatterjee, Gopal Pandurangan, Peter Robinson
We present two distributed algorithms for the {\em Byzantine counting problem}, which is concerned with estimating the size of a network in the presence of a large number of Byzant…
Awake Complexity of Distributed Minimum Spanning Tree
John Augustine, William K. Moses, Gopal Pandurangan
We study the distributed minimum spanning tree (MST) problem, a fundamental problem in distributed computing. It is well-known that distributed MST can be solved in $\tilde{O}(D+\s…
Distributed MIS in Awake Complexity
Fabien Dufoulon, William K. Moses, 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-know…
Singularly Near Optimal Leader Election in Asynchronous Networks
Shay Kutten, William K. Moses, Gopal Pandurangan +1
This paper concerns designing distributed algorithms that are {\em singularly optimal}, i.e., algorithms that are {\em simultaneously} time and message {\em optimal}, for the funda…
Can We Break Symmetry with o(m) Communication?
Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju +1
We study the communication cost (or message complexity) of fundamental distributed symmetry breaking problems, namely, coloring and MIS. While significant progress has been made in…