Convergence of some leader election algorithms
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 \emph{phases} (or rounds) before getting only one player? We present a probabilistic analysis of this algorit...
Main Authors: | Svante Janson, Christian Lavault, Guy Louchard |
---|---|
Format: | Article |
Language: | English |
Published: |
Discrete Mathematics & Theoretical Computer Science
2008-01-01
|
Series: | Discrete Mathematics & Theoretical Computer Science |
Subjects: | |
Online Access: | https://dmtcs.episciences.org/437/pdf |
Similar Items
-
Asymptotic behavior of some statistics in Ewens random permutations
by: Valentin Feray
Published: (2012-01-01) -
Support and density of the limit $m$-ary search trees distribution
by: Brigitte Chauvin, et al.
Published: (2012-01-01) -
Mean field analysis for inhomogeneous bike sharing systems
by: Christine Fricker, et al.
Published: (2012-01-01) -
Exactly Solvable Balanced Tenable Urns with Random Entries via the Analytic Methodology
by: Basile Morcrette, et al.
Published: (2012-01-01) -
Noncommutative symmetric functions III : Deformations of Cauchy and convolution algebras
by: Gérard Duchamp, et al.
Published: (1997-01-01)