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

DOI10.1016/0020-0190(88)90215-3MaRDI QIDQ1107315zbMATH OpenOpenAlexDBLPWikidataFDO

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

• scientific article; zbMATH DE number 4028858 (Why is no real title available?)
• 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
• Electing a leader in a synchronous ring
• Lower Bounds for Distributed Maximum-Finding Algorithms

Cited in

(6)

• Finding cut-offs in leaderless rendez-vous protocols is easy
• 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
• Some lower bound results for decentralized extrema-finding in rings of processors
• New lower bound techniques for distributed leader finding and other problems on rings of processors
• Optimal cost-sensitive distributed minimum spanning tree algorithm

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)