This paper presents a randomized Las Vegas distributed algorithm that constructs a minimum spanning tree (MST) in weighted networks with optimal (up to polylogarithmic factors) time and message complexity. This algorithm runs in @math time and exchanges @math messages (both with high probability), where @math is the number of nodes of the network, @math is the diameter, and @math is the number of edges. This is the first distributed MST algorithm that matches the time lower bound of @math [Elkin, SIAM J. Comput. 2006] and the message lower bound of @math [, J.ACM 2015] (which both apply to randomized algorithms). The prior time and message lower bounds are derived using two completely different graph constructions; the existing lower bound construction that shows one lower bound does not work for the other. To complement our algorithm, we present a new lower bound graph construction for which any distributed MST algorithm requires @math rounds and @math messages.
Some classes of graphs admit efficient MST algorithms that beat the general @math time lower bound. This is the case for planar graphs, graphs of bounded genus, treewidth, or pathwidth @cite_12 @cite_30 @cite_43 , and graphs with small random walk mixing time @cite_20 .
@cite_30 @cite_43 @cite_20 @cite_12
2484918492 2515165863 2737872496 2294674552
Distributed optimization algorithms are frequently faced with solving sub-problems on disjoint connected parts of a network. Unfortunately, the diameter of these parts can be significantly larger than the diameter of the underlying network, leading to slow running times. Recent work by [Ghaffari and Hauepler; SODA'16] showed that this phenomenon can be seen as the broad underlying reason for the pervasive Omega(√n + D) lower bounds that apply to most optimization problems in the CONGEST model. On the positive side, this work also introduced low-congestion shortcuts as an elegant solution to circumvent this problem in certain topologies of interest. Particularly, they showed that there exist good shortcuts for any planar network and more generally any bounded genus network. This directly leads to fast O(DlogO(1)n) distributed optimization algorithms on such topologies, e.g., for MST and Min-Cut approximation, given that one can efficiently construct these shortcuts in a distributed manner. Unfortunately, the shortcut construction of [Ghaffari and Hauepler; SODA'16] relies heavily on having access to a bounded genus embedding of the network. Computing such an embedding distributedly, however, is a hard problem - even for planar networks. No distributed embedding algorithm for bounded genus graphs is in sight. In this work, we side-step this problem by defining a slightly restricted and more structured form of shortcuts and giving a novel construction algorithm which efficiently finds a shortcut which is, up to a logarithmic factor, as good as the best shortcut that exists for a given network. This new construction algorithm directly leads to an O(D logO(1) n)-round algorithm for solving optimization problems like MST for any topology for which good restricted shortcuts exist - without the need to compute any embedding. This includes the first efficient algorithm for bounded genus graphs. We show that many distributed network optimization problems can be solved much more efficiently in structured and topologically simple networks. We present a randomized distributed algorithm that computes a minimum spanning tree in τ(G) · 2O(√(log n log log n))) rounds, in any n-node graph G with mixing time τ(G). This result provides a sub-polynomial complexity for a wide range of graphs of practical interest, and goes below the celebrated Ω(D+ √n) lower bound of Das [STOC'11] which holds for some worst-case general graphs. The core novelty in this result is a distributed method for permutation routing. In this problem, one is given a number of source-destination pairs, and we should deliver one packet from each source to its destination, all in parallel, in the shortest span of time possible. Our algorithm allows us to route and deliver all these packets in τ(G) · 2O(√(log n log log n)) rounds, assuming that each node v is the source or destination for at most dG(v) packets. The main technical ingredient in this routing result is a certain hierarchical embedding of good-expansion random graphs on the base graph, which we believe can be of interest well beyond this work. This paper introduces the concept of low-congestion shortcuts for (near-)planar networks, and demonstrates their power by using them to obtain near-optimal distributed algorithms for problems such as Minimum Spanning Tree (MST) or Minimum Cut, in planar networks. Consider a graph G = (V, E) and a partitioning of V into subsets of nodes S1, . . ., SN, each inducing a connected subgraph G[Si]. We define an α-congestion shortcut with dilation β to be a set of subgraphs H1, . . ., HN ⊆ G, one for each subset Si, such that 1. For each i ∈ [1, N], the diameter of the subgraph G[Si] + Hi is at most β. 2. For each edge e ∈ E, the number of subgraphs G[Si] + Hi containing e is at most α. We prove that any partition of a D-diameter planar graph into individually-connected parts admits an O(D log D)-congestion shortcut with dilation O(D log D), and we also present a distributed construction of it in O(D) rounds. We moreover prove these parameters to be near-optimal; i.e., there are instances in which, unavoidably, max α, β = Ω(D[EQUATION]). Finally, we use low-congestion shortcuts, and their efficient distributed construction, to derive O(D)-round distributed algorithms for MST and Min-Cut, in planar networks. This complexity nearly matches the trivial lower bound of Ω(D). We remark that this is the first result bypassing the well-known Ω(D + [EQUATION]) existential lower bound of general graphs (see Peleg and Rubinovich [FOCS'99]; Elkin [STOC'04]; and Das [STOC'11]) in a family of graphs of interest.