Towards Fair Leader Election in Wireless Networks

  Zbigniew Golebiewski, Marek Klonowski,  Michal Koza, Miroslaw Kutylowski

               Institute of Mathematics and Computer Science
                     Wroclaw University of Technology

In this paper we consider a leader election problem in ad-hoc single hop radio network 
with an adversary. The aim of the adversary is to be chosen a leader. In many scenarios
it can be a staring point for performing other attacks and taking control over the whole
network.

In our paper we show that in typical and well-known algorithms it is not possible to avoid
this danger i.e. the adversary can always use such strategy that the node under its control
becomes a leader with high probability. This attack is efficient even if the adversary controls
very small number of nodes. Moreover, we show that it is not possible in practice even 
to detect such malicious behaviour.

Our second contribution is a new leader election algorithm that provides to some extent 
immunity against this types of attack. We consider several realistic network models and 
we design appropriate methods for each of them. We also show that in some scenarios 
it is not possible to keep the adversary from becoming the leader.

AD HOC NOW'2009, LNCS