Convergence of some leader election algorithms
Svante Janson, Christian Lavault, Guy Louchard
Abstract
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 Xn 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 α of the players
survive
in each round. We prove a kind of convergence in distribution for
Xn-log1/α
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(Xn,
⌈Z+log1/α n⌉)→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 1982.
We study the latter algorithm further, including numerical results.
Full Text: PDF PostScript