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

DOI10.1016/0304-3975(91)90193-6zbMath0732.68048OpenAlexW2006888470WikidataQ59568030 ScholiaQ59568030MaRDI QIDQ808701

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

lower boundrandomized algorithmsdistributed algorithmleader electionasynchronous ring of processors

Mathematics Subject Classification ID

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

Related Items (4)

Some lower bound results for decentralized extrema-finding in rings of processors ⋮ Fast leader election in anonymous rings with bounded expected delay ⋮ Hundreds of impossibility results for distributed computing ⋮ TOPOLOGICAL CONSTRAINTS FOR SENSE OF DIRECTION

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Randomized function evaluation on a ring
• A better lower bound for distributed leader finding in bidirectional asynchronous rings of processors
• Average number of messages for distributed leader-fitting in rings of processors
• Lower Bounds for Distributed Maximum-Finding Algorithms
• Electing a leader in a synchronous ring
• A lower bound for probabilistic distributed algorithms
• Computing on an anonymous ring
• The Bit Complexity of Randomized Leader Election on a Ring
• 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

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