9 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…
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…
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…