The asymmetric leader election algorithm with Swedish stopping: a probabilistic analysis

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 tau 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 R-n, Number of null rounds T-n. 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, whereever results are given in both papers, they coincide, although they are presented in different ways.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2012, Vol. 14 no. 2 (2), pp.91--127
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00990592
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 16:27:44
Dernière modification le : jeudi 7 septembre 2017 - 01:03:38
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:45:56

Fichier

1841-7406-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990592, version 1

Collections

Citation

Guy Louchard, Helmut Prodinger. The asymmetric leader election algorithm with Swedish stopping: a probabilistic analysis. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2012, Vol. 14 no. 2 (2), pp.91--127. 〈hal-00990592〉

Partager

Métriques

Consultations de la notice

210

Téléchargements de fichiers

203