Bit complexity of breaking and achieving symmetry in chains and rings

DOI10.1145/1326554.1326557zbMath1326.68035OpenAlexW1977127383MaRDI QIDQ3546359

Yefim Dinitz, Shlomo Moran, Sergio Rajsbaum

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

zbMATH Keywords

lower boundsdistributed computingcommunication complexityconsensusleader electionbit complexitytight boundmessage complexitycommunication costprocessor ringprocessor chainsymmetric synchronous execution

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Distributed systems (68M14)

Related Items

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