Quasi-Optimal Leader Election Algorithms in Radio Networks with Loglogarithmic Awake Time Slots
<|reference_start|>Quasi-Optimal Leader Election Algorithms in Radio Networks with Loglogarithmic Awake Time Slots: A radio network (RN) is a distributed system consisting of $n$ radio stations. We design and analyze two distributed leader election protocols in RN where the number $n$ of radio stations is unknown. The first algorithm runs under the assumption of {\it limited collision detection}, while the second assumes that {\it no collision detection} is available. By ``limited collision detection'', we mean that if exactly one station sends (broadcasts) 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 signals. Moreover, both protocols allow the stations to keep asleep as long as possible, thus minimizing their awake time slots (such algorithms are called {\it energy-efficient}). Both randomized protocols in RN areshown 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 algorithms is set up that match the $\Omega(\log{(n)})$ time lower-bound established by Kushilevitz and Mansour.<|reference_end|>
@article{lavault2006quasi-optimal,
    title={Quasi-Optimal Leader Election Algorithms in Radio Networks with
  Loglogarithmic Awake Time Slots},
    author={Christian Lavault (LIPN), Jean-Franc{c}ois Marckert (LaBRI), Vlady
  Ravelomanana (LIPN)},
    journal={10th IEEE International Conference on Telecommunications (2003)
  1113-1119},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0607034},
    primaryClass={cs.DC cs.NI}
}