Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model. (English) Zbl 1522.68733
Summary: 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.
MSC:
| 68W15 | Distributed algorithms |
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | 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) |
| [2] | Awerbuch, B., Complexity of network synchronization, J ACM, 32, 4, 804-823 (1985) · Zbl 0628.68045 · doi:10.1145/4221.4227 |
| [3] | 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) |
| [4] | Awerbuch, B.; Goldreich, O.; Vainish, R., On the Message Complexity of Broadcast: A Basic Lower Bound (1987), Cambridge: Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge |
| [5] | 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) · Zbl 0696.68020 · doi:10.1145/77600.77618 |
| [6] | 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) · doi:10.1109/TDSC.2007.1007 |
| [7] | 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) |
| [8] | 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) |
| [9] | 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) · Zbl 1317.68016 |
| [10] | 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) · Zbl 1116.05077 · doi:10.1137/S0097539704441058 |
| [11] | Elkin, M.: Synchronizers, spanners. In: Kao, Ming-Yang (ed) Encyclopedia of Algorithms, pp. 1-99. Springer (2008) |
| [12] | 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). doi:10.1145/3055399.3055452 · Zbl 1369.68344 |
| [13] | Elkin, M.: A simple deterministic distributed mst algorithm, with near-optimal time and message complexities. arXiv preprint arXiv:1703.02411 (2017) · Zbl 1380.68421 |
| [14] | 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) · Zbl 1315.68149 |
| [15] | 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) · Zbl 1373.68447 |
| [16] | 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) |
| [17] | Gallager, RG; Humblet, PA; Spira, PM, A distributed algorithm for minimum-weight spanning trees, ACM Trans. Program. Lang. Syst., 5, 1, 66-77 (1983) · Zbl 0498.68040 · doi:10.1145/357195.357200 |
| [18] | Garay, JA; Kutten, S.; Peleg, D., A sublinear time distributed algorithm for minimum-weight spanning trees, SIAM J. Comput., 27, 1, 302-316 (1998) · Zbl 0911.05052 · doi:10.1137/S0097539794261118 |
| [19] | 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). doi:10.4230/LIPIcs.DISC.2018.30. http://drops.dagstuhl.de/opus/volltexte/2018/9819 · Zbl 1497.68564 |
| [20] | 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). doi:10.4230/LIPIcs.DISC.2018.32. http://drops.dagstuhl.de/opus/volltexte/2018/9821 · Zbl 1497.68565 |
| [21] | 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) · Zbl 1423.68345 |
| [22] | 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) · Zbl 1333.68213 |
| [23] | Kutten, S.; Pandurangan, G.; Peleg, D.; Robinson, P.; Trehan, A., On the complexity of leader election, J. ACM, 62, 1, 7 (2015) · Zbl 1321.68285 · doi:10.1145/2699440 |
| [24] | 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) · Zbl 1376.68161 |
| [25] | 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) |
| [26] | 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) |
| [27] | Mashreghi, A., King, V.: Faster asynchronous mst and low diameter tree construction with sublinear communication. arXiv preprint arXiv:1907.12152 (2019) |
| [28] | 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) · Zbl 1370.68319 |
| [29] | 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) · Zbl 0973.05074 · doi:10.1137/S0097539700369740 |
| [30] | 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) · Zbl 0681.68091 |
| [31] | Sarma, AD; 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) · Zbl 1259.68227 · doi:10.1137/11085178X |
| [32] | Singh, G.; Bernstein, AJ, A highly asynchronous minimum spanning tree protocol, Distrib. Comput., 8, 3, 151-161 (1995) · Zbl 1448.68475 · doi:10.1007/BF02242717 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
