Convergence of some leader election algorithms
| dc.creator | Janson, Svante | |
| dc.creator | Lavault, Christian | |
| dc.creator | Louchard, Guy | |
| dc.date | 2008-02-11 | |
| dc.date.accessioned | 2026-07-07T09:19:52Z | |
| dc.date.available | 2026-07-07T09:19:52Z | |
| dc.description | 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 alpha of the players survive in each round. We prove a kind of convergence in distribution for X_n-log_a n, where the basis a=1/alpha; 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 the distribution of X_n can be approximated by Z+log_a n rounded to the nearest larger integer. 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. | |
| dc.description | 27 pages, 13 figures, 5 tables | |
| dc.identifier | https://arxiv.org/abs/0802.1389 | |
| dc.identifier | http://arxiv.org/abs/0802.1389 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/154551 | |
| dc.subject | Distributed, Parallel, and Cluster Computing | |
| dc.subject | Probability | |
| dc.title | Convergence of some leader election algorithms | |
| dc.type | text |