A Quasi-Optimal Leader Election Algorithm in Radio Networks with Log-Logarithmic Awake Time Slots

Details A Quasi-Optimal Leader Election Algorithm in Radio Networks with Log-Logarithmic Awake Time Slots A Quasi-Optimal Leader Election Algorithm in Radio Networks with Log-Logarithmic Awake Time Slots

2006-07-07

arxiv.org/abs/cs/0607028v1

Computer Science

Distributed, Parallel, and Cluster Computing

Scientific paper

Radio networks (RN) are distributed systems (\textit{ad hoc networks}) consisting in $n \ge 2$ radio stations. Assuming the number $n$ unknown, two distinct models of RN without collision detection (\textit{no-CD}) are addressed: the model with \textit{weak no-CD} RN and the one with \textit{strong no-CD} RN. We design and analyze two distributed leader election protocols, each one running in each of the above two (no-CD RN) models, respectively. Both randomized protocols are shown to elect a leader within $\BO(\log{(n)})$ expected time, with no station being awake for more than $\BO(\log{\log{(n)}})$ time slots (such algorithms are said to be \textit{energy-efficient}). Therefore, a new class of efficient algorithms is set up that matchthe $\Omega(\log{(n)})$ time lower-bound established by Kushilevitz and Mansour.

Affiliated with

Also associated with

No associations

Rating

A Quasi-Optimal Leader Election Algorithm in Radio Networks with Log-Logarithmic Awake Time Slots 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 A Quasi-Optimal Leader Election Algorithm in Radio Networks with Log-Logarithmic Awake Time Slots, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Quasi-Optimal Leader Election Algorithm in Radio Networks with Log-Logarithmic Awake Time Slots will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-96459