Abstract
This note presents a more efficient algorithm for finding the largest element in a circular list of processors when messages can be passed in either direction. It passes 2N*floor(lg N) + 3N messages in the worst case, compared to Chang and Roberts' N(N + 1)/2 and Hirschberg and Sinclair's 8N + 8*ceiling(N lg N) messages. The technique is a selective elimination of possible processes, which then merely relay future messages between the remaining contenders.
- 1 Chang, E. and Roberts, R. An improved algorithm for decentralized extrema-finding in circular configurations of processes. Comm. ACM, 22, 5 (May 1979), 281-283. Google ScholarDigital Library
- 2 Hirschberg, D.S. and Sinclair, J.B. Decentralized extrema-finding in circular configurations of processors. Comm. A CM, 23, 11 (Nov, 1980), 627-628. Google ScholarDigital Library
Index Terms
On an improved algorithm for decentralized extrema finding in circular configurations of processors
Recommendations
Decentralized extrema-finding in circular configurations of processors
This note presents an efficient algorithm, requiring O(n log n) message passes, for finding the largest (or smallest) of a set of n uniquely numbered processors arranged in a circle, in which no central controller exists and the number of processors is ...
An improved algorithm for decentralized extrema-finding in circular configurations of processes
This note presents an improvement to LeLann's algorithm for finding the largest (or smallest) of a set of uniquely numbered processes arranged in a circle, in which no central controller exists and the number of processes is not known a priori. This ...
An improved distributed algorithm for maximal independent set
SODA '16: Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithmsThe Maximal Independent Set (MIS) problem is one of the basics in the study of locality in distributed graph algorithms. This paper presents a very simple randomized algorithm for this problem providing a near-optimal local complexity, which ...
Comments