research-article

Public Access

A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees

Authors:

Gopal Pandurangan,

Peter Robinson,

Michele ScquizzatoAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 16, Issue 1

Article No.: 13, Pages 1 - 27

https://doi.org/10.1145/3365005

Published: 15 November 2019 Publication History

All formats PDF

Abstract

This article 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 hop-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) [10] and the message lower bound of Ω (m) [31], 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.

References

[1]

Hagit Attiya and Jennifer Welch. 1998. Distributed Computing: Fundamentals, Simulations and Advanced Topics. McGraw-Hill, Inc.

Digital Library

[2]

Baruch Awerbuch. 1987. Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems. In Proceedings of the 19th ACM Symposium on Theory of Computing (STOC). 230--240.

Digital Library

[3]

Baruch Awerbuch, Oded Goldreich, David Peleg, and Ronen Vainish. 1990. A trade-off between information and communication in broadcast protocols. J. ACM 37, 2 (1990), 238--256.

Digital Library

[4]

Baruch Awerbuch and David Peleg. 1990. Sparse partitions. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science (FOCS). 503--513.

Digital Library

[5]

Francis Chin and H. F. Ting. 1985. An almost linear time and O(n log n + e) messages distributed algorithm for minimum-weight spanning trees. In Proceedings of the 26th IEEE Symposium on Foundations of Computer Science (FOCS). 257--266.

[6]

Richard Cole and Uzi Vishkin. 1986. Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing (STOC). 206--219.

Digital Library

[7]

Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. 2012. Distributed verification and hardness of distributed approximation. SIAM J. Comput. 41, 5 (2012), 1235--1265.

Digital Library

[8]

Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan, and Prasad Tetali. 2013. Distributed random walks. J. ACM 60, 1, Article 2 (2013).

[9]

Michael Elkin. 2006. A faster distributed protocol for constructing a minimum spanning tree. J. Comput. Syst. Sci. 72, 8 (2006), 1282--1308.

Digital Library

[10]

Michael Elkin. 2006. An unconditional lower bound on the time-approximation trade-off for the distributed minimum spanning tree problem. SIAM J. Comput. 36, 2 (2006), 433--456.

Digital Library

[11]

Michael Elkin. 2017. A simple deterministic distributed MST algorithm, with near-optimal time and message complexities. In Proceedings of the 2017 ACM Symposium on Principles of Distributed Computing (PODC). 157--163.

Digital Library

[12]

Michalis Faloutsos and Mart Molle. 2004. A linear-time optimal-message distributed algorithm for minimum spanning trees. Distributed Computing 17, 2 (2004), 151--170.

Digital Library

[13]

Eli Gafni. 1985. Improvements in the time complexity of two message-optimal election algorithms. In Proceedings of the 4th Symposium on Principles of Distributed Computing (PODC). 175--185.

Digital Library

[14]

Robert G. Gallager, Pierre A. Humblet, and Philip M. Spira. 1983. A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst. 5, 1 (1983), 66--77.

Digital Library

[15]

Juan A. Garay, Shay Kutten, and David Peleg. 1998. A sublinear time distributed algorithm for minimum-weight spanning trees. SIAM J. Comput. 27, 1 (1998), 302--316.

Digital Library

[16]

Mohsen Ghaffari and Bernhard Haeupler. 2016. Distributed algorithms for planar networks II: Low-congestion shortcuts, MST, and min-cut. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 202--219.

Digital Library

[17]

Mohsen Ghaffari and Fabian Kuhn. 2018. Distributed MST and broadcast with fewer messages, and faster gossiping. In Proceedings of the 32nd International Symposium on Distributed Computing (DISC). 30:1--30:12.

[18]

Mohsen Ghaffari, Fabian Kuhn, and Hsin-Hao Su. 2017. Distributed MST and routing in almost mixing time. In Proceedings of the 2017 ACM Symposium on Principles of Distributed Computing (PODC). 131--140.

Digital Library

[19]

Robert Gmyr and Gopal Pandurangan. 2018. Time-message trade-offs in distributed algorithms. In Proceedings of the 32nd International Symposium on Distributed Computing (DISC). 32:1--32:18.

[20]

Bernhard Haeupler, D. Ellis Hershkowitz, and David Wajc. 2018. Round- and message-optimal distributed graph algorithms. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC). 119--128.

Digital Library

[21]

Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. 2016. Low-congestion shortcuts without embedding. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC). 451--460.

Digital Library

[22]

Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. 2016. Near-optimal low-congestion shortcuts on bounded parameter graphs. In Proceedings of the 30th International Symposium on Distributed Computing (DISC). 158--172.

[23]

James W. Hegeman, Gopal Pandurangan, Sriram V. Pemmaraju, Vivek B. Sardeshmukh, and Michele Scquizzato. 2015. Toward optimal bounds in the congested clique: Graph connectivity and MST. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC). 91--100.

Digital Library

[24]

Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. 2016. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In Proceedings of the 48th ACM Symposium on Theory of Computing (STOC). 489--498.

Digital Library

[25]

Maleq Khan and Gopal Pandurangan. 2008. A fast distributed approximation algorithm for minimum spanning trees. Distributed Computing 20, 6 (2008), 391--402.

[26]

Valerie King, Shay Kutten, and Mikkel Thorup. 2015. Construction and impromptu repair of an MST in a distributed network with o(m) communication. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC). 71--80.

Digital Library

[27]

Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan, and Peter Robinson. 2015. Distributed computation of large-scale graph problems. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 391--410.

Digital Library

[28]

Liah Kor, Amos Korman, and David Peleg. 2013. Tight bounds for distributed minimum-weight spanning tree verification. Theory Comput. Syst. 53, 2 (2013), 318--340.

[29]

Eyal Kushilevitz and Noam Nisan. 1997. Communication Complexity. Cambridge University Press.

Digital Library

[30]

Shay Kutten, Danupon Nanongkai, Gopal Pandurangan, and Peter Robinson. 2014. Distributed symmetry breaking in hypergraphs. In Proceedings of the 28th International Symposium on Distributed Computing (DISC). 469--483.

[31]

Shay Kutten, Gopal Pandurangan, David Peleg, Peter Robinson, and Amitabh Trehan. 2015. On the complexity of universal leader election. J. ACM 62, 1, Article 7 (2015).

Digital Library

[32]

Shay Kutten and David Peleg. 1998. Fast distributed construction of small k-dominating sets and applications. J. Algorithms 28, 1 (1998), 40--66.

Digital Library

[33]

Christoph Lenzen. 2016. Lecture Notes on Theory of Distributed Systems. https://www.mpi-inf.mpg.de/fileadmin/inf/d1/teaching/winter15/tods/ToDS.pdf.

[34]

Christoph Lenzen and Boaz Patt-Shamir. 2014. Improved distributed steiner forest construction. In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing (PODC). 262--271.

Digital Library

[35]

Nancy Lynch. 1996. Distributed Algorithms. Morgan Kaufmann Publishers.

Digital Library

[36]

Ali Mashreghi and Valerie King. 2017. Time-communication trade-offs for minimum spanning tree construction. In Proceedings of the 18th International Conference on Distributed Computing and Networking (ICDCN). Article 8.

Digital Library

[37]

Danupon Nanongkai. 2014. Distributed approximation algorithms for weighted shortest paths. In Proceedings of the 46th ACM Symposium on Theory of Computing (STOC). 565--573.

Digital Library

[38]

Danupon Nanongkai, Atish Das Sarma, and Gopal Pandurangan. 2011. A tight unconditional lower bound on distributed randomwalk computation. In Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing (PODC). 257--266.

Digital Library

[39]

Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, Talal Riaz, and Peter Robinson. 2017. Symmetry breaking in the Congest model: Time- and message-efficient algorithms for ruling sets. In Proceedings of the 31st International Symposium on Distributed Computing (DISC). 38:1--38:16.

Digital Library

[40]

Gopal Pandurangan. 2019. Distributed Network Algorithms. https://sites.google.com/site/gopalpandurangan/dna.

[41]

Gopal Pandurangan, David Peleg, and Michele Scquizzato. 2016. Message lower bounds via efficient network synchronization. In Proceedings of the 23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO). 75--91.

[42]

Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. 2017. A time- and message-optimal distributed algorithm for minimum spanning trees. In Proceedings of the 49th Annual ACM Symposium on the Theory of Computing (STOC). 743--756.

Digital Library

[43]

Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. 2018. The distributed minimum spanning tree problem. Bulletin of the EATCS 125 (2018).

[44]

David Peleg. 1998. Distributed matroid basis completion via elimination upcast and distributed correction of minimum-weight spanning trees. In Proceedings of the 25th International Colloquium on Automata, Languages and Programming (ICALP). 164--175.

Digital Library

[45]

David Peleg. 2000. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics.

[46]

David Peleg and Vitaly Rubinovich. 2000. A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction. SIAM J. Comput. 30, 5 (2000), 1427--1442.

Digital Library

[47]

Alexander A. Razborov. 1992. On the distributional complexity of disjointness. Theor. Comput. Sci. 106, 2 (1992), 385--390.

[48]

Robert Endre Tarjan. 1983. Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics.

[49]

Gerard Tel. 1994. Introduction to Distributed Algorithms. Cambridge University Press.

[50]

Andrew Chi-Chih Yao. 1977. Probabilistic computations: Toward a unified measure of complexity. In Proceedings of the 18th Annual Symposium on Foundations of Computer Science (FOCS). 222--227.

Cited By

Augustine JGilbert SKuhn FRobinson PSourav S(2022)Latency, capacity, and distributed minimum spanning treesJournal of Computer and System Sciences10.1016/j.jcss.2021.11.006126:C(1-20)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1016/j.jcss.2021.11.006
Baniata HAnaqreh AKertesz A(2021)DONS: Dynamic optimized neighbor selection for smart blockchain networksFuture Generation Computer Systems10.1016/j.future.2021.12.010Online publication date: Dec-2021
https://doi.org/10.1016/j.future.2021.12.010

Index Terms

A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees
1. Theory of computation
  1. Design and analysis of algorithms
    1. Distributed algorithms

Recommendations

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

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 ...
Balancing minimum spanning trees and shortest-path trees

We give a simple algorithm to find a spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree. The algorithm provides a continuous tradeoff: given the two trees and aź>0, the algorithm returns a spanning tree in ...
Distributed verification of minimum spanning trees
PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing

The problem of verifying a Minimum Spanning Tree (MST) was introduced by Tarjan in a sequential setting. Given a graph and a tree that spans it, the algorithm is required to check whether this tree is an MST. This paper investigates the problem in the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 16, Issue 1

Special Issue on Soda'18 and Regular Papers

January 2020

369 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/3372373

Editor:
Aravind Srinivasan
University of Maryland, USA

Issue’s Table of Contents

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 November 2019

Accepted: 01 September 2019

Revised: 01 August 2019

Received: 01 March 2018

Published in TALG Volume 16, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

US-Israel Binational Science Foundation (BSF)
European Research Council (ERC)
NSF
European Union's Horizon 2020 research and innovation programme

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
1,033
Total Downloads

Downloads (Last 12 months)194
Downloads (Last 6 weeks)31

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Augustine JGilbert SKuhn FRobinson PSourav S(2022)Latency, capacity, and distributed minimum spanning treesJournal of Computer and System Sciences10.1016/j.jcss.2021.11.006126:C(1-20)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1016/j.jcss.2021.11.006
Baniata HAnaqreh AKertesz A(2021)DONS: Dynamic optimized neighbor selection for smart blockchain networksFuture Generation Computer Systems10.1016/j.future.2021.12.010Online publication date: Dec-2021
https://doi.org/10.1016/j.future.2021.12.010

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents