| We consider a broad class of fair leader election algorithms, and study the duration of contestants and the overall cost of the algorithm. We give sufficient conditions for the duration and the normalized total cost to have a geometric and a perpetuity limit law respectively. For the duration, the proof is established via convergence of the first-order Wasserstein distance from the geometric limit. For the normalized overall cost, the method of proof is also convergence of the first-order Wasserstein distance, augmented with an argument based on a contraction mapping in the first-order Wasserstein metric space to show that the limit approaches a unique fixed point solution of a perpetuity distributional equation. The two steps are commonly referred to as the contraction method.;Our main contribution is to present a unifying treatment for leader election algorithms and see how perpetuities naturally come about. In the past, leader election algorithms have been discussed via a variety of methods, such as analytic techniques, poissonization, integral transforms, etc., which may work for some splitting protocols but not the others. Our treatment covers one-sided leader election algorithms represented by a certain stochastic recurrence with linearly bounded toll functions.;We give several examples to illustrate the asymptotic theory presented. In the first example, we study the scenario when the size of the set produced at each stage follows a discrete uniform distribution. In this example we go a little beyond asymptotics into areas such as exact moments and rates of convergence. In the second example, we obtain the limit distributions for the duration and the overall cost for the power distributions. The third example is the classic binomial case, where the leader election is done via coin flipping. We obtain the geometric limit distribution for the duration and further show that the lower order asymptotics may have fluctuations. For the total cost we obtain the first-order and second-order asymptotics. We also specify a rate of convergence for the weak law in the form of a central limit theorem. The fourth example explores the asymptotic distribution for the duration and cost when the advancing set has a size which has a distribution involving atoms. In the final example, we obtain the limit distributions for the duration and cost when the selection process is carried out in the form of a tournament bracket.;For the duration of a contestant, the only aspect of the limiting distribution of the selection algorithm that enters the picture in the geometric limit is its mean. All distributions of the splitting protocols that have the same limiting mean will have the same geometric limit law. This shows that fair leader election is a robust algorithm across a wide variety of splitting protocols. For instance, the uniform splitting, binomial splitting, and certain ladder contests, albeit remarkable differences among these splitting protocols, all have the same geometric limit for the duration of participants. Findings in the dissertation appear in the Journal of Applied Probability, Vol. 48 (2011) and Advances in Applied Probability, Vol. 46 (2014). |
