Bit complexity of breaking and achieving symmetry in chains and rings
From MaRDI portal
Publication:3546359
DOI10.1145/1326554.1326557zbMath1326.68035OpenAlexW1977127383MaRDI QIDQ3546359
Publication date: 21 December 2008
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1326554.1326557
lower boundsdistributed computingcommunication complexityconsensusleader electionbit complexitytight boundmessage complexitycommunication costprocessor ringprocessor chainsymmetric synchronous execution
Related Items (13)
Two absolute bounds for distributed bit complexity ⋮ On the time and the bit complexity of distributed randomised anonymous ring colouring ⋮ Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings ⋮ Communication Complexity of Wait-Free Computability in Dynamic Networks ⋮ An optimal bit complexity randomized distributed MIS algorithm ⋮ Deterministic leader election takes \(\Theta (D + \log n)\) bit rounds ⋮ About randomised distributed graph colouring and graph partition algorithms ⋮ Fast protocols for leader election and spanning tree construction in a distributed network ⋮ Generalized Symmetry Breaking Tasks and Nondeterminism in Concurrent Objects ⋮ Trading Bit, Message, and Time Complexity of Distributed Algorithms ⋮ An Optimal Bit Complexity Randomized Distributed MIS Algorithm (Extended Abstract) ⋮ Distributed communication complexity of spanning tree construction ⋮ A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots
This page was built for publication: Bit complexity of breaking and achieving symmetry in chains and rings