Abstract
We provide the first asynchronous distributed algorithms to compute broadcast and minimum spanning tree with o(m) bits of communication, in a sufficiently dense graph with n nodes and m edges. For decades, it was believed that \(\varOmega (m)\) bits of communication are required for any algorithm that constructs a broadcast tree. In 2015, King, Kutten and Thorup showed that in the KT1 model where nodes have initial knowledge of their neighbours’ identities it is possible to construct MST in \({\tilde{O}}(n)\) messages in the synchronous CONGEST model. In the CONGEST model messages are of size \(O(\log n)\). However, no algorithm with o(m) messages was known for the asynchronous case. Here, we provide an algorithm that uses \(O(n^{3/2} \log ^{3/2} n)\) messages to find MST in the asynchronous CONGEST model. Our algorithm is randomized Monte Carlo and outputs MST with high probability. We will provide an algorithm for computing a spanning tree with \(O(n^{3/2} \log ^{3/2} n)\) messages. Given a spanning tree, we can compute MST with \({\tilde{O}}(n)\) messages.
Similar content being viewed by others
References
Ahn, K.J., Guha, S., McGregor, A.: Graph sketches: sparsification, spanners, and subgraphs. In: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pp. 5–14. ACM (2012)
Awerbuch, B.: Complexity of network synchronization. J ACM 32(4), 804–823 (1985)
Awerbuch, B.: Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of computing, pp. 230–240. ACM (1987)
Awerbuch, B., Goldreich, O., Vainish, R.: On the Message Complexity of Broadcast: A Basic Lower Bound. Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge (1987)
Awerbuch, B., Goldreich, O., Vainish, R., Peleg, D.: A trade-off between information and communication in broadcast protocols. J ACM 37(2), 238–256 (1990)
Awerbuch, B., Kutten, S., Mansour, Y., Patt-Shamir, B., Varghese, G.: A time-optimal self-stabilizing synchronizer using a phase clock. IEEE Trans Dependable Secure Comput 4(3), 180–190 (2007)
Awerbuch, B., Peleg, D.: Network synchronization with polylogarithmic overhead. In: 31st Annual Symposium on Foundations of Computer Science, 1990. Proceedings., pp. 514–522. IEEE (1990)
Chin, F., Ting, H.: An almost linear time and o (nlogn+ e) messages distributed algorithm for minimum-weight spanning trees. In: 26th Annual Symposium on Foundations of Computer Science, pp. 257–266. IEEE (1985)
Elkin, M.: A faster distributed protocol for constructing a minimum spanning tree. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 359–368. Society for Industrial and Applied Mathematics (2004)
Elkin, M.: An unconditional lower bound on the time-approximation trade-off for the distributed minimum spanning tree problem. SIAM J. Comput. 36(2), 433–456 (2006)
Elkin, M.: Synchronizers, spanners. In: Kao, Ming-Yang (ed) Encyclopedia of Algorithms, pp. 1–99. Springer (2008)
Elkin, M.: Distributed exact shortest paths in sublinear time. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pp. 757–770. ACM, New York, NY, USA (2017). https://doi.org/10.1145/3055399.3055452
Elkin, M.: A simple deterministic distributed mst algorithm, with near-optimal time and message complexities. arXiv preprint arXiv:1703.02411 (2017)
Emek, Y., Korman, A.: Efficient threshold detection in a distributed environment. In: Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp. 183–191. ACM (2010)
Faloutsos, M., Molle, M.: Optimal distributed algorithm for minimum spanning trees revisited. In: Proceedings of the Fourteenth Annual ACM Symposium on Principles of DistributCd computing, pp. 231–237. ACM (1995)
Gafni, E.: Improvements in the time complexity of two message-optimal election algorithms. In: Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, pp. 175–185. ACM (1985)
Gallager, R.G., Humblet, P.A., Spira, P.M.: A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst. 5(1), 66–77 (1983)
Garay, J.A., Kutten, S., Peleg, D.: A sublinear time distributed algorithm for minimum-weight spanning trees. SIAM J. Comput. 27(1), 302–316 (1998)
Ghaffari, M., Kuhn, F.: Distributed MST and broadcast with fewer messages, and faster gossiping. In: Schmid, U., Widder, J. (eds.) 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), vol. 121, pp. 30:1–30:12. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018). https://doi.org/10.4230/LIPIcs.DISC.2018.30. http://drops.dagstuhl.de/opus/volltexte/2018/9819
Gmyr, R., Pandurangan, G.: Time-Message Trade-Offs in Distributed Algorithms. In: Schmid, U., Widder , J. (eds.) 32nd International Symposium on Distributed Computing (DISC 2018), Leibniz International Proceedings in Informatics (LIPIcs), vol. 121, pp. 32:1–32:18. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018). https://doi.org/10.4230/LIPIcs.DISC.2018.32. http://drops.dagstuhl.de/opus/volltexte/2018/9821
Kapron, B.M., King, V., Mountjoy, B.: Dynamic graph connectivity in polylogarithmic worst case time. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1131–1142. Society for Industrial and Applied Mathematics (2013)
King, V., Kutten, S., Thorup, M.: 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, pp. 71–80. ACM (2015)
Kutten, S., Pandurangan, G., Peleg, D., Robinson, P., Trehan, A.: On the complexity of leader election. J. ACM 62(1), 7 (2015)
Kutten, S., Peleg, D.: Fast distributed construction of k-dominating sets and applications. In: Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, pp. 238–251. ACM (1995)
Mashreghi, A., King, V.: Time-communication trade-offs for minimum spanning tree construction. In: Proceedings of the 18th International Conference on Distributed Computing and Networking, p. 8. ACM (2017)
Mashreghi, A., King, V.: Brief announcement: faster asynchronous mst and low diameter tree construction with sublinear communication. In: 33rd International Symposium on Distributed Computing (DISC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2019)
Mashreghi, A., King, V.: Faster asynchronous mst and low diameter tree construction with sublinear communication. arXiv preprint arXiv:1907.12152 (2019)
Pandurangan, G., Robinson, P., Scquizzato, M.: 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. ACM (2017)
Peleg, D., Rubinovich, V.: A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction. SIAM J. Comput. 30(5), 1427–1442 (2000). https://doi.org/10.1137/S0097539700369740
Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. In: Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, pp. 77–85. ACM (1987)
Sarma, A.D., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. SIAM J. Comput. 41(5), 1235–1265 (2012)
Singh, G., Bernstein, A.J.: A highly asynchronous minimum spanning tree protocol. Distrib. Comput. 8(3), 151–161 (1995)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Funded with an NSERC Grant.
Rights and permissions
About this article
Cite this article
Mashreghi, A., King, V. Broadcast and minimum spanning tree with o(m) messages in the asynchronous CONGEST model . Distrib. Comput. 34, 283–299 (2021). https://doi.org/10.1007/s00446-020-00387-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00446-020-00387-y