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

DOI10.1145/2767386.2767405MaRDI QIDQ2796243zbMATH OpenOpenAlexFDO

Authors Valerie King, Shay Kutten, Mikkel Thorup

Publication date 23 March 2016

Published in Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.03320

zbMATH Keywords

distributed algorithmsspanning treenetwork algorithmsmessage complexity

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15) Distributed systems (68M14) Network protocols (68M12)

Abstract: 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 neighbors. 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(nlo{g}^{2}n/loglogn)$ messages for MST and $O(nlogn)$ 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 $Omega(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(nlogn/loglogn)$ 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 additional information. Previous algorithms for this problem that use an amortized $o(m)$ messages per update require substantial preprocessing and additional local storage between updates.

Recommendations

• Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model
• Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model
• Distributed MST and broadcast with fewer messages, and faster gossiping
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds

Cites work

• scientific article; zbMATH DE number 826255 (Why is no real title available?)
• Memorization and Association on a Realistic Neural Model

Cited in

(16)

• Latency, capacity, and distributed minimum spanning trees
• Near-optimal distributed computation of small vertex cuts
• Brief Announcement: What Can We Compute in a Single Round of the Congested Clique?
• Deterministic Fault-Tolerant Connectivity Labeling Scheme
• Improved Tradeoffs for Leader Election
• Optimal Message-Passing with Noisy Beeps
• Distributed MST and broadcast with fewer messages, and faster gossiping
• Time-message trade-offs in distributed algorithms
• Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model
• Communication efficient self-stabilizing leader election
• Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model
• Fooling views: a new lower bound technique for distributed computations under congestion
• Optimal maintenance of a spanning tree
• Communication costs in a geometric communication network
• \texttt{Sample(x)=(a*x<=t)} is a distinguisher with probability \(1/8\)
• Beep-and-sleep: message and energy efficient set cover

This page was built for publication: Construction and impromptu repair of an MST in a distributed network with \(o(m)\) communication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2796243)