On the distribution for the duration of a randomized leader election algorithm

DOI10.1214/aoap/1035463332zbMath0870.60018OpenAlexW2035490304MaRDI QIDQ1354843

James Allen Fill, Hosam M. Mahmoud, Wojciech Szpankowski

Publication date: 12 June 1997

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

Full work available at URL: https://doi.org/10.1214/aoap/1035463332

zbMATH Keywords

heightasymptotic distributiondistributed computingrandom treestriesleader electionPoissonizationde-Poissonization

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Extreme value theory; extremal stochastic processes (60G70)

Related Items

One-sided variations on binary search trees ⋮ Bivariate issues in leader election algorithms with Marshall-Olkin limit distribution ⋮ On the contraction method with degenerate limit equation. ⋮ On the distribution for the duration of a randomized leader election algorithm ⋮ Normal limiting distribution of the size of binary interval trees ⋮ Quasi-optimal energy-efficient leader election algorithms in radio networks ⋮ Analytical depoissonization and its applications ⋮ Stochastic coalescence in logarithmic time ⋮ An analytic approach to the asymptotic variance of trie statistics and related structures ⋮ Survivors in leader election algorithms ⋮ On the multiplicity of the maximum in a discrete random sample ⋮ On a leader election algorithm: truncated geometric case study ⋮ The asymmetric leader election algorithm: another approach ⋮ On tries, contention trees and their analysis ⋮ Asymptotic Properties of a Leader Election Algorithm ⋮ Block size in geometric(\(p\))-biased permutations ⋮ Perpetuities in Fair Leader Election Algorithms ⋮ The oscillatory distribution of distances in random tries ⋮ Asymptotic analysis of a leader election algorithm ⋮ From coin tossing to rock-paper-scissors and beyond: a log-exp gap theorem for selecting a leader ⋮ One-sided variations on interval trees ⋮ The asymmetric leader election algorithm: Number of survivors near the end of the game ⋮ Leader election using random walks ⋮ Sorting algorithms for broadcast communications: mathematical analysis. ⋮ Unnamed Item ⋮ 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Mellin transforms and asymptotics: Harmonic sums
• Mellin transforms and asymptotics: Finite differences and Rice's integrals
• Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees
• How to select a loser
• On the performance evaluation of extendible hashing and trie searching
• Asymptotical growth of a class of random trees
• Probabilistic counting algorithms for data base applications
• Approximating functions by their Poisson transform
• Probability approximations via the Poisson clumping heuristic
• A study of trie-like structures under the density model
• Independent process approximations for random combinatorial structures
• On the distribution for the duration of a randomized leader election algorithm
• How many random questions are necessary to identify \(n\) distinct objects?
• Paths in a random digital tree: limiting distributions
• On Birthday, Collectors', Occupancy and Other Classical Urn Problems
• The analysis of linear probing sort by the use of a new mathematical transform
• Solution of a Linear Recurrence Equation Arising in the Analysis of Some Algorithms
• Analysis of Extendible Hashing
• Searching for losers
• Limiting Distribution for the Depth in PATRICIA Tries
• Ultimate Characterizations of the Burst Response of an Interval Searching Algorithm: A Study of a Functional Equation
• New results on the size of tries
• Extreme value theory for a class of discrete distributions with applications to some stochastic processes
• On Deviations between Theoretical and Empirical Distributions