Perpetuities in Fair Leader Election Algorithms. (March 2014)

• Record Type: Journal Article
• Authors: Kalpathy, Ravi; Mahmoud, Hosam
• Is Part Of: Advances in applied probability. Volume 46:Number 1(2014)
• Page Start: 203
• Page End: 216
• Publication Date: 2014-03
• Subjects: Leader election, -- recurrence, -- functional equation, -- fixed point, -- contraction method, -- metric space, -- perpetuity, -- weak convergence; 60C05, -- 60F05, -- 68W40; Probabilities -- Periodicals; Stochastic models -- Periodicals; Electronic journals; Periodicals; 519.2
• DOI: 10.1239/aap/1396360110
• Languages: English
• ISSNs: 0001-8678

Abstract

Abstract : We consider a broad class of fair leader election algorithms, and study the duration of contestants (the number of rounds a randomly selected contestant stays in the competition) and the overall cost of the algorithm. We give sufficient conditions for the duration to have a geometric limit distribution (a perpetuity built from Bernoulli random variables), and for the limiting distribution of the total cost (after suitable normalization) to be a perpetuity. For the duration, the proof is established via convergence (to 0) 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 use of these two steps is commonly referred to as the contraction method.