Carleton University
Technical Report TR-61
August 1984
Analysis of Distributed Algorithms for Extrema Finding in a Ring
D. Rotem, E. Korach, N. Santoro
Abstract
A new and more detailed analysis of the algorithm of Chang and Roberts for distributed extrema finding on a ring is presented. This analysis shows that this simple algorithm which is known to be average case optimal , com pares very favorably with all the other known algorithms as it requires O(nlogn) messages with probability tending to one. A bidirectional version of this algorithm is presented and shown to dominate the unidirectional one in its average message complexity. Finally , both the unidirectional and the bidirectional algorithms are generalized to perform k selection in the ring , i.e. , find the k largest labelled processors.