Loading [MathJax]/jax/output/HTML-CSS/jax.js

Svante Janson ; Christian Lavault ; Guy Louchard - Convergence of some leader election algorithms

dmtcs:437 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, Vol. 10 no. 3 - https://doi.org/10.46298/dmtcs.437
Convergence of some leader election algorithmsArticle

Authors: Svante Janson ; Christian Lavault ; Guy Louchard

    We start with a set of n players. With some probability P(n,k), we kill nk players; the other ones stay alive, and we repeat with them. What is the distribution of the number Xn of \emph{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 \al of the players survive in each round. We prove a kind of convergence in distribution for Xnlog1/α(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\l(Xn,Z+log1/α(n)\r)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. We study the latter algorithm further, including numerical results.


    Volume: Vol. 10 no. 3
    Section: Analysis of Algorithms
    Published on: January 1, 2008
    Imported on: March 26, 2015
    Keywords: Analysis of algorithms,distributed election algorithms,probability,[MATH.MATH-PR] Mathematics [math]/Probability [math.PR],[INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

    2 Documents citing this article

    Consultation statistics

    This page has been seen 482 times.
    This article's PDF has been downloaded 586 times.