\magnification=1400\nopagenumbers\hsize=6truein\noindent{\bf
Svante Janson and Wojciech Szpankowski\smallskip\noindent
Analysis of an Asymmetric Leader Election Algorithm}\vskip1cm\noindent
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 {\it 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.


\bye