Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication

DOI10.1145/2767386.2767405zbMath1333.68213arXiv1502.03320OpenAlexW1982792741MaRDI QIDQ2796243

Mikkel Thorup, Shay Kutten, Valerie King

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

spanning treedistributed algorithmsnetwork algorithmsmessage complexity

Mathematics Subject Classification ID

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

Related Items (13)

Latency, capacity, and distributed minimum spanning trees ⋮ Sample(x)=(a*x<=t) Is a Distinguisher with Probability 1/8 ⋮ Communication costs in a geometric communication network ⋮ Brief Announcement: What Can We Compute in a Single Round of the Congested Clique? ⋮ Deterministic Fault-Tolerant Connectivity Labeling Scheme ⋮ Optimal Message-Passing with Noisy Beeps ⋮ Improved Tradeoffs for Leader Election ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Beep-and-sleep: message and energy efficient set cover

Cites Work

• Memorization and Association on a Realistic Neural Model
• Unnamed Item

This page was built for publication: Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication