Analysis of an asymmetric leader election algorithm
type: Item
instance of: scholarly article
title: Analysis of an asymmetric leader election algorithm
zbMATH Open document ID: 0884.05004
author: Svante Janson
author: Wojciech Szpankowski
published in: The Electronic Journal of Combinatorics
publication date: 1998-02-12T00:00:00Z
full work available at URL: https://eudml.org/doc/119211
review text: Summary: We consider a leader election algorithm in which a set of distributed objects (people, computers, etc.) try to identify one object as their leader. The election process is randomized, that is, at every stage of the algorithm those objects that survived so far flip a ``biased'' coin, and those who received, say a tail, survive for the next round. The process continues until only one object remains. Our interest is in evaluating the limiting distribution and the first two moments of the number of rounds needed to select a leader. We establish precise asymptotics for the first two moments, and show that the asymptotic expression for the duration of the algorithm exhibits some periodic fluctuations and consequently no limiting distribution exists. These results are proved by analytical techniques of the precise analysis of algorithms such as: analytical poissonization and depoissonization, Mellin transform, and complex analysis.
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 1118002
zbMATH Keywords: leader election algorithm
zbMATH Keywords: election process
zbMATH Keywords: limiting distribution
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1118002