A Quasi-Optimal Leader Election Algorithm in Radio Networks with Log-Logarithmic Awake Time Slots
| dc.creator | Lavault, Christian | |
| dc.creator | Marckert, Jean-François | |
| dc.creator | Ravelomanana, Vlady | |
| dc.date | 2006-07-07 | |
| dc.date.accessioned | 2026-07-07T07:16:17Z | |
| dc.date.available | 2026-07-07T07:16:17Z | |
| dc.description | 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 $Ω(\log{(n)})$ time lower-bound established by Kushilevitz and Mansour. | |
| dc.identifier | https://arxiv.org/abs/cs/0607028 | |
| dc.identifier | http://arxiv.org/abs/cs/0607028 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/113534 | |
| dc.subject | Distributed, Parallel, and Cluster Computing | |
| dc.subject | Networking and Internet Architecture | |
| dc.title | A Quasi-Optimal Leader Election Algorithm in Radio Networks with Log-Logarithmic Awake Time Slots | |
| dc.type | text |