Convergence of some leader election algorithms

MaRDI QIDQ3575440zbMATH OpenFDO

Authors Svante Janson, Christian Lavault, Guy Louchard

Publication date 27 July 2010

Full work available at URL https://arxiv.org/abs/0802.1389, https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/950/0.html

zbMATH Keywords

convergence in distributionleader election algorithmsoscillations

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05)

Abstract: We start with a set of n players. With some probability P(n,k), we kill n-k players; the other ones stay alive, and we repeat with them. What is the distribution of the number X_n of phases (or rounds) before getting only one player? We present a probabilistic analysis of this algorithm under some conditions on the probability distributions P(n,k), including stochastic monotonicity and the assumption that roughly a fixed proportion alpha of the players survive in each round. We prove a kind of convergence in distribution for X_n-log_a n, where the basis a=1/alpha; as in many other similar problems there are oscillations and no true limit distribution, but suitable subsequences converge, and there is an absolutely continuous random variable Z such that the distribution of X_n can be approximated by Z+log_a n rounded to the nearest larger integer. Applications of the general result include the leader election algorithm where players are eliminated by independent coin tosses and a variation of the leader election algorithm proposed by W.R. Franklin. We study the latter algorithm further, including numerical results.

Recommendations

• The asymmetric leader election algorithm: number of survivors near the end of the game
• Asymptotic properties of a leader election algorithm
• Survivors in leader election algorithms
• Survivors in Leader Election Algorithms
• Analysis of an asymmetric leader election algorithm

Cited in

(16)

• Survivors in leader election algorithms
• On a leader election algorithm: truncated geometric case study
• Bivariate issues in leader election algorithms with Marshall-Olkin limit distribution
• Leader election using random walks
• Asymptotic properties of a leader election algorithm
• On leader green election
• A binomial splitting process in connection with corner parking problems
• The Swedish leader election protocol: analysis and variations
• Perpetuities in fair leader election algorithms
• Survivors in Leader Election Algorithms
• The asymmetric leader election algorithm: number of survivors near the end of the game
• The asymmetric leader election algorithm with Swedish stopping: a probabilistic analysis
• Perpetuities in fair leader election algorithms
• A leader-election procedure using records
• How to select a loser
• Convergence results for unanimous voting

This page was built for publication: Convergence of some leader election algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3575440)