Asymptotic Properties of a Leader Election Algorithm

DOI10.1239/jap/1308662645zbMath1219.60008OpenAlexW2067119472MaRDI QIDQ3014993

Mark Daniel Ward, Hosam M. Mahmoud, Ravi Kalpathy

Publication date: 8 July 2011

Published in: Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/6b64bcbd003d7be12b6478bfe37073b87b89bb46

zbMATH Keywords

weak convergencefixed pointcontraction methodleader electionanalytic combinatoricsRice's methodWasserstein metric space

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Central limit and other weak theorems (60F05) Trees (05C05) Combinatorial probability (60C05)

Related Items

Bivariate issues in leader election algorithms with Marshall-Olkin limit distribution, Survivors in leader election algorithms, On a leader election algorithm: truncated geometric case study, Perpetuities in Fair Leader Election Algorithms, The asymmetric leader election algorithm: Number of survivors near the end of the game, Analysis of fully distributed splitting and naming probabilistic procedures and applications, Analysis of Fully Distributed Splitting and Naming Probabilistic Procedures and Applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Mellin transforms and asymptotics: Finite differences and Rice's integrals
• How to select a loser
• A limit theory for random skip lists
• On the distribution for the duration of a randomized leader election algorithm
• Analysis of an asymmetric leader election algorithm
• A general limit theorem for recursive algorithms and combinatorial structures
• The contraction method for recursive algorithms
• Number of survivors in the presence of a demon
• Recursive random variables with subgaussian distributions
• Advancing in the presence of a demon
• A limit theorem for “quicksort”