Quasi-Optimal Leader Election Algorithms in Radio Networks with Loglogarithmic Awake Time Slots

Simple item page
dc.creatorLavault, Christian
dc.creatorMarckert, Jean-François
dc.creatorRavelomanana, Vlady
dc.date2006-07-08
dc.date.accessioned2026-07-07T07:16:17Z
dc.date.available2026-07-07T07:16:17Z
dc.descriptionA 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 $Ω(\log{(n)})$ time lower-bound established by Kushilevitz and Mansour.
dc.identifierhttps://arxiv.org/abs/cs/0607034
dc.identifierhttp://arxiv.org/abs/cs/0607034
dc.identifier10th IEEE International Conference on Telecommunications (2003) 1113-1119
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/113537
dc.subjectDistributed, Parallel, and Cluster Computing
dc.subjectNetworking and Internet Architecture
dc.titleQuasi-Optimal Leader Election Algorithms in Radio Networks with Loglogarithmic Awake Time Slots
dc.typetext

Files

Collections

arXiv