Lower Bounds for Distributed Maximum-Finding Algorithms
- 20 September 1984
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 31 (4) , 905-918
- https://doi.org/10.1145/1634.1889
Abstract
Tills paper establishes several lower bounds of the form f~(nlogn) for the number of messages needed to find the maximum label in a circular configuration of n labeled processes with no central controller.Keywords
This publication has 4 references indexed in Scilit:
- An O ( n log n ) Unidirectional Algorithm for the Circular Extrema ProblemACM Transactions on Programming Languages and Systems, 1982
- On an improved algorithm for decentralized extrema finding in circular configurations of processorsCommunications of the ACM, 1982
- Decentralized extrema-finding in circular configurations of processorsCommunications of the ACM, 1980
- An improved algorithm for decentralized extrema-finding in circular configurations of processesCommunications of the ACM, 1979