LIPIcs.DISC.2019.49.pdf
- Filesize: 317 kB
- 3 pages
Document
Brief Announcement: Faster Asynchronous MST and Low Diameter Tree Construction with Sublinear Communication
Authors
-
Part of:
Volume:
33rd International Symposium on Distributed Computing (DISC 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Distributed Computing (DISC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-10-08
Cite As Get BibTex
Ali Mashreghi and Valerie King. Brief Announcement: Faster Asynchronous MST and Low Diameter Tree Construction with Sublinear Communication. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 49:1-49:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.DISC.2019.49
Abstract
Building a spanning tree, minimum spanning tree (MST), and BFS tree in a distributed network are fundamental problems which are still not fully understood in terms of time and communication cost. The first work to succeed in computing a spanning tree with communication sublinear in the number of edges in an asynchronous CONGEST network appeared in DISC 2018. That algorithm which constructs an MST is sequential in the worst case; its running time is proportional to the total number of messages sent. Our paper matches its message complexity but brings the running time down to linear in n. Our techniques can also be used to provide an asynchronous algorithm with sublinear communication to construct a tree in which the distance from a source to each node is within an additive term of sqrt{n} of its actual distance.
Subject Classification
ACM Subject Classification
- Theory of computation → Distributed computing models
Keywords
- Distributed Computing
- Minimum Spanning Tree
- Broadcast Tree
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Baruch Awerbuch. Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems. In STOC, pages 230-240, 1987.
-
Baruch Awerbuch, Oded Goldreich, Ronen Vainish, and David Peleg. A trade-off between information and communication in broadcast protocols. Journal of the ACM, 37(2):238-256, 1990.
-
R.G. Gallager. Distributed minimum hop algorithms. Technical Report LIDS-P-1175, MIT Laboratory for Information and Decision Systems, 1982.
-
Mohsen Ghaffari and Fabian Kuhn. Distributed MST and Broadcast with Fewer Messages, and Faster Gossiping. In DISC, pages 30:1-30:12, 2018.
-
Valerie King, Shay Kutten, and Mikkel Thorup. Construction and impromptu repair of an MST in a distributed network with o(m) communication. In PODC, pages 71-80, 2015.
-
Ali Mashreghi and Valerie King. Broadcast and Minimum Spanning Tree with o(m) Messages in the Asynchronous CONGEST Model. In DISC, volume 121, pages 37:1-37:17, 2018.
- Ali Mashreghi and Valerie King. Faster asynchronous MST and low diameter tree construction with sublinear communication. arXiv e-prints, July 2019. URL: http://arxiv.org/abs/1907.12152.
-
David Peleg. Distributed computing. SIAM Monographs on discrete mathematics and applications, 5, 2000.