Adversary Immune Leader Election in Ad Hoc Radio Networks

Miroslaw Kutylowski,  Wojciech Rutkowski

Abstract

Recently, many leader election algorithms have been designed for ad  hoc
radio  networks.  These solutions are aimed to be efficient with respect
to time complexity and energy cost. They work quite  well  even  in  the
no-collision detection (no-CD) model.

All these algorithms are quite fragile in the sense  that  an  adversary
may  easily  disturb  communication so that the result of computation is
faulty. As a consequence, more than one station may regard itself as the
leader.  This is a severe fault, since leader election is intended to be
a subroutine used to avoid collisions. The reason for this phenomenon is
that  so  far  leader  election  algorithm eliminated candidates for the
leader so that finally exactly one candidate  survives.  At  the  moment
when  few  candidates remain it is easy to disturb communication so that
each of them thinks he is the only remaining candidate. Energy  cost  of
the adversary is very low.

It is impossible to make leader  election  algorithm  totally  resistant
against  an  adversary  --  if it is broadcasting all the time it causes
collisions all the time and destroys any communication. So  we  consider
the  case  that  an adversary has limited energy resources, as any other
participant.

We present a new approach that yields a leader election algorithm for  a
single-hop  no-CD  radio  network.  The  algorithm  has  time complexity
O(log^3 N) and energy cost O(sqrt(log N)). This is worse than  the  best
algorithms  constructed  so  far (O(log N) time and O(log star N) energy
cost), but  suceeds  in  presence  of  an  adversary  with  energy  cost
eta=Theta(log N) with probability 2^(-Omega(sqrt(log N))). (The log star
energy cost algorithm can be efficiently attacked by an adversary with a
constant energy cost!)