AModified O(n) Leader Election Algorithm for Complete Networks
Maria Castillo, F. Fariña, Alberto Córdoba, Jesús Villadangos · Proceedings - Euromicro Workshop on Parallel and Distributed Processing/Proceedings · 2007
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