AModified O(n) Leader Election Algorithm for Complete Networks

This paper presents a modified leader election algorithm for complete networks without sense of direction. The original algorithm, introduced by Villadangos et al. in (2005), had the aim of reducing the number of exchanged messages in order to select a leader. However, the original O(n) algorithm fails to choose a leader on several occasions. A modified algorithm, which eliminates the problems that cause the wrong behaviour, is proposed. It is formally proved that the new algorithm verifies the correctness criteria that consist of selecting a unique leader in every case. Additionally, the algorithm maintains the O(n) complexity in both messages and time, where n is the number of nodes in the system