Time-message trade-offs in distributed algorithms

DOI10.4230/LIPICS.DISC.2018.32MaRDI QIDQ5090924zbMATH OpenFDO

Authors Robert Gmyr, Gopal Pandurangan

Publication date 21 July 2022

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

zbMATH Keywords

MSTrandomized algorithmsparsifiersingular optimality

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Distributed algorithms (68W15)

Recommendations

• Round- and message-optimal distributed graph algorithms
• Distributed MST and broadcast with fewer messages, and faster gossiping

Cites work

• A Distributed Algorithm for Minimum-Weight Spanning Trees
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
• A trade-off between information and communication in broadcast protocols
• All-Pairs Almost Shortest Paths
• Almost-Tight Distributed Minimum Cut Algorithms
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• Construction and impromptu repair of an MST in a distributed network with \(o(m)\) communication
• Distributed Computing: A Locality-Sensitive Approach
• Distributed computation of large-scale graph problems
• Distributed minimum cut approximation
• Distributed verification and hardness of distributed approximation
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• On the Complexity of Universal Leader Election
• Probability and Computing
• Random sampling in cut, flow, and network design problems
• Randomized broadcast in networks
• Round- and message-optimal distributed graph algorithms
• The distributed minimum spanning tree problem
• Toward optimal bounds in the congested clique, graph connectivity and MST
• Universal classes of hash functions

Cited in

(14)

• Ability to Count Messages Is Worth Θ(Δ) Rounds in Distributed Computing
• Low-congestion shortcut and graph parameters
• Latency, capacity, and distributed minimum spanning trees
• Time and Message Bounds for Election in Synchronous and Asynchronous Complete Networks
• Communication costs in a geometric communication network
• Constant space and non-constant time in distributed computing
• Interval approximations of message causality in distributed executions
• New classes of distributed time complexity
• Beep-and-sleep: message and energy efficient set cover
• Beep-and-sleep: message and energy efficient set cover
• Deterministic Fault-Tolerant Connectivity Labeling Scheme
• Singularly optimal randomized leader election
• Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model
• Efficient distributed algorithms by using the archimedean time assumption

This page was built for publication: Time-message trade-offs in distributed algorithms

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