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

Standard

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

Harvard

Pandurangan, G, Robinson, P & Scquizzato, M 2017, A time- and message-optimal distributed algorithm for minimum spanning trees. in STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery (ACM), New York, pp. 743-756. https://doi.org/10.1145/3055399.3055449

APA

Pandurangan, G., Robinson, P., & Scquizzato, M. (2017). A time- and message-optimal distributed algorithm for minimum spanning trees. In STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (pp. 743-756). Association for Computing Machinery (ACM). https://doi.org/10.1145/3055399.3055449

Vancouver

Pandurangan G, Robinson P, Scquizzato M. A time- and message-optimal distributed algorithm for minimum spanning trees. In 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 https://doi.org/10.1145/3055399.3055449

Author

Pandurangan, Gopal ; Robinson, Peter ; Scquizzato, Michele. / A time- and message-optimal distributed algorithm for minimum spanning trees. STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. New York : Association for Computing Machinery (ACM), 2017. pp. 743-756

BibTeX

@inproceedings{d9ac5eb0008445d180ad023adfcbf315,
title = "A time- and message-optimal distributed algorithm for minimum spanning trees",
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 {\~A}•(D + {\^a}ˆ{\v s}n) time and exchanges {\~A}•(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 {\^I}{\textcopyright}(D + {\^a}ˆ{\v s}n) [Elkin, SIAM J. Comput. 2006] and the message lower bound of {\^I}{\textcopyright}(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 {\^I}{\textcopyright}(D + {\^a}ˆ{\v s}n) rounds and {\^I}{\textcopyright}(m) messages.",
author = "Gopal Pandurangan and Peter Robinson and Michele Scquizzato",
year = "2017",
month = jun,
day = "19",
doi = "10.1145/3055399.3055449",
language = "English",
pages = "743--756",
booktitle = "STOC 2017",
publisher = "Association for Computing Machinery (ACM)",
address = "United States",

}

RIS

TY - GEN

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

AU - Pandurangan, Gopal

AU - Robinson, Peter

AU - Scquizzato, Michele

PY - 2017/6/19

Y1 - 2017/6/19

N2 - 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.

AB - 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.

U2 - 10.1145/3055399.3055449

DO - 10.1145/3055399.3055449

M3 - Conference contribution

SP - 743

EP - 756

BT - STOC 2017

PB - Association for Computing Machinery (ACM)

CY - New York

ER -