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 log 2 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. A dynamic distributed network is one which undergoes online edge insertions or deletions. We also show how to repair an MST or ST in a dynamic network with asynchronous communication. An edge deletion can be processed in O(n log n/ log log n) expected messages in the MST, and O(n) expected messages for the ST problem, while an edge insertion uses O(n) messages in the worst case. We call this "impromptu" updating as we assume that between processing of edge updates there is no preprocessing or storage of * Research supported by Simons Institute for the Theory of Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org.
Recently, King et al. REF showed a surprising and elegant result: in the KT 1 model one can give a randomized Monte Carlo algorithm to construct an MST inÕ (n) messages (Ω(n) is a message lower bound) and inÕ (n) time.
Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication
PODC '15
Computer Science