Quasi-Optimal Leader Election Algorithms in Radio Networks

in Radio Networks with Log-logarithmic Awake Time Slots

A radio network (RN) is a distributed system consisting of n radio stations. We address
the problem of designing and analyzing distributed leader election protocols in a RN,
under the assumptions that no collision detection mechanism is available and that the number
$n$ of radio stations is unknown. In this paper, we are interested in protocols that allow
the stations to keep asleep as long as possible, thus minimizing their awake time slots
(such algorithms are called ``energy-efficient''). We set up a new class of randomized
algorithms in RN, that elect a leader in O(log(n)) expected time with no station
being awake for more than $O(\log{\log{(n)}})$ time slots. Our algorithms are shown to
match the Omega(log(n)) time lower-bound established by
Kushilevitz and Mansour.
Moreover, in terms of overall energy consumption of the n-station RN,
the class of such leader election algorithms achieves O(n log log(n)) awake time
complexity, whereas all previous leader election algorithms require O(n log(n)) time.