Convergence of some leader election algorithms

Details Convergence of some leader election algorithms Convergence of some leader election algorithms

2008-02-11

arxiv.org/abs/0802.1389v1

Computer Science

Distributed, Parallel, and Cluster Computing

27 pages, 13 figures, 5 tables

Scientific paper

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 phases (or rounds) before getting only one player? We present a probabilistic analysis of this algorithm under some conditions on the probability distributions P(n,k), including stochastic monotonicity and the assumption that roughly a fixed proportion alpha of the players survive in each round. We prove a kind of convergence in distribution for X_n-log_a n, where the basis a=1/alpha; as in many other similar problems there are oscillations and no true limit distribution, but suitable subsequences converge, and there is an absolutely continuous random variable Z such that the distribution of X_n can be approximated by Z+log_a n rounded to the nearest larger integer. Applications of the general result include the leader election algorithm where players are eliminated by independent coin tosses and a variation of the leader election algorithm proposed by W.R. Franklin. We study the latter algorithm further, including numerical results.

Affiliated with

Also associated with

No associations

Rating

Convergence of some leader election algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Convergence of some leader election algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Convergence of some leader election algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-625007