6 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 M(∞): = lim n→∞ M(n) = 2.441715879..., 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 M(∞, t): = lim n→∞ M(n, t) 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.