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!)