Asymptotic analysis of a leader election algorithm

Itai and Rodeh showed that, on the average, the communication of a leader election algorithm takes no more than LN bits, where L≃2.441716 and N denotes the size of the ring. We give a precise asymptotic analysis of the average number of rounds M(n) required by the algorithm, proving for example that where n is the number of starting candidates in the election. Accurate asymptotic expressions of the second moment M(2)(n) of the discrete random variable at hand, its probability distribution, and the generalization to all moments are given. Corresponding asymptotic expansions (n→∞) are provided for sufficiently large j, where j counts the number of rounds. Our numerical results show that all computations perfectly fit the observed values. Finally, we investigate the generalization to probability t/n, where t is a non-negative real parameter. The real function is shown to admit one unique minimum M(∞,t*) on the real segment (0,2). Furthermore, the variations of M(∞,t) on the whole real line are also studied in detail.