Construction and impromptu repair of an MST in a distributed network with o(m) communication

TY - GEN

T1 - Construction and impromptu repair of an MST in a distributed network with o(m) communication

AU - King, Valerie

AU - Kutten, Shay

AU - Thorup, Mikkel

PY - 2015/7/21

Y1 - 2015/7/21

N2 - 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(logn) 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 neighabors, or in the case of MST, the distinct weights of its inacident edges and knows n, then there are Monte Carlo alagorithms 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) mesasages for ST, resp. These results contradict the "folk theaorem" noted in Awerbuch, et.al., JACM 1990 that the disatributed construction of a broadcast tree requires Q(m) mesasages. This lower bound has been shown there and in other papers for some CONGEST models; our protocol demonastrates 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 asynachronous 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 processaing of edge updates there is no preprocessing or storage of additional information. Previous algorithms for this probalem that use an amortized o(m) messages per update reaquire substantial preprocessing and additional local storage between updates.

AB - 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(logn) 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 neighabors, or in the case of MST, the distinct weights of its inacident edges and knows n, then there are Monte Carlo alagorithms 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) mesasages for ST, resp. These results contradict the "folk theaorem" noted in Awerbuch, et.al., JACM 1990 that the disatributed construction of a broadcast tree requires Q(m) mesasages. This lower bound has been shown there and in other papers for some CONGEST models; our protocol demonastrates 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 asynachronous 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 processaing of edge updates there is no preprocessing or storage of additional information. Previous algorithms for this probalem that use an amortized o(m) messages per update reaquire substantial preprocessing and additional local storage between updates.

KW - distributed algorithms, message complexity, network algorithms, spanning tree

U2 - 10.1145/2767386.2767405

DO - 10.1145/2767386.2767405

M3 - Article in proceedings

SN - 978-1-4503-3617-8

SP - 71

EP - 80

BT - Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing

PB - Association for Computing Machinery

T2 - The ACM Symposium on Principles of Distributed Computing 2015

Y2 - 21 July 2015 through 23 July 2015

ER -