3 papers
cs.DC2026
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…
cs.DC2025
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…
cs.DC2024
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…