The asymmetric leader election algorithm: Number of survivors near the end of the game

Abstract

The following classical asymmetric leader election algorithm has obtained quite a bit of attention lately. Starting with n players, each one throws a coin, and the k of them which have each thrown a head (with probability q) go on, and the leader will be found amongst them, using the same strategy. Should nobody advance, the party will repeat the procedure. One of the most interesting parameter here is the number J (n) of rounds until a leader has been identified. In this paper we investigate, in the classical leader election algorithm, what happens near the end of the game, namely we fix an integer κ and we study the behaviour of the number of survivors L at level J (n) − κ. In our asymptotic analysis (for n → ∞) we are focusing on the limiting distribution functions. We also investigate what happens, if the parameter p = 1 − q gets small (p → 0) or large (p → 1). We use three efficient tools: an urn model, a Mellin-Laplace technique for harmonic sums and some asymptotic distributions related to one of the extreme-value distributions: the Gumbel law. This study was motivated by a recent paper by Kalpathy, Mahmoud and Rosenkrantz, where they consider the number of survivors S_n,t, after t election rounds, in a broad class of fair leader election algorithms starting with n candidates.

Mathematics Subject Classification (2010):

• 68R05
• 68W40

Key words:

• Asymmetric leader election algorithm
• number of rounds until a leader has been identified
• number of survivors near the end of the game
• limiting distribution functions
• urn model
• Mellin-Laplace technique for harmonic sums
• Gumbel distribution
• analytic combinatorics