Abstract
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 Õ(D + √n) time and exchanges Õ(m) messages (both with high probability), where n is the number of nodes of the network, D is the diameter, and m is the number of edges. This is the first distributed MST algorithm that matches simultaneously the time lower bound of Ω(D + √n) [Elkin, SIAM J. Comput. 2006] and the message lower bound of Ω(m) [Kutten et al., J. ACM 2015], which both apply to randomized Monte Carlo 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 both Ω(D + √n) rounds and Ω(m) messages.
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 both Ω(D + √n) rounds and Ω(m) messages.
| Original language | English |
|---|---|
| Title of host publication | STOC 2017 |
| Subtitle of host publication | Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing |
| Place of Publication | New York |
| Publisher | Association for Computing Machinery (ACM) |
| Pages | 743-756 |
| Number of pages | 14 |
| ISBN (Electronic) | 978-1-4503-4528-6 |
| DOIs | |
| Publication status | Published - 19 Jun 2017 |