The Asymmetric Leader Election Algorithm with swedish stopping: A probabilistic analysis
Helmut Prodinger, Guy Louchard
Abstract
We study a leader election protocol that we call the Swedish leader
election protocol. This name comes from a protocol presented by
L. Bondesson, T. Nilsson, and G. Wikstrand (2007). The goal is to
select one among n > 0 players, by proceeding through
a number of rounds. If there is only one player remaining, the
protocol stops and the player is declared the leader. Otherwise, all
remaining players flip a biased coin; with probability q
the player survives to the next round, with probability
p=1-q the player loses (is killed) and plays no further
… unless all players lose in a given round (null round), so all
of them play again. In the classical leader election protocol, any
number of null rounds may take place, and with probability 1
some player will ultimately be elected. In the Swedish leader election
protocol there is a maximum number τ of consecutive
null rounds, and if the threshold is attained the protocol fails
without declaring a leader. In this paper, several parameters are
asymptotically analyzed, among them: Success Probability, Number of
rounds Rn, Number of null rounds
Tn. This paper is a companion paper to
Louchard, Martinez and Prodinger (2011) where De-Poissonization was
used, together with the Mellin transform. While this works fine as far
as it goes, there are limitations, in particular of a computational
nature. The approach chosen here is similar to earlier efforts of the
same authors - Louchard and Prodinger (2004,2005,2009). Identifying
some underlying distributions as Gumbel (type) distributions, one can
start with approximations at a very early stage and compute (at least
in principle) all moments asymptotically. This is in contrast to the
companion work, where only expected values were considered. In an
appendix, it is shown that, wherever results are given in both papers,
they coincide, although they are presented in different ways.
Full Text: PDF PostScript