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.
Das @cite_36 settled the time complexity of distributed approximate MST by showing that this problem, as well as approximating shortest paths and about twenty other problems, satisfies a time lower bound of @math . This applies to deterministic as well as randomized algorithms, and to both exact and approximate versions. In other words, any distributed algorithm for computing a @math -approximation to MST, for any @math , takes @math time in the worst case.
@cite_36
2592535728 2015819397 2009279347 2030982625
Distributed minimum spanning tree (MST) problem is one of the most central and fundamental problems in distributed graph algorithms. Kutten and Peleg [KP98] devised an algorithm with running time O(D + √n . log* n), where D is the hop-diameter of the input n-vertex m-edge graph, and with message complexity O(m + n3 2). Peleg and Rubinovich [PR99] showed that the running time of the algorithm of [KP98] is essentially tight, and asked if one can achieve near-optimal running time together with near-optimal message complexity. In a recent breakthrough, [PRS16] answered this question in the affirmative, and devised a randomized algorithm with time O(D+ √n) and message complexity O(m). They asked if such a simultaneous time- and message-optimality can be achieved by a deterministic algorithm. In this paper, building upon the work of [PRS16], we answer this question in the affirmative, and devise a deterministic algorithm that computes MST in time O((D + √n). log n), using O(m . log n + n log n . log* n) messages. The polylogarithmic factors in the time and message complexities of our algorithm are significantly smaller than the respective factors in the result of [PRS16]. Also, our algorithm and its analysis are very simple and self-contained, as opposed to rather complicated previous sublinear-time algorithms [GKP98,KP98,E04b,PRS16]. This paper presents a lower bound of @math on the time required for the distributed construction of a minimum-weight spanning tree (MST) in weighted n-vertex networks of diameter @math , in the bounded message model. This establishes the asymptotic near-optimality of existing time-efficient distributed algorithms for the problem, whose complexity is @math . We give a 7.18-approximation algorithm for the minimum latency problem that uses only @math calls to the prize-collecting Steiner tree (PCST) subroutine of Goemans and Williamson. This improves the previous best algorithms in both performance guarantee and running time. A previous algorithm of Goemans and Kleinberg for the minimum latency problem requires an approximation algorithm for the @math -minimum spanning tree ( @math -MST) problem which is called as a black box for each value of @math . Their algorithm can achieve an approximation factor of 10.77 while making @math PCST calls, a factor of 8.98 using @math PCST calls, or a factor of @math using @math PCST calls, via the @math -MST algorithms of Garg, Arya and Ramesh, and Arora and Karakostas, respectively. Here @math denotes the number of nodes in the instance, and @math is the largest edge cost in the input. In all cases, the running time is dominated by the PCST calls. Since the PCST subroutine can be implemented to run in @math time, the overall running time of our algorithm is @math . We also give a faster randomized version of our algorithm that achieves the same approximation guarantee in expectation, but uses only @math PCST calls, and derandomize it to obtain a deterministic algorithm with factor @math , using @math PCST calls. The basic idea for our improvement is that we do not treat the @math -MST algorithm as a black box. This allows us to take advantage of some special situations in which the PCST subroutine delivers a 2-approximate @math -MST. We are able to obtain the same approximation ratio that would be given by Goemans and Kleinberg if we had access to 2-approximate @math -MSTs for all values of @math , even though we have them only for some values of @math that we are not able to specify in advance. We also extend our algorithm to a weighted version of the minimum latency problem. This paper studies the problem of constructing a minimum-weight spanning tree (MST) in a distributed network. This is one of the most important problems in the area of distributed computing. There is a long line of gradually improving protocols for this problem, and the state of the art today is a protocol with running time O(Λ(G)+n⋅log∗n) due to Kutten and Peleg [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40–66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20–27], where Λ(G) denotes the diameter of the graph G. Peleg and Rubinovich [D. Peleg, V. Rubinovich, A near-tight lower bound on the time complexity of distributed MST construction, in: Proc. 40th IEEE Symp. on Foundations of Computer Science, 1999, pp. 253–261] have shown that Ω˜(n) time is required for constructing MST even on graphs of small diameter, and claimed that their result “establishes the asymptotic near-optimality” of the protocol of [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40–66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20–27]. In this paper we refine this claim, and devise a protocol that constructs the MST in Ω˜(μ(G,ω)+n) rounds, where μ(G,ω) is the MST-radius of the graph. The ratio between the diameter and the MST-radius may be as large as Θ(n), and, consequently, on some inputs our protocol is faster than the protocol of [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40–66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20–27] by a factor of Ω˜(n). Also, on every input, the running time of our protocol is never greater than twice the running time of the protocol of [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40–66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20–27]. As part of our protocol for constructing an MST, we develop a protocol for constructing neighborhood covers with a drastically improved running time. The latter result may be of independent interest.