D. S. Hirschberg
Abstract
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 not known a priori.
- 1 Chang, E., and Roberts, R. An improved algorithm for decentralized extrema-fmding in circularly configuraiions of processes. Comm. ACM 22, 5 (May 1979), 281-283. Google Scholar
Digital Library
- 2 LeLann, G. Distributed systems--Towards a formal approach. Inform. Proc. 77, North-Holland Pub. Co., 1977, Amsterdam, pp. 155-160.Google Scholar
- 3 Bums, J.E. A formal model for message passing systems. Tech. Rep. No. 91, Comptr. Sci. Dept., Indiana Univ., May 1980.Google Scholar
Recommendations
On an improved algorithm for decentralized extrema finding in circular configurations of processors
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 +...
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 ...
Predictable performance in SMT processors
CF '04: Proceedings of the 1st conference on Computing frontiersCurrent instruction fetch policies in SMT processors are oriented towards optimization of overall throughput and/or fairness. However, they provide no control over how individual threads are executed, leading to performance unpredictability, since the ...
Comments