On a leader election algorithm: Truncated geometric case study

Recent work of Kalpathy and Mahmoud (in press) gives very general results for a broad class of fair leader election algorithms. They study the duration of contestants, i.e., the number of rounds a randomly selected contestant stays in the competition and another parameter for the associated tree structure. They present a unifying treatment for leader election algorithms, and they show how perpetuities naturally come about. Their theory, however, produces only trivial asymptotic results for the duration of election for some distributions, such as a truncated geometric distribution. In the case of a truncated geometric distribution, the limiting distribution of the duration of contestants is degenerate, and the method of Kalpathy and Mahmoud (in press) does not yield the precise asymptotics. The goal of this short note is to use an alternative method–namely, the q-series methodology–to make a very precise asymptotic analysis of the rate of decay of the mean and the variance of the duration of the election.