Bit complexity of breaking and achieving symmetry in chains and rings

DOI10.1145/1326554.1326557zbMath1326.68035MaRDI 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 bounds; distributed computing; communication complexity; consensus; leader election; bit complexity; tight bound; message complexity; communication cost; processor ring; processor chain; symmetric synchronous execution

Mathematics Subject Classification ID

68M10: Network design and communication in computer systems

68M14: Distributed systems

Related Items

Communication Complexity of Wait-Free Computability in Dynamic Networks, A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots, 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, An optimal bit complexity randomized distributed MIS algorithm, About randomised distributed graph colouring and graph partition algorithms, Deterministic leader election takes \(\Theta (D + \log n)\) bit rounds, Fast protocols for leader election and spanning tree construction in a distributed network, Distributed communication complexity of spanning tree construction, Two absolute bounds for distributed bit complexity, 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)