{"docId":437,"paperId":437,"url":"https:\/\/dmtcs.episciences.org\/437","doi":"10.46298\/dmtcs.437","journalName":"Discrete Mathematics & Theoretical Computer Science","issn":"","eissn":"1365-8050","volume":[{"vid":85,"name":"Vol. 10 no. 3"}],"section":[{"sid":2,"title":"Analysis of Algorithms","description":[]}],"repositoryName":"Hal","repositoryIdentifier":"hal-00461881","repositoryVersion":1,"repositoryLink":"https:\/\/hal.science\/hal-00461881v1","dateSubmitted":"2015-03-26 16:20:06","dateAccepted":"2015-06-09 14:46:58","datePublished":"2008-01-01 08:00:00","titles":{"en":"Convergence of some leader election algorithms"},"authors":["Janson, Svante","Lavault, Christian","Louchard, Guy"],"abstracts":{"en":"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 \\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 $X_n - \\log_{1\/\\!\\alpha}(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(X_n, \\lceil Z + \\log_{1\/\\!\\alpha} (n)\\rceil\\r) \\to 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."},"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]"]}