Geodesic
Analysis of an asymmetric leader election algorithm
The electronic journal of combinatorics, Tome 4 (1997) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We consider a leader election algorithm in which a set of distributed objects (people, computers, etc.) try to identify one object as their leader. The election process is randomized, that is, at every stage of the algorithm those objects that survived so far flip a biased coin, and those who received, say a tail, survive for the next round. The process continues until only one objects remains. Our interest is in evaluating the limiting distribution and the first two moments of the number of rounds needed to select a leader. We establish precise asymptotics for the first two moments, and show that the asymptotic expression for the duration of the algorithm exhibits some periodic fluctuations and consequently no limiting distribution exists. These results are proved by analytical techniques of the precise analysis of algorithms such as: analytical poissonization and depoissonization, Mellin transform, and complex analysis.
DOI : 10.37236/1302
Classification : 05A15, 60C05
Mots-clés : leader election algorithm, election process, limiting distribution 
@article{10_37236_1302,
     author = {Svante Janson and Wojciech Szpankowski},
     title = {Analysis of an asymmetric leader election algorithm},
     journal = {The electronic journal of combinatorics},
     year = {1997},
     volume = {4},
     number = {1},
     doi = {10.37236/1302},
     zbl = {0884.05004},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1302/}
}
TY  - JOUR
AU  - Svante Janson
AU  - Wojciech Szpankowski
TI  - Analysis of an asymmetric leader election algorithm
JO  - The electronic journal of combinatorics
PY  - 1997
VL  - 4
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1302/
DO  - 10.37236/1302
ID  - 10_37236_1302
ER  - 
%0 Journal Article
%A Svante Janson
%A Wojciech Szpankowski
%T Analysis of an asymmetric leader election algorithm
%J The electronic journal of combinatorics
%D 1997
%V 4
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/1302/
%R 10.37236/1302
%F 10_37236_1302
Svante Janson; Wojciech Szpankowski. Analysis of an asymmetric leader election algorithm. The electronic journal of combinatorics, Tome 4 (1997) no. 1. doi: 10.37236/1302

Cité par Sources :