A time- and message-optimal distributed algorithm for minimum spanning trees

Gopal Pandurangan, Peter Robinson, Michele Scquizzato

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

46 Downloads (Pure)

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
Publication statusPublished - 19 Jun 2017

Cite this