A better lower bound for distributed leader finding in bidirectional asynchronous rings of processors

DOI10.1016/0020-0190(88)90215-3zbMath0652.68052DBLPjournals/ipl/Bodlaender88OpenAlexW2142515485WikidataQ59568105 ScholiaQ59568105MaRDI QIDQ1107315

Hans L. Bodlaender

Publication date: 1988

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

lower bounddistributed computingmessage complexityleader finding on rings of processors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Theory of operating systems (68N25)

Related Items (4)

Optimal cost-sensitive distributed minimum spanning tree algorithm ⋮ Some lower bound results for decentralized extrema-finding in rings of processors ⋮ Exact average message complexity values for distributed election on bidirectional rings of processors ⋮ New lower bound techniques for distributed leader finding and other problems on rings of processors

Cites Work

• Unnamed Item
• Lower Bounds for Distributed Maximum-Finding Algorithms
• Electing a leader in a synchronous 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: A better lower bound for distributed leader finding in bidirectional asynchronous rings of processors