Leader election: a Markov chain approach

DOI10.14708/MA.V44I1.1141MaRDI QIDQ5357641zbMATH OpenOpenAlexFDO

Authors Klass Hagemann, Rudolf Grübel

Publication date 12 September 2017

Published in Mathematica Applicanda (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.03047

zbMATH Keywords

boundary theoryelection algorithmsgeometric distributionMarkov chainmaximaperiodicitytail \(\sigma\)-field

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Boundary theory for Markov processes (60J50) Analysis of algorithms (68W40)

Abstract: A well-studied randomized election algorithm proceeds as follows: In each round the remaining candidates each toss a coin and leave the competition if they obtain heads. Of interest is the number of rounds required and the number of winners, both related to maxima of geometric random samples, as well as the number of remaining participants as a function of the number of rounds. We introduce two related Markov chains and use ideas and methods from discrete potential theory to analyse the respective asymptotic behaviour as the initial number of participants grows. One of the tools used is the approach via the R'enyi-Sukhatme representation of exponential order statistics, which was first used in the leader election context by Bruss and Gr"ubel in cite{BrGr03}.

Recommendations

• Leader election using random walks
• A probabilistic analysis of a leader election algorithm
• Asymptotic analysis of a leader election algorithm
• Asymptotic properties of a leader election algorithm
• On the distribution for the duration of a randomized leader election algorithm
• Leader election in the presence of n-1 initial failures
• Leader election in rings of ambient processes
• Leader election in rings of ambient processes
• Leader election in SINR model with arbitrary power control

Cited in

(7)

• The size of the last merger and time reversal in -coalescents
• Bivariate issues in leader election algorithms with Marshall-Olkin limit distribution
• Leader election using random walks
• Leader election in SINR model with arbitrary power control
• A leader-election procedure using records
• The truncated geometric election algorithm: duration of the election
• On distribution of the leadership time in counting votes and predicting winners

This page was built for publication: Leader election: a Markov chain approach

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