Trading bit, message, and time complexity of distributed algorithms
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 176511
- On the complexity of distributed graph coloring
- On lower bounds for the time and the bit complexity of some probabilistic distributed graph algorithms. Extended abstract
- An optimal bit complexity randomized distributed MIS algorithm (extended abstract)
- Distributed Maximal Independent Set using Small Messages
Cites work
- A new technique for distributed symmetry breaking
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- An optimal bit complexity randomized distributed MIS algorithm (extended abstract)
- Bit complexity of breaking and achieving symmetry in chains and rings
- Communication Complexity
- Design and Analysis of Distributed Algorithms
- Deterministic distributed vertex coloring in polylogarithmic time
- Distributed \(({\Delta}+1)\)-coloring in linear (in \({\Delta})\) time
- Distributed computing with advice: information sensitivity of graph coloring
- Electing a leader in a synchronous ring
- Improved Distributed Approximate Matching
- Locality in Distributed Graph Algorithms
- On the complexity of distributed graph coloring
- On the searchability of small-world networks with arbitrary underlying structure
- Rounds in Communication Complexity Revisited
- Trading bit, message, and time complexity of distributed algorithms
- What cannot be computed locally!
Cited in
(11)- Tight bounds for synchronous communication of information using bits and silence
- Deterministic leader election takes \(\Theta (D + \log n)\) bit rounds
- Message lower bounds via efficient network synchronization
- A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots
- Message Lower Bounds via Efficient Network Synchronization
- Trading bit, message, and time complexity of distributed algorithms
- Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds
- Symmetry breaking depending on the chromatic number or the neighborhood growth
- Ability to Count Messages Is Worth Θ(Δ) Rounds in Distributed Computing
- On the microscopic view of time and messages
- A note on the message complexity of Cidon's distributed depth-first search algorithm
This page was built for publication: Trading bit, message, and time complexity of distributed algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3095315)
