The Bit Complexity of Randomized Leader Election on a Ring

DOI10.1137/0218002zbMATH Open0674.68029OpenAlexW2077204293MaRDI QIDQ3829068FDOQ3829068

Authors

Publication date 1989

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0218002

zbMATH Keywords

complexityrandomized algorithmslower boundsattritionleader electioncommunication complexityasynchronous distributed computationprocessor ringssolitude verification

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Theory of computing (68Q99)

Recommendations

• scientific article; zbMATH DE number 177572
• On the bit complexity of distributed computations in a ring with a leader
• Improved bounds for electing a leader in a synchronous ring
• Deterministic, constant space, self-stabilizing leader election on uniform rings
• Randomized self-stabilizing and space optimal leader election under arbitrary scheduler on rings
• The complexity of leader election in diameter-two networks
• Compact deterministic self-stabilizing leader election on a ring: the exponential advantage of being talkative

Cited In (15)

• Bit-optimal election in synchronous rings
• Randomized function evaluation on a ring
• Symmetry breaking in distributed networks
• Hundreds of impossibility results for distributed computing
• Two absolute bounds for distributed bit complexity
• Simplifying Itai-Rodeh leader election for anonymous rings
• Tight lower bounds for probabilistic solitude verification on anonymous rings
• Structural Information and Communication Complexity
• Title not available (Why is no real title available?)
• The topology of randomized symmetry-breaking distributed computing
• Title not available (Why is no real title available?)
• On the bit complexity of distributed computations in a ring with a leader
• Anonymous wireless rings
• The space complexity of leader election in anonymous networks
• New lower bound techniques for distributed leader finding and other problems on rings of processors

This page was built for publication: The Bit Complexity of Randomized Leader Election on a Ring

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