New lower bound techniques for distributed leader finding and other problems on rings of processors

DOI10.1016/0304-3975(91)90193-6MaRDI QIDQ808701zbMATHOpenAlexWikidataFDO

Authors Hans L. Bodlaender

Publication date 1991

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://dspace.library.uu.nl/handle/1874/16571

zbMATH Keywords

randomized algorithmslower bounddistributed algorithmleader electionasynchronous ring of processors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10)

Recommendations

• Two lower bounds in asynchronous distributed computation
• Some lower bound results for decentralized extrema-finding in rings of processors
• scientific article; zbMATH DE number 177572
• Computing on an anonymous ring
• Lower Bounds for Distributed Maximum-Finding Algorithms

Cites work

• scientific article; zbMATH DE number 3850459 (Why is no real title available?)
• scientific article; zbMATH DE number 3978376 (Why is no real title available?)
• scientific article; zbMATH DE number 4028858 (Why is no real title available?)
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 17531 (Why is no real title available?)
• A better lower bound for distributed leader finding in bidirectional asynchronous rings of processors
• A lower bound for probabilistic distributed algorithms
• An O ( n log n ) Unidirectional Algorithm for the Circular Extrema Problem
• An O(n log n) unidirectional distributed algorithm for extrema finding in a circle
• An improved algorithm for decentralized extrema-finding in circular configurations of processes
• Average number of messages for distributed leader-fitting in rings of processors
• Computing on an anonymous ring
• Electing a leader in a synchronous ring
• Lower Bounds for Distributed Maximum-Finding Algorithms
• Randomized function evaluation on a ring
• The Bit Complexity of Randomized Leader Election on a Ring

Cited in

(14)

• scientific article; zbMATH DE number 177572 (Why is no real title available?)
• Average number of messages for distributed leader finding in rings of processors
• Finding cut-offs in leaderless rendez-vous protocols is easy
• scientific article; zbMATH DE number 3978376 (Why is no real title available?)
• On the bit complexity of distributed computations in a ring with a leader
• Tight lower bounds for probabilistic solitude verification on anonymous rings
• Some lower bound results for decentralized extrema-finding in rings of processors
• Hundreds of impossibility results for distributed computing
• Some problems in distributed computational geometry
• Lower Bounds for Distributed Maximum-Finding Algorithms
• Average number of messages for distributed leader-fitting in rings of processors
• Fast leader election in anonymous rings with bounded expected delay
• TOPOLOGICAL CONSTRAINTS FOR SENSE OF DIRECTION
• scientific article; zbMATH DE number 17531 (Why is no real title available?)

This page was built for publication: New lower bound techniques for distributed leader finding and other problems on rings of processors

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