Average number of messages for distributed leader-fitting in rings of processors (Q1117694)

Korach, Rotem, and Santoro proposed a probabilistic algorithm (P) as well as a deterministic algorithm (D) for finding a leader in an asynchronous bidirectional ring of processors. The author presents a detailed analysis of the exact asymptotic average values of the number of messages required in these algorithms. These values which equal both to \(2^{-1/2} n\cdot H_ n+O(n)\) (where \(H_ n\) denotes the n-th harmonic number) are obtained by use of considerations from the theory of permutations and combinatorial enumeration arguments.