Trading Bit, Message, and Time Complexity of Distributed Algorithms

DOI10.1007/978-3-642-24100-0_4zbMath1350.68282OpenAlexW1552044364MaRDI QIDQ3095315

No author found.

Publication date: 28 October 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-24100-0_4

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (8)

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 ⋮ Deterministic leader election takes \(\Theta (D + \log n)\) bit rounds ⋮ On the Microscopic View of Time and Messages ⋮ Message lower bounds via efficient network synchronization ⋮ Trading Bit, Message, and Time Complexity of Distributed Algorithms ⋮ Message Lower Bounds via Efficient Network Synchronization ⋮ A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots

Cites Work

• Distributed computing with advice: information sensitivity of graph coloring
• On the searchability of small-world networks with arbitrary underlying structure
• Trading Bit, Message, and Time Complexity of Distributed Algorithms
• Improved Distributed Approximate Matching
• An Optimal Bit Complexity Randomized Distributed MIS Algorithm (Extended Abstract)
• Design and Analysis of Distributed Algorithms
• Bit complexity of breaking and achieving symmetry in chains and rings
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Electing a leader in a synchronous ring
• Locality in Distributed Graph Algorithms
• Rounds in Communication Complexity Revisited
• Communication Complexity
• Distributed (δ+1)-coloring in linear (in δ) time
• A new technique for distributed symmetry breaking
• Deterministic distributed vertex coloring in polylogarithmic time
• On the complexity of distributed graph coloring
• What cannot be computed locally!

This page was built for publication: Trading Bit, Message, and Time Complexity of Distributed Algorithms