Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication
Valerie Jean King, Shay Kutten, Mikkel Thorup · 2015
In the CONGEST model, a communications network is an undirected graph whose n nodes are processors and whose m edges are the communications links between processors. At any given time step, a message of size O(log n) may be sent by each node to each of its neighbours. We show for the synchronous model: If all nodes start in the same round, and each node knows its ID and the ID's of its neighbors, or in the case of MST, the distinct weights of its incident edges and knows n, then there are Monte Carlo algorithms which succeed w.h.p. to determine a minimum spanning forest (MST) and a spanning forest (ST) using O(n log2 n/log log n) messages for MST and O(n log n) messages for ST, resp. These results contradict the "folk theorem" noted in Awerbuch, et.al., JACM 1990 that the distributed construction of a broadcast tree requires Ω(m) messages. This lower bound has been shown there and in other papers for some CONGEST models; our protocol demonstrates the limits of these models.