1 citations · 1 across the 10 of their papers we have counts for
15 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…
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…
Distributed Coloring in the SLEEPING Model
Fabien Dufoulon, Pierre Fraigniaud, Mikaël Rabie +1
In distributed network computing, a variant of the LOCAL model has been recently introduced, referred to as the SLEEPING model. In this model, nodes have the ability to decide on w…
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…
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…
Beeping Shortest Paths via Hypergraph Bipartite Decomposition
Fabien Dufoulon, Yuval Emek, Ran Gelles
Constructing a shortest path between two network nodes is a fundamental task in distributed computing. This work develops schemes for the construction of shortest paths in randomiz…
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…
Efficient Deterministic Leader Election for Programmable Matter
Fabien Dufoulon, Shay Kutten, William K. Moses
It was suggested that a programmable matter system (composed of multiple computationally weak mobile particles) should remain connected at all times since otherwise, reconnection i…