First Order Asymptotic Variance of a Leader Election Algorithm

• Activity Number: 183 - Contributed Poster Presentations: IMS
• Type: Contributed
• Date/Time: Monday, July 30, 2018 : 10:30 AM to 12:20 PM
• Sponsor: IMS
• Author(s): Simon Langowski* and Mark Daniel Ward
• Companies: Purdue University and Purdue University
• Keywords: asymptotic; leader election; generating functions

Abstract

In 2012, Gaither and Ward discovered the first-order asymptotic growth of the expected number of items chosen in a leader election algorithm, introduced by Krieger, Pollak, and Samuel-Cahn (2007). In our analysis, S. Langowski and M. D. Ward analyze the first-order asymptotic growth for the variance of this leader election algorithm. The analysis utilizes probability generating functions, differential equations, and asymptotic analysis. This research is supported under NSF grant 1246818.