A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees. / Pandurangan, Gopal; Robinson, Peter; Scquizzato, Michele.

STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. New York : Association for Computing Machinery (ACM), 2017. p. 743-756.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Published

Documents

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.
Original languageEnglish
Title of host publicationSTOC 2017
Subtitle of host publicationProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
Place of PublicationNew York
PublisherAssociation for Computing Machinery (ACM)
Pages743-756
Number of pages14
ISBN (Electronic)978-1-4503-4528-6
DOIs
StatePublished - 19 Jun 2017
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 27814589