2006/07/07 by Christian Lavault, Lavault, Christian, Jean-François Marckert +3
Computer Science · #Distributed #FOS: Computer and information sciences #Networking and Internet Architecture (cs.NI) #Parallel #and Cluster Computing (cs.DC) #cs.DC #cs.NI
paper · pdf · doi:10.48550/arxiv.cs/0607028
arxiv created 2006/07/07 · arxiv updated 2009/12/01
Radio networks (RN) are distributed systems (ad hoc networks) consisting in n ≥ 2 radio stations. Assuming the number n unknown, two distinct models of RN without collision detection (no-CD) are addressed: the model with weak no-CD RN and the one with 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(loglog(n)) time slots (such algorithms are said to be energy-efficient). Therefore, a new class of efficient algorithms is set up that matchthe Ω(log(n)) time lower-bound established by Kushilevitz and Mansour.