Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-23T18:19:57.906Z Has data issue: false hasContentIssue false
  • English
  • Français

Asymptotic Properties of a Leader Election Algorithm

Part of: Algorithms - Computer Science Limit theorems Combinatorial probability Graph theory

Published online by Cambridge University Press:  14 July 2016

Ravi Kalpathy ,
Hosam M. Mahmoud  and
Mark Daniel Ward
Ravi Kalpathy*
Affiliation:
The George Washington University
Hosam M. Mahmoud*
Affiliation:
The George Washington University
Mark Daniel Ward*
Affiliation:
Purdue University
*
∗Postal address: Department of Statistics, The George Washington University, 2140 Pennsylvania Avenue, Washington, DC 20052, USA.
∗Postal address: Department of Statistics, The George Washington University, 2140 Pennsylvania Avenue, Washington, DC 20052, USA.
∗∗∗∗Postal address: Department of Statistics, Purdue University, 150 North University Street, West Lafayette, IN 47907-1451, USA. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We consider a serialized coin-tossing leader election algorithm that proceeds in rounds until a winner is chosen, or all contestants are eliminated. The analysis allows for either biased or fair coins. We find the exact distribution for the duration of any fixed contestant; asymptotically, it turns out to be a geometric distribution. Rice's method (an analytic technique) shows that the moments of the duration contain oscillations, which we give explicitly for the mean and variance. We also use convergence in the Wasserstein metric space to show that the distribution of the total number of coin flips (among all participants), suitably normalized, approaches a normal limiting random variable.

Keywords

Leader electionanalytic combinatoricsRice's methodfixed pointcontraction methodWasserstein metric spaceweak convergence

MSC classification

Secondary: 60C05: Combinatorial probability 05C05: Trees 60F05: Central limit and other weak theorems 68W40: Analysis of algorithms
Type
Research Article
Information
Journal of Applied Probability , Volume 48 , Issue 2 , June 2011 , pp. 569 - 575
Copyright
Copyright © Applied Probability Trust 2011 

Footnotes

Research supported by NSF Science & Technology Center grant CCF-0939370.

References

[1] Barbour, A. D., Holst, L. and Janson, S. (1992). Poisson Approximation. Clarendon Press, Oxford.CrossRefGoogle Scholar
[2] Devroye, L. (1992). A limit theory for random skip lists. Ann. Appl. Prob. 2, 597–609.CrossRefGoogle Scholar
[3] Fill, J. A., Mahmoud, H. M. and Szpankowski, W. (1996). On the distribution for the duration of a randomized leader election algorithm. Ann. Appl. Prob. 6, 1260–1283.CrossRefGoogle Scholar
[4] Flajolet, P. and Sedgewick, R. (1995). Mellin transforms and asymptotics: finite differences and Rice's integrals. Theoret. Comput. Sci. 144, 101–124.CrossRefGoogle Scholar
[5] Janson, S. and Szpankowski, W. (1997). Analysis of an asymmetric leader election algorithm. Electron. J. Combinatorics 4, R17, 16 pp.CrossRefGoogle Scholar
[6] Karr, A. F. (1993). Probability. Springer, New York.CrossRefGoogle Scholar
[7] Louchard, G. and Prodinger, H. (2008). Advancing in the presence of a demon. Math. Slovaca 58, 263–276.CrossRefGoogle Scholar
[8] Louchard, G., Prodinger, H. and Ward, M. D. (2011). Number of survivors in the presence of a demon. To appear in Periodica Mathematica Hungarica.Google Scholar
[9] Neininger, R. (2005). Recursive random variables with subgaussian distributions. Statist. Decisions 23, 131–146.CrossRefGoogle Scholar
[10] Neininger, R. and Rüschendorf, L. (2004). A general limit theorem for recursive algorithms and combinatorial structures. Ann. Appl. Prob. 14, 378–418.CrossRefGoogle Scholar
[11] Papadakis, T., Munroe, J. I. and Poblete, P. V. (1990). Analysis of the expected search cost in skip lists. In SWAT 90 (Bergen, 1990; Lecture Notes Comput. Sci. 447), Springer, Berlin, pp. 160–172.CrossRefGoogle Scholar
[12] Prodinger, H. (1993). How to select a loser. Discrete Math. 120, 149–159.CrossRefGoogle Scholar
[13] Pugh, W. (1989). Skip lists: a probabilistic alternative to balanced trees. In Algorithms and Data Structures (Ottawa, ON, 1989; Lecture Notes Comput. Sci. 382), Springer, Berlin, pp. 437–449.CrossRefGoogle Scholar
[14] Rösler, U. (1991). A limit theorem for “Quicksort”. RAIRO Inf. Théor. Appl. 25, 85–100.CrossRefGoogle Scholar
[15] Rösler, U. and Rüschendorf, L. (2001). The contraction method for recursive algorithms. Algorithmica 29, 3–33.CrossRefGoogle Scholar