Bit complexity of breaking and achieving symmetry in chains and rings

DOI10.1145/1326554.1326557MaRDI QIDQ3546359zbMATH OpenOpenAlexFDO

Authors Shlomo Moran, Sergio Rajsbaum, Yefim Dinitz

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

distributed computinglower boundsconsensusleader electioncommunication complexitybit complexitytight boundmessage complexitycommunication costprocessor ringprocessor chainsymmetric synchronous execution

Mathematics Subject Classification ID

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

Recommendations

• Bit complexity of breaking and achieving symmetry in chains and rings (extended abstract)
• The complexity of symmetry-breaking formulas
• Circuit complexity of symmetric Boolean functions in antichain basis
• scientific article; zbMATH DE number 4035741
• scientific article; zbMATH DE number 4062892
• scientific article; zbMATH DE number 165425
• Symmetric groups and quotient complexity of Boolean operations
• Long symmetric chains in the Boolean lattice
• Parameterized complexity results in symmetry breaking
• Decompositions of the Boolean lattice into rank-symmetric chains.

Cited in

(17)

• Trading bit, message, and time complexity of distributed algorithms
• Structural Information and Communication Complexity
• Bit complexity of breaking and achieving symmetry in chains and rings (extended abstract)
• Generalized symmetry breaking tasks and nondeterminism in concurrent objects
• The topology of randomized symmetry-breaking distributed computing
• An optimal bit complexity randomized distributed MIS algorithm
• 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
• Distributed communication complexity of spanning tree construction
• An optimal bit complexity randomized distributed MIS algorithm (extended abstract)
• Exact communication costs for consensus and leader in a tree
• Communication Complexity of Wait-Free Computability in Dynamic Networks
• About randomised distributed graph colouring and graph partition algorithms
• A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots
• Deterministic leader election takes \(\Theta (D + \log n)\) bit rounds
• Two absolute bounds for distributed bit complexity
• Fast protocols for leader election and spanning tree construction in a distributed network

This page was built for publication: Bit complexity of breaking and achieving symmetry in chains and rings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3546359)