A Quasi-Optimal Leader Election Algorithm in Radio Networks with Log-Logarithmic Awake Time Slots
<|reference_start|>A Quasi-Optimal Leader Election Algorithm in Radio Networks with Log-Logarithmic Awake Time Slots: Radio networks (RN) are distributed systems (\textit{ad hoc networks}) consisting in $n \ge 2$ radio stations. Assuming the number $n$ unknown, two distinct models of RN without collision detection (\textit{no-CD}) are addressed: the model with \textit{weak no-CD} RN and the one with \textit{strong no-CD} RN. We design and analyze two distributed leader election protocols, each one running in each of the above two (no-CD RN) models, respectively. Both randomized protocols are shown to elect a leader within $\BO(\log{(n)})$ expected time, with no station being awake for more than $\BO(\log{\log{(n)}})$ time slots (such algorithms are said to be \textit{energy-efficient}). Therefore, a new class of efficient algorithms is set up that matchthe $\Omega(\log{(n)})$ time lower-bound established by Kushilevitz and Mansour.<|reference_end|>
@article{lavault2006a,
    title={A Quasi-Optimal Leader Election Algorithm in Radio Networks with
  Log-Logarithmic Awake Time Slots},
    author={Christian Lavault (LIPN), Jean-Franc{c}ois Marckert (LaBRI), Vlady
  Ravelomanana (LIPN)},
    journal={arXiv preprint arXiv:cs/0607028},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0607028},
    primaryClass={cs.DC cs.NI}
}