8 papers
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)…
Tight Communication Bounds for Distributed Algorithms in the Quantum Routing Model
Fabien Dufoulon, Frédéric Magniez, Gopal Pandurangan
We present new distributed quantum algorithms for fundamental distributed computing problems, namely, leader election, broadcast, Minimum Spanning Tree (MST), and Breadth-First Sea…
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…
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…