Quasi-optimal leader election algorithms in radio networks with log-logarithmic awake time-slots
Christian Lavault, Jean‐François Marckert, Vlady Ravelomanana · 2003
A radio network (RN) is a distributed system consisting of n radio stations. We designed and analyzed two distributed leader election protocols in RN where the number n of radio stations is unknown. The first algorithm runs under the assumption of limited collision detection, while the second assumes that no collision detection is available. By "limited collision detection", we mean that if exactly one station sends (broadcast) a message, then all stations (including the transmitter) that are listening at this moment receive the sent message. By contrast, the second no-collision-detection algorithm assumes that a station cannot simultaneously send and listen to signals. Moreover, both protocols allow the stations to keep asleep as long as possible, thus minimizing their awake time slots (such algorithms are called energy-efficient). Both randomized protocols in RN are shown to elect a leader in O (log (n)) expected time, with no station being awake for more than O (log log (n)) time slots. Therefore, a new class of efficient algorithm is set up that matches the /spl Omega/(log (n)) time lower-bound established by Kushilevitz and Mansour (1998).