 On a leader election algorithm: Truncated geometric case studyRavi Kalpathy and Mark Daniel Ward Statistics & Probability Letters, 2014, vol. 87, issue C, 40-47 Abstract: 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. Keywords: Analysis of algorithms; Leader election; Recurrence; q-series (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:stapro:v:87:y:2014:i:c:p:40-47 Ordering information: This journal article can be ordered from DOI: 10.1016/j.spl.2013.12.020 Access Statistics for this article Statistics & Probability Letters is currently edited by Somnath Datta and Hira L. Koul More articles in Statistics & Probability Letters from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.