12 papers · 1 filter
Tight Energy Lower Bounds for Distributed Graph Algorithms
Fabien Dufoulon, Gopal Pandurangan, Peter Robinson
There has been a significant recent interest in designing distributed algorithms in the SLEEPING model that minimize the {energy (a.k.a awake) complexity, which measures the number…
Fast Gossip-based Rumor Spreading using Small Messages
Fabien Dufoulon, William K. Moses, Gopal Pandurangan
We study gossip algorithms for the fundamental rumor spreading problem, where the goal is to disseminate a rumor from a given source node to all nodes in an arbitrary (and unknown)…
Energy-Efficient Maximal Independent Sets in Radio Networks
Dominick Banasik, Varsha Dani, Fabien Dufoulon +3
The maximal independent set (MIS) is one of the most fundamental problems in distributed computing, and it has been studied intensively for over four decades. This paper focuses on…
Improved Byzantine Agreement under an Adaptive Adversary
Fabien Dufoulon, Gopal Pandurangan
Byzantine agreement is a fundamental problem in fault-tolerant distributed computing that has been studied intensively for the last four decades. Much of the research has focused o…
Fully-Distributed Construction of Byzantine-Resilient Dynamic Peer-to-Peer Networks
Aayush Gupta, Gopal Pandurangan
We address a fundamental problem in Peer-to-Peer (P2P) networks, namely, constructing and maintaining dynamic P2P overlay network topologies with essential properties such as conne…
Message Optimality and Message-Time Trade-offs for APSP and Beyond
Fabien Dufoulon, Shreyas Pai, Gopal Pandurangan +2
Round complexity is an extensively studied metric of distributed algorithms. In contrast, our knowledge of the \emph{message complexity} of distributed computing problems and its r…
Quantum Communication Advantage for Leader Election and Agreement
Fabien Dufoulon, Frédéric Magniez, Gopal Pandurangan
This work focuses on understanding the quantum message complexity of two central problems in distributed computing, namely, leader election and agreement in synchronous message-pas…
The Singular Optimality of Distributed Computation in LOCAL
Fabien Dufoulon, Gopal Pandurangan, Peter Robinson +1
It has been shown that one can design distributed algorithms that are (nearly) singularly optimal, meaning they simultaneously achieve optimal time and message complexity (within p…
Fully-Distributed Byzantine Agreement in Sparse Networks
John Augustine, Fabien Dufoulon, Gopal Pandurangan
Byzantine agreement is a fundamental problem in fault-tolerant distributed networks that has been studied intensively for the last four decades. Most of these works designed protoc…
Towards Communication-Efficient Peer-to-Peer Networks
Khalid Hourani, William K. Moses, Gopal Pandurangan
We focus on designing Peer-to-Peer (P2P) networks that enable efficient communication. Over the last two decades, there has been substantial algorithmic research on distributed pro…
Time- and Communication-Efficient Overlay Network Construction via Gossip
Fabien Dufoulon, Michael Moorman, William K. Moses +1
We focus on the well-studied problem of distributed overlay network construction. We consider a synchronous gossip-based communication model where in each round a node can send a m…
The Message Complexity of Distributed Graph Optimization
Fabien Dufoulon, Shreyas Pai, Gopal Pandurangan +2
The message complexity of a distributed algorithm is the total number of messages sent by all nodes over the course of the algorithm. This paper studies the message complexity of d…