2016/07/22 by Gopal Pandurangan, Pandurangan, Gopal, Peter M. Robinson +3
Computer Science · #Complexity and Algorithms in Graphs #Cooperative Communication and Network Coding #Data Structures and Algorithms (cs.DS) #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1607.06883
openalex publication_date 2016/07/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper presents a randomized Las Vegas distributed algorithm that\nconstructs a minimum spanning tree (MST) in weighted networks with optimal (up\nto polylogarithmic factors) time and message complexity. This algorithm runs in\n\O(D + \√(n)) time and exchanges \O(m) messages (both with\nhigh probability), where n is the number of nodes of the network, D is the\ndiameter, and m is the number of edges. This is the first distributed MST\nalgorithm that matches \simultaneously the time lower bound of\n\\Ω(D + \√(n)) [Elkin, SIAM J. Comput. 2006] and the message\nlower bound of \Ω(m) [Kutten et al., J.ACM 2015] (which both apply to\nrandomized algorithms).\n The prior time and message lower bounds are derived using two completely\ndifferent graph constructions; the existing lower bound construction that shows\none lower bound em does not work for the other. To complement our algorithm,\nwe present a new lower bound graph construction for which any distributed MST\nalgorithm requires \both \\Ω(D + \√(n)) rounds and\n\Ω(m) messages.\n