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

Gopal Pandurangan; Peter Robinson; Michele Scquizzato

doi:10.1145/3055399.3055449

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

Gopal Pandurangan
, Peter Robinson
, Michele Scquizzato

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

48 Citations (Scopus)

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 language	English
Title of host publication	Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
Publisher	Association for Computing Machinery
Pages	743-756
ISBN (Print)	9781450345286
DOIs	https://doi.org/10.1145/3055399.3055449
Publication status	Published - 19 Jun 2017
Externally published	Yes
Event	49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017) - Montreal, Canada Duration: 19 Jun 2017 → 23 Jun 2017

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing
Volume	Part F128415
ISSN (Print)	0737-8017

Conference

Conference	49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017)
Abbreviated title	STOC 2017
Place	Canada
City	Montreal
Period	19/06/17 → 23/06/17

Research Keywords

Distributed algorithms
Minimum spanning trees

Access Output

10.1145/3055399.3055449

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

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

@inproceedings{bd0890d1303141d6b2f12d1f2b4f00b5,

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 {\~O}(D + √n) time and exchanges {\~O}(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.",

keywords = "Distributed algorithms, Minimum spanning trees",

author = "Gopal Pandurangan and Peter Robinson and Michele Scquizzato",

year = "2017",

month = jun,

day = "19",

doi = "10.1145/3055399.3055449",

language = "English",

isbn = "9781450345286",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "743--756",

booktitle = "Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing",

address = "United States",

note = "49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), STOC 2017 ; Conference date: 19-06-2017 Through 23-06-2017",

}

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

A Time- and message-optimal distributed algorithm for minimum spanning trees. / Pandurangan, Gopal; Robinson, Peter; Scquizzato, Michele.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery, 2017. p. 743-756 (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. Part F128415).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

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.

KW - Distributed algorithms

KW - Minimum spanning trees

UR - https://www.scopus.com/pages/publications/85024397813

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85024397813&origin=recordpage

U2 - 10.1145/3055399.3055449

DO - 10.1145/3055399.3055449

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9781450345286

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 743

EP - 756

BT - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing

PB - Association for Computing Machinery

T2 - 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017)

Y2 - 19 June 2017 through 23 June 2017

ER -

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

Abstract

Publication series

Conference

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this