2026-08-17T07:43:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9826 2024-03-06T10:45:01Z ddc:004 open_access

Broadcast and Minimum Spanning Tree with o(m) Messages in the Asynchronous CONGEST Model Mashreghi, Ali King, Valerie Distributed Computing Minimum Spanning Tree Broadcast Tree 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 Omega(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 neighbors' identities it is possible to construct MST in 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 were 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 O~(n) messages. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ali Mashreghi and Valerie King 2018 Is Part Of LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2018.37 urn:nbn:de:0030-drops-98263 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.37 eng https://creativecommons.org/licenses/by/3.0/legalcode