Abstract | ||
---|---|---|
We consider the number of survivors in a broad class of fair leader election algorithms after a number of election rounds. We give sufficient conditions for the number of survivors to converge to a product of independent identically distributed random variables. The number of terms in the product is determined by the round number considered. Each individual term in the product is a limit of a scaled random variable associated with the splitting protocol. The proof is established via convergence (to 0) of the first-order Wasserstein distance from the product limit. In a broader context, the paper is a case study of a class of stochastic recursive equations. We give two illustrative examples, one with binomial splitting protocol (for which we show that a normalized version is asymptotically Gaussian) and one with uniform splitting protocol. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1016/j.spl.2013.09.011 | Statistics & Probability Letters |
Keywords | Field | DocType |
60E05,60F05,68W40 | Leader election,Convergence (routing),Randomized algorithm,Discrete mathematics,Random variable,Weak convergence,Algorithm,Gaussian,Statistics,Recursion,Mathematics,Round number | Conference |
Volume | Issue | ISSN |
83 | 12 | 0167-7152 |
Citations | PageRank | References |
2 | 0.43 | 5 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ravi Kalpathy | 1 | 2 | 0.43 |
Hosam M. Mahmoud | 2 | 183 | 55.63 |
Walter Rosenkrantz | 3 | 2 | 0.43 |