Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-19T06:33:11.348Z Has data issue: false hasContentIssue false

Asymptotic and numerical studies of the leader election algorithm

Published online by Cambridge University Press:  01 February 2002

CHARLES KNESSL
Affiliation:
Department of Mathematics, Statistics and Computer Science (M/C 249), University of Illinois at Chicago, 851 South Morgan Street, Chicago, IL 60607-7045, USA
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A leader is to be elected from n people using the following algorithm. Each person flips a coin. Those people who wind up with tails (which occurs with probability p, 0 < p < 1) move on to the next stage. Those with heads are eliminated. Let Hn denote the number of stages needed until there is a single winner. We analyze the moments and the probability distribution of Hn. In the symmetric model we have an unbiased coin with p = 1/2; in the asymmetric model p ≠ 1/2. We analyze these models asymptotically, for n → ∞, using a variety of analytical and numerical approaches. This leads to simple derivations of some existing results, as well as some new results for the asymmetric case. Our analysis makes some assumptions about the forms of various asymptotic expansions as well as their asymptotic matching.

Information

Type
Research Article
Copyright
2001 Cambridge University Press