%0 Journal Article
%T Convergence of some leader election algorithms
%A Svante Janson
%A Christian Lavault
%A Guy Louchard
%J Discrete Mathematics & Theoretical Computer Science
%D 2008
%I Discrete Mathematics & Theoretical Computer Science
%X We start with a set of n players. With some probability P(n,k), we kill n-k players; the other ones stay alive, and we repeat with them. What is the distribution of the number X n of phases (or rounds) before getting only one player? We present a probabilistic analysis of this algorithm under some conditions on the probability distributions P(n,k), including stochastic monotonicity and the assumption that roughly a fixed proportion ¦Á of the players survive in each round. We prove a kind of convergence in distribution for X n - log 1/¦Á n; as in many other similar problems there are oscillations and no true limit distribution, but suitable subsequences converge, and there is an absolutely continuous random variable Z such that d(X n,  Z+ log 1/¦Á n )¡ú0, where d is either the total variation distance or the Wasserstein distance. Applications of the general result include the leader election algorithm where players are eliminated by independent coin tosses and a variation of the leader election algorithm proposed by W.R. Franklin 1982. We study the latter algorithm further, including numerical results.
%U http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/950