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

DOI10.1016/0020-0190(88)90215-3zbMATH Open0652.68052DBLPjournals/ipl/Bodlaender88OpenAlexW2142515485WikidataQ59568105 ScholiaQ59568105MaRDI QIDQ1107315FDOQ1107315

Authors: 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

distributed computinglower boundmessage complexityleader finding on rings of processors

Mathematics Subject Classification ID

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

Cites Work

• Electing a leader in a synchronous ring
• An O ( n log n ) Unidirectional Algorithm for the Circular Extrema Problem
• An improved algorithm for decentralized extrema-finding in circular configurations of processes
• Lower Bounds for Distributed Maximum-Finding Algorithms
• An O(n log n) unidirectional distributed algorithm for extrema finding in a circle
• Title not available (Why is that?)

Cited In (6)

• Finding cut-offs in leaderless rendez-vous protocols is easy
• Some lower bound results for decentralized extrema-finding in rings of processors
• Optimal cost-sensitive distributed minimum spanning tree algorithm
• Exact average message complexity values for distributed election on bidirectional rings of processors
• On the bit complexity of distributed computations in a ring with a leader
• New lower bound techniques for distributed leader finding and other problems on rings of processors

This page was built for publication: A better lower bound for distributed leader finding in bidirectional asynchronous rings of processors

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