This paper presents a distributed O(1)-approximation algorithm, with expected- @math running time, in the @math model for the metric facility location problem on a size- @math clique network. Though metric facility location has been considered by a number of researchers in low-diameter settings, this is the first sub-logarithmic-round algorithm for the problem that yields an O(1)-approximation in the setting of non-uniform facility opening costs. In order to obtain this result, our paper makes three main technical contributions. First, we show a new lower bound for metric facility location, extending the lower bound of B a (ICALP 2005) that applies only to the special case of uniform facility opening costs. Next, we demonstrate a reduction of the distributed metric facility location problem to the problem of computing an O(1)-ruling set of an appropriate spanning subgraph. Finally, we present a sub-logarithmic-round (in expectation) algorithm for computing a 2-ruling set in a spanning subgraph of a clique. Our algorithm accomplishes this by using a combination of randomized and deterministic sparsification.
Several more recent papers have continued the development of super-fast'' algorithms in low-diameter settings. In STOC 2011, Lenzen and Wattenhofer @cite_16 derived tight bounds on parallel load balancing and their result has applications in how information can be quickly disseminated in a clique (in the @math model). In PODC 2011, Patt-Shamir and Teplitsky @cite_20 presented on @math randomized algorithm for the problem. Third, Lenzen @cite_2 showed that randomization is not necessary for solving problems such as distributed sorting efficiently. Lenzen presented , constant-round algorithms for a routing problem and for the distributed sorting problem considered in @cite_20 . Constant-round algorithms for sophisticated problems, of the kind described by Lenzen @cite_2 , highlight the difficulty of showing non-trivial lower bounds in the @math model for clique networks. For example, it has been proved that computing an MST in general requires @math rounds for diameter- @math graphs @cite_3 , but no non-trivial lower bounds are known for diameter- @math or clique (diameter- @math ) networks.
@cite_16 @cite_3 @cite_20 @cite_2
1992996565 1515635142 2900102855 2030982625
We study two fundamental graph problems, Graph Connectivity (GC) and Minimum Spanning Tree (MST), in the well-studied Congested Clique model, and present several new bounds on the time and message complexities of randomized algorithms for these problems. No non-trivial (i.e., super-constant) time lower bounds are known for either of the aforementioned problems; in particular, an important open question is whether or not constant-round algorithms exist for these problems. We make progress toward answering this question by presenting randomized Monte Carlo algorithms for both problems that run in O(log log log n) rounds (where n is the size of the clique). Our results improve by an exponential factor on the long-standing (deterministic) time bound of O(log log n) rounds for these problems due to (SICOMP 2005). Our algorithms make use of several algorithmic tools including graph sketching, random sampling, and fast sorting. The second contribution of this paper is to present several almost-tight bounds on the message complexity of these problems. Specifically, we show that Ω(n2) messages are needed by any algorithm (including randomized Monte Carlo algorithms, and regardless of the number of rounds) that solves the GC (and hence also the MST) problem if each machine in the Congested Clique has initial knowledge only of itself (the so-called KT0 model). In contrast, if the machines have initial knowledge of their neighbors' IDs (the so-called KT1 model), we present a randomized Monte Carlo algorithm for MST that uses O(n polylog n) messages and runs in O(polylog n) rounds. To complement this, we also present a lower bound in the KT1 model that shows that Ω(n) messages are required by any algorithm that solves GC, regardless of the number of rounds used. Our results are a step toward understanding the power of randomization in the Congested Clique with respect to both time and message complexity. We study the broadcast version of the CONGEST CLIQUE model of distributed computing. In this model, in each round, any node in a network of size @math can send the same message (i.e. broadcast a message) of limited size to every other node in the network. Nanongkai presented in [STOC'14] a randomized @math -approximation algorithm to compute all pairs shortest paths (APSP) in time @math on weighted graphs, where we use the convention that @math is essentially @math polylog @math and @math is essentially @math polylog @math . We complement this result by proving that any randomized @math -approximation of APSP and @math -approximation of the diameter of a graph takes @math time in the worst case. This demonstrates that getting a negligible improvement in the approximation factor requires significantly more time. Furthermore this bound implies that already computing a @math -approximation of all pairs shortest paths is among the hardest graph-problems in the broadcast-version of the CONGEST CLIQUE model and contrasts a recent @math -approximation for APSP that runs in time @math in the unicast version of the CONGEST CLIQUE model. On the positive side we provide a deterministic version of Nanongkai's @math -approximation algorithm for APSP. To do so we present a fast deterministic construction of small hitting sets. We also show how to replace another randomized part within Nanongkai's algorithm with a deterministic source-detection algorithm designed for the CONGEST model presented by Lenzen and Peleg at PODC'13. In the distributed all-pairs shortest paths problem (APSP), every node in the weighted undirected distributed network (the CONGEST model) needs to know the distance from every other node using least number of communication rounds (typically called time complexity ). The problem admits @math -approximation @math -time algorithm and a nearly-tight @math lower bound [Nanongkai, STOC'14; Lenzen and Patt-Shamir PODC'15] @math , @math and @math hide polylogarithmic factors. Note that the lower bounds also hold even in the unweighted case and in the weighted case with polynomial approximation ratios LenzenP_podc13,HolzerW12,PelegRT12,Nanongkai-STOC14 . . For the exact case, Elkin [STOC'17] presented an @math time bound, which was later improved to @math [Huang, Nanongkai, Saranurak FOCS'17]. It was shown that any super-linear lower bound (in @math ) requires a new technique [Censor-Hillel, Khoury, Paz, DISC'17], but otherwise it remained widely open whether there exists a @math -time algorithm for the exact case, which would match the best possible approximation algorithm. This paper resolves this question positively: we present a randomized (Las Vegas) @math -time algorithm, matching the lower bound up to polylogarithmic factors. Like the previous @math bound, our result works for directed graphs with zero (and even negative) edge weights. In addition to the improved running time, our algorithm works in a more general setting than that required by the previous @math bound; in our setting (i) the communication is only along edge directions (as opposed to bidirectional), and (ii) edge weights are arbitrary (as opposed to integers in 1, 2, ... poly(n) ). ... 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.