Lower Bounds for Distributed Maximum-Finding Algorithms

DOI10.1145/1634.1889zbMath0628.68046OpenAlexW2001357803WikidataQ58330005 ScholiaQ58330005MaRDI QIDQ3765249

Ephraim Korach, Doron Rotem, Jan K. Pachl

Publication date: 1984

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1634.1889

zbMATH Keywords

lower boundsdistributed algorithmsmessage complexitycommunication ringselection algorithmsmaximum label in a circular configuration of n labeled processesnumber of messages

Mathematics Subject Classification ID

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

Related Items

Asymptotically optimal election on weighted rings ⋮ Optimal cost-sensitive distributed minimum spanning tree algorithm ⋮ On the bit complexity of distributed computations in a ring with a leader ⋮ Language complexity on the synchronous anonymous ring ⋮ Some lower bound results for decentralized extrema-finding in rings of processors ⋮ A better lower bound for distributed leader finding in bidirectional asynchronous rings of processors ⋮ Distributed election in complete networks ⋮ Time vs bits ⋮ Fast leader election in anonymous rings with bounded expected delay ⋮ Bit-optimal election in synchronous rings ⋮ Randomized function evaluation on a ring ⋮ Towards optimal distributed election on chordal rings ⋮ A simple, efficient algorithm for maximum finding on rings ⋮ Message terminating algorithms for anonymous rings of unknown size ⋮ On the message complexity of distributed problems ⋮ Efficient elections in chordal ring networks ⋮ Asymptotically Optimal Election on Weighted Rings ⋮ Two lower bounds in asynchronous distributed computation ⋮ New lower bound techniques for distributed leader finding and other problems on rings of processors