<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 12 Issue 4" %>
The Asymmetric Leader Election Algorithm: Another Approach
Guy Louchard1 and Helmut Prodinger2
1Universit\'e Libre de Bruxelles, D\'epartement d'Informatique, CP 212, Boulevard du Triomphe, B-1050 Bruxelles, Belgium
louchard@ulb.ac.be
2Helmut Prodinger, Mathematics Department, Stellenbosch University, 7602 Stellenbosch, South Africa
hproding@sun.ac.za
Annals of Combinatorics 12 (4) pp.445-474 December, 2008
AMS Subject Classification: 68R05, 60C05
Abstract:
The asymmetric leader election algorithm has obtained quite a bit of attention lately. In this paper we want to analyze the following asymptotic properties of the number of rounds: Limiting distribution function, all moments in a simple automatic way, asymptotics for $p\ra 0$, $p\ra 1 $ (where $p$ denotes the ``killing'' probability). This also leads to a few interesting new identities. We use two paradigms: First, in some urn model, we have asymptotic independence of urns behaviour as far as random variables related to urns with a fixed number of balls are concerned. Next, we use a technique easily leading to the asymptotics of the moments of extreme-value related distribution functions.
Keywords: leader election, Gumbel distribution, urn model, Mellin transform

References:

1. F.T. Bruss and R. Gr¨ubel, On the multiplicity of the maximum in a discrete random sample, Ann. Appl. Probab. 13 (4) (2003) 1252–-1263.

2. J.A. Fill, H. Mahmoud, and W. Szpankowski, On the distribution for the duration of a randomized leader election algorithm, Ann. Appl. Probab. 6 (4) (1996) 1260–-1283.

3. R.L. Graham, D.E. Knuth, and O. Patashnik, Concrete Mathematics, 2nd Ed., Addison Wesley, MA, 1994.

4. S. Janson, Rounding of continuous random variables and oscillatory asymptotics, Ann. Probab. 34 (5) (2006) 1807-–1826.

5. S. Janson and W. Szpankowski, Analysis of an asymmetric leader election algorithm, Electron. J. Combin. 4 (1) (1997) #R17.

6. C. Knessl, Asymptotics and numerical studies of the leader election algorithm, European J. Appl. Math. 12 (6) (2001) 645-–664.

7. G. Louchard and H. Prodinger, Asymptotics of the moments of extreme-value related distribution functions, Algorithmica 46 (3-4) (2006) 431–467; long version on line at: http://www.ulb.ac.be/di/mcs/louchard/moml.ps.

8. G. Louchard and H. Prodinger, On gaps and unoccupied urns in sequences of geometrically distributed random variables, Discrete Math. 308 (9) (2008) 1538–-1562.

9. G. Louchard, H. Prodinger, and M.D. Ward, The number of distinct values of some multiplicity in sequences of geometrically distributed random variables, In: 2005 International Conference on Analysis of Algorithms, Discrete Math. Theoret. Comput. Sci. Proc., (2005) pp. 231–256; online at: http://www.univie.ac.at/EMIS/journals/DMTCS/ proceedings/dmAD01ind.html.

10. H. Mohamed, A probabilistic analysis of a leader election algorithm, In: Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, Discrete Math. Theoret. Comput. Sci. Proc., (2006) pp. 225-–236; online at: http://www-rocq.inria.fr/who/Hanene.Mohamed/Preprints.html.

11. H. Prodinger, How to select a loser, Discrete Math. 120 (1-3) (1993) 149–-159.

12. H. Prodinger, Periodic oscillations in the analysis of algorithms—and their cancellations, J. Iranian Statist. Soc. 3 (2004) 251-–270.