Geodesic
Convergence of some leader election algorithms
Discrete mathematics & theoretical computer science, Tome 10 (2007-2008) no. 3.

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2008_10_3_a10,
     author = {Janson, Svante and Lavault, Christian and Louchard, Guy},
     title = {Convergence of some leader election algorithms},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {10},
     number = {3},
     year = {2007-2008},
     doi = {10.46298/dmtcs.437},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.437/}
}
TY  - JOUR
AU  - Janson, Svante
AU  - Lavault, Christian
AU  - Louchard, Guy
TI  - Convergence of some leader election algorithms
JO  - Discrete mathematics & theoretical computer science
PY  - 2007-2008
VL  - 10
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.437/
DO  - 10.46298/dmtcs.437
LA  - en
ID  - DMTCS_2008_10_3_a10
ER  - 
%0 Journal Article
%A Janson, Svante
%A Lavault, Christian
%A Louchard, Guy
%T Convergence of some leader election algorithms
%J Discrete mathematics & theoretical computer science
%D 2007-2008
%V 10
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.437/
%R 10.46298/dmtcs.437
%G en
%F DMTCS_2008_10_3_a10
Janson, Svante; Lavault, Christian; Louchard, Guy. Convergence of some leader election algorithms. Discrete mathematics & theoretical computer science, Tome 10 (2007-2008) no. 3. doi : 10.46298/dmtcs.437. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.437/

Cité par Sources :