Electronic Thesis/Dissertation
Perpetuities in Fair Leader Election Algorithms Open Access
Downloadable Content
Download PDFWe 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 firstorder Wasserstein distance from the geometric limit. For the normalized overall cost, the method of proof is also convergence of the firstorder Wasserstein distance, augmented with an argument based on a contraction mapping in the firstorder 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 onesided 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 firstorder and secondorder 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).

Author
Language
Keyword
Date created
Type of Work
Rights statement
GW Unit
Degree
Advisor
Committee Member(s)
Persistent URL
 License
Relationships
Items
Thumbnail  Title  Date Uploaded  Visibility  Actions 

Kalpathy_gwu_0075A_11911.pdf  20180116  Open Access 
