Document Open Access Logo

Distributed MST and Broadcast with Fewer Messages, and Faster Gossiping

Authors Mohsen Ghaffari, Fabian Kuhn

PDF
Thumbnail PDF

File

LIPIcs.DISC.2018.30.pdf
  • Filesize: 333 kB
  • 12 pages

Document Identifiers

Author Details

Mohsen Ghaffari
  • ETH Zurich, Switzerland
Fabian Kuhn
  • University of Freiburg, Germany

Cite AsGet BibTex

Mohsen Ghaffari and Fabian Kuhn. Distributed MST and Broadcast with Fewer Messages, and Faster Gossiping. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 30:1-30:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.DISC.2018.30

Abstract

We present a distributed minimum spanning tree algorithm with near-optimal round complexity of O~(D+sqrt{n}) and message complexity O~(min{n^{3/2}, m}). This is the first algorithm with sublinear message complexity and near-optimal round complexity and it improves over the recent algorithms of Elkin [PODC'17] and Pandurangan et al. [STOC'17], which have the same round complexity but message complexity O~(m). Our method also gives the first broadcast algorithm with o(n) time complexity - when that is possible at all, i.e., when D=o(n) - and o(m) messages. Moreover, our method leads to an O~(sqrt{nD})-round GOSSIP algorithm with bounded-size messages. This is the first such algorithm with a sublinear round complexity.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Distributed Algorithms
  • Minimum Spanning Tree
  • Round Complexity
  • Message Complexity
  • Gossiping
  • Broadcast

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Graph sketches: sparsification, spanners, and subgraphs. In Proceedings of the 31st symposium on Principles of Database Systems, pages 5-14. ACM, 2012. Google Scholar
  2. Baruch Awerbuch. Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems. In Proc. of the Symp. on Theory of Comp. (STOC), pages 230-240. ACM, 1987. Google Scholar
  3. Baruch Awerbuch, Oded Goldreich, Ronen Vainish, and David Peleg. A trade-off between information and communication in broadcast protocols. Journal of the ACM (JACM), 37(2):238-256, 1990. Google Scholar
  4. Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen. Near-optimal approximate shortest paths and transshipment in distributed and streaming models. In LIPIcs-Leibniz International Proceedings in Informatics, volume 91. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  5. Keren Censor-Hillel, Bernhard Haeupler, Jonathan Kelner, and Petar Maymounkov. Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 961-970. ACM, 2012. Google Scholar
  6. F Chin and HF Ting. An almost linear time and O(nlogn+ e) messages distributed algorithm for minimum-weight spanning trees. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS), pages 257-266. IEEE, 1985. Google Scholar
  7. Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. Distributed verification and hardness of distributed approximation. In Proc. of the Symp. on Theory of Comp. (STOC), pages 363-372, 2011. Google Scholar
  8. Michael Elkin. Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem. In Proc. of the Symp. on Theory of Comp. (STOC), pages 331-340, 2004. Google Scholar
  9. Michael Elkin. A simple deterministic distributed mst algorithm, with near-optimal time and message complexities. In Proceedings of the ACM Symposium on Principles of Distributed Computing, pages 157-163. ACM, 2017. Google Scholar
  10. Michalis Faloutsos and Mart Molle. A linear-time optimal-message distributed algorithm for minimum spanning trees. Distributed Computing, 17(2):151-170, 2004. Google Scholar
  11. Eli Gafni. Improvements in the time complexity of two message-optimal election algorithms. In the Proc. of the Int'l Symp. on Princ. of Dist. Comp. (PODC), pages 175-185. ACM, 1985. Google Scholar
  12. Robert G. Gallager, Pierre A. Humblet, and Philip M. Spira. A distributed algorithm for minimum-weight spanning trees. ACM Transactions on Programming Languages and systems (TOPLAS), 5(1):66-77, 1983. Google Scholar
  13. J.A. Garay, S. Kutten, and D. Peleg. A sub-linear time distributed algorithm for minimum-weight spanning trees. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS), 1993. Google Scholar
  14. M. Ghaffari and F. Kuhn. Distributed minimum cut approximation. In Proc. of the Int'l Symp. on Dist. Comp. (DISC), pages 1-15, 2013. Google Scholar
  15. Mohsen Ghaffari. Near-optimal distributed approximation of minimum-weight connected dominating set. In International Colloquium on Automata, Languages, and Programming, pages 483-494. Springer, 2014. Google Scholar
  16. Mohsen Ghaffari and Bernhard Haeupler. Distributed algorithms for planar networks ii: Low-congestion shortcuts, mst, and min-cut. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 202-219. SIAM, 2016. Google Scholar
  17. Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn, Christoph Lenzen, and Boaz Patt-Shamir. Near-optimal distributed maximum flow. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pages 81-90. ACM, 2015. Google Scholar
  18. Mohsen Ghaffari, Fabian Kuhn, and Hsin-Hao Su. Distributed mst and routing in almost mixing time. In the Proc. of the Int'l Symp. on Princ. of Dist. Comp. (PODC), pages 131-140. ACM, 2017. Google Scholar
  19. Mohsen Ghaffari and Christoph Lenzen. Near-optimal distributed tree embedding. In International Symposium on Distributed Computing, pages 197-211. Springer, 2014. Google Scholar
  20. Mohsen Ghaffari and Merav Parter. Mst in log-star rounds of congested clique. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pages 19-28. ACM, 2016. Google Scholar
  21. George Giakkoupis. Tight bounds for rumor spreading in graphs of a given conductance. In Symposium on Theoretical Aspects of Computer Science (STACS2011), volume 9, pages 57-68, 2011. Google Scholar
  22. Bernhard Haeupler. Simple, fast and deterministic gossip and rumor spreading. Journal of the ACM (JACM), 62(6):47, 2015. Google Scholar
  23. James W. Hegeman, Gopal Pandurangan, Sriram V. Pemmaraju, Vivek B. Sardeshmukh, and Michele Scquizzato. Toward optimal bounds in the congested clique: Graph connectivity and MST. In the Proc. of the Int'l Symp. on Princ. of Dist. Comp. (PODC), pages 91-100. ACM, 2015. Google Scholar
  24. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 489-498. ACM, 2016. Google Scholar
  25. Tomasz Jurdziński and Krzysztof Nowicki. Mst in o (1) rounds of congested clique. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2620-2632. SIAM, 2018. Google Scholar
  26. Maleq Khan and Gopal Pandurangan. A fast distributed approximation algorithm for minimum spanning trees. Distributed Computing, 20(6):391-402, 2008. Google Scholar
  27. Valerie King, Shay Kutten, and Mikkel Thorup. 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, pages 71-80. ACM, 2015. Google Scholar
  28. Liah Kor, Amos Korman, and David Peleg. Tight bounds for distributed mst verification. In Symposium on Theoretical Aspects of Computer Science (STACS2011), volume 9, pages 57-68, 2011. Google Scholar
  29. Shay Kutten, Gopal Pandurangan, David Peleg, Peter Robinson, and Amitabh Trehan. On the complexity of universal leader election. Journal of the ACM (JACM), 62(1):7, 2015. Google Scholar
  30. Shay Kutten and David Peleg. Fast distributed construction of k-dominating sets and applications. In the Proc. of the Int'l Symp. on Princ. of Dist. Comp. (PODC), pages 238-251, 1995. Google Scholar
  31. Christoph Lenzen and Boaz Patt-Shamir. Fast routing table construction using small messages: Extended abstract. In Proc. of the Symp. on Theory of Comp. (STOC), pages 381-390, 2013. Google Scholar
  32. Ali Mashreghi and Valerie King. Time-communication trade-offs for minimum spanning tree construction. In Proceedings of the 18th International Conference on Distributed Computing and Networking, page 8. ACM, 2017. Google Scholar
  33. Danupon Nanongkai. Distributed approximation algorithms for weighted shortest paths. In Proc. of the Symp. on Theory of Comp. (STOC), 2014. Google Scholar
  34. Danupon Nanongkai and Hsin-Hao Su. Almost-tight distributed minimum cut algorithms. In International Symposium on Distributed Computing, pages 439-453. Springer, 2014. Google Scholar
  35. Jaroslav Nešetřil, Eva Milková, and Helena Nešetřilová. Otakar boruvka on minimum spanning tree problem translation of both the 1926 papers, comments, history. Discrete Mathematics, 233(1):3-36, 2001. Google Scholar
  36. Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. A time-and message-optimal distributed algorithm for minimum spanning trees. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 743-756. ACM, 2017. Google Scholar
  37. David Peleg. Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000. Google Scholar
  38. David Peleg and Vitaly Rubinovich. A near-tight lower bound on the time complexity of distributed MST construction. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS), pages 253-, 1999. Google Scholar
  39. Gurdip Singh and Arthur J Bernstein. A highly asynchronous minimum spanning tree protocol. Distributed Computing, 8(3):151-161, 1995. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact