Broadcast and minimum spanning tree with o ( m ) messages in the asynchronous CONGEST model
2021
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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
29
References
0
Citations
NaN
KQI