Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-12-02T19:21:13.364Z Has data issue: false hasContentIssue false
  • English
  • Français

Asymptotic and numerical studies of the leader election algorithm

Published online by Cambridge University Press:  01 February 2002

CHARLES KNESSL
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
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

Type
Research Article
Information
European Journal of Applied Mathematics , Volume 12 , Issue 6 , December 2001 , pp. 645 - 664
Copyright
2001 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)