Bit complexity of breaking and achieving symmetry in chains and rings
From MaRDI portal
Publication:3546359
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
lower bounds; distributed computing; communication complexity; consensus; leader election; bit complexity; tight bound; message complexity; communication cost; processor ring; processor chain; symmetric synchronous execution
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)