## Abstract

This paper presents a randomized (Las Vegas) distributed algorithm that constructs a minimum spanning tree (MST) in weighted networks with optimal (up to polylogarithmic factors) time and message complexity. This algorithm runs in Ã•(D + âˆšn) time and exchanges Ã•(m) messages (both with high probability), where n is the number of nodes of the network, D is the diameter, and m is the number of edges. This is the first distributed MST algorithm that matches simultaneously the time lower bound of Î©(D + âˆšn) [Elkin, SIAM J. Comput. 2006] and the message lower bound of Î©(m) [Kutten et al., J. ACM 2015], which both apply to randomized Monte Carlo algorithms.

The prior time and message lower bounds are derived using two completely different graph constructions; the existing lower bound construction that shows one lower bound does not work for the other. To complement our algorithm, we present a new lower bound graph construction for which any distributed MST algorithm requires both Î©(D + âˆšn) rounds and Î©(m) messages.

The prior time and message lower bounds are derived using two completely different graph constructions; the existing lower bound construction that shows one lower bound does not work for the other. To complement our algorithm, we present a new lower bound graph construction for which any distributed MST algorithm requires both Î©(D + âˆšn) rounds and Î©(m) messages.

Original language | English |
---|---|

Title of host publication | STOC 2017 |

Subtitle of host publication | Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing |

Place of Publication | New York |

Publisher | Association for Computing Machinery (ACM) |

Pages | 743-756 |

Number of pages | 14 |

ISBN (Electronic) | 978-1-4503-4528-6 |

DOIs | |

Publication status | Published - 19 Jun 2017 |