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…