Time-message trade-offs in distributed algorithms
From MaRDI portal
Publication:5090924
Recommendations
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 computation of large-scale graph problems
- Distributed Computing: A Locality-Sensitive Approach
- 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
(17)- Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model
- Latency, capacity, and distributed minimum spanning trees
- Low-congestion shortcut and graph parameters
- Time and Message Bounds for Election in Synchronous and Asynchronous Complete Networks
- Constant space and non-constant time in distributed computing
- Efficient distributed algorithms by using the archimedean time assumption
- Ability to Count Messages Is Worth Θ(Δ) Rounds 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
- Communication costs in a geometric communication network
- Deterministic Fault-Tolerant Connectivity Labeling Scheme
- Singularly optimal randomized leader election
- Time- and communication-efficient overlay network construction via gossip
- Tight bounds on the message complexity of distributed tree verification
- Deterministic fault-tolerant connectivity labeling scheme
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)
