Quasi-Optimal Leader Election Algorithms in Radio Networks with Loglogarithmic Awake Time Slots

Details Quasi-Optimal Leader Election Algorithms in Radio Networks with Loglogarithmic Awake Time Slots Quasi-Optimal Leader Election Algorithms in Radio Networks with Loglogarithmic Awake Time Slots

2006-07-08

arxiv.org/abs/cs/0607034v1

10th IEEE International Conference on Telecommunications (2003) 1113-1119

Computer Science

Distributed, Parallel, and Cluster Computing

Scientific paper

A radio network (RN) is a distributed system consisting of $n$ radio stations. We design and analyze two distributed leader election protocols in RN where the number $n$ of radio stations is unknown. The first algorithm runs under the assumption of {\it limited collision detection}, while the second assumes that {\it no collision detection} is available. By ``limited collision detection'', we mean that if exactly one station sends (broadcasts) a message, then all stations (including the transmitter) that are listening at this moment receive the sent message. By contrast, the second no-collision-detection algorithm assumes that a station cannot simultaneously send and listen signals. Moreover, both protocols allow the stations to keep asleep as long as possible, thus minimizing their awake time slots (such algorithms are called {\it energy-efficient}). Both randomized protocols in RN areshown to elect a leader in $O(\log{(n)})$ expected time, with no station being awake for more than $O(\log{\log{(n)}})$ time slots. Therefore, a new class of efficient algorithms is set up that match the $\Omega(\log{(n)})$ time lower-bound established by Kushilevitz and Mansour.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-347664