Efficient Algorithms for Leader Election in Radio Networks

         Tomasz Jurdzinski, Miroslaw Kutylowski, Jan Zatopianski

We present energy efficient algorithms for  leader  election  in  single
channel  single-hop  radio  networks  with  no  collision  detection. We
present a deterministic solution with sublogarithmic  energy  cost  (the
best  previous  result was O(log n)) and show a double logarithmic lower
bound. We prove that this lower bound holds in a randomized case,  in  a
certain sense.

For the case, when the number $n$ of active stations can be approximated
in  advance,  we  show  a  randomized  algorithm with energy consumption
O(\log^*n) that yields a result with high probability (the best previous
result was O(loglog n)).