Round- and Message-Optimal Distributed Part-Wise Aggregation
share
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 a long time. 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. In this paper we provide algorithms that are simultaneously round-optimal with near-linear message complexities for a number of well-studied distributed optimization problems. Our algorithmic centerpiece is such a distributed algorithm that solves what we dub Part-Wise Aggregation: computing simple functions over each part of a graph partition. From this algorithm we derive round-optimal algorithms for MST, Approximate Min-Cut and Approximate Single Source Shortest Paths (SSSP), all with Õ(m) message complexities. On general graphs all of our algorithms achieve a worst-case optimal Õ(D+√(n)) round complexities and Õ(m) message complexities. Furthermore, our algorithms require even fewer rounds on many widely-studied classes of graphs, namely planar, genus-bounded, treewidth-bounded and pathwidth-bounded graphs. For these graphs our algorithms require an optimal Õ(D) rounds and Õ(m) messages. Our results are the first instance of distributed algorithms with Õ(m) message complexities for Approximate Min-Cut and Approximate SSSP. Moreover, our algorithms are the first algorithms for any of these problems that beat the general graph round lower bound of Ω̃(D + √(n)) on graph families of interest and simultaneously achieve an Õ(m) message complexity.
READ FULL TEXT