RR-3089 : Analysis of an Asymmetric Leader Election Algorithm

Abstract : 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.

Résumé : On considère un algorithme d'élection dans lequel un ensemble d'objets distribués (personnes, ordinateurs, etc...) essayent d'identifier l'un d'eux comme leur leader. Le processus d'élection est aléatoire, basé sur un jeu de pile ou face biaisé~: à chaque étape de l'algorithme, les objets qui ont survécu jusque là, passent au prochain tour s'ils obtiennent pile par exemple. On s'intéresse à la distribution limite et aux deux premiers moments du nombre de tours nécessaires pour élire un leader. On établit des asymptotiques précis pour les deux premiers moments, on montre que l'expression asymptotique de la durée de l'algorithme exhibe des fluctuations périodiques et par conséquent qu'il n'existe pas de distribution limite. Ces résultats sont prouvés par des techniques d'analyse algorithmique telles que~: poissonnisation et dépoissonnisation, transformée de Mellin et analyse complexe.

RR-3089 - Analysis of an Asymmetric Leader Election Algorithm