Time-message trade-offs in distributed algorithms
From MaRDI portal
Publication:5090924
DOI10.4230/LIPICS.DISC.2018.32zbMATH Open1497.68565arXiv1810.03513MaRDI QIDQ5090924FDOQ5090924
Authors: Robert Gmyr, Gopal Pandurangan 
Publication date: 21 July 2022
Full work available at URL: https://arxiv.org/abs/1810.03513
Recommendations
Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Distributed algorithms (68W15)
Cites Work
- Universal classes of hash functions
- Distributed minimum cut approximation
- A trade-off between information and communication in broadcast protocols
- Distributed Computing: A Locality-Sensitive Approach
- Distributed verification and hardness of distributed approximation
- All-Pairs Almost Shortest Paths
- Probability and Computing
- A Distributed Algorithm for Minimum-Weight Spanning Trees
- Chernoff–Hoeffding Bounds for Applications with Limited Independence
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
- Randomized broadcast in networks
- Random sampling in cut, flow, and network design problems
- Round- and message-optimal distributed graph algorithms
- The distributed minimum spanning tree problem
- Distributed computation of large-scale graph problems
- Toward optimal bounds in the congested clique, graph connectivity and MST
- Almost-Tight Distributed Minimum Cut Algorithms
- On the Complexity of Universal Leader Election
- Construction and impromptu repair of an MST in a distributed network with \(o(m)\) communication
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)
