Distributed graph algorithms that separately optimize for either the number of rounds used or the total number of messages sent have been studied extensively. However, algorithms simultaneously efficient with respect to both measures have been elusive. For example, only very recently was it shown that for Minimum Spanning Tree (MST), an optimal message and round complexity is achievable (up to polylog terms) by a single algorithm in the CONGEST model of communication.

We provide algorithms that are simultaneously round-optimal with near-linear message complexities for a number of well-studied distributed optimization problems. Our main result is such a distributed algorithm for the fundamental primitive of computing simple functions over each part of a graph partition. From this algorithm we derive round- and message-optimal algorithms for MST, Approximate Min-Cut and Approximate Single Source Shortest Paths. On general graphs all of our algorithms achieve worst-case optimal $\tilde{O}(D+\sqrt n)$ round complexity and $\tilde{O}(m)$ message complexity. Furthermore, our algorithms require optimal $\tilde{O}(D)$ rounds and $\tilde{O}(n)$ messages on planar, genus-bounded, treewidth-bounded and pathwidth-bounded graphs.

ArXiv post available here.