Electing a leader in multi-hop radio networks

Research output: Chapter in Book/Report/Conference proceedingConference contribution

16 Scopus citations


We consider the task of electing a leader in a distributed manner in ad hoc multi-hop radio networks. Radio networks represent the class of wireless networks in which one frequency is used for transmissions, network's topology can be represented by a simple undirected graph with some n nodes, and there is no collision detection. We give a randomized algorithm electing a leader in O(n) expected time and prove that this time bound is optimal. We give a deterministic algorithm electing a leader in O(n log3/2 n √log log n) time. By way of application, we show how to perform gossiping with combined messages in O(n log3/2 n√log log n) time by a deterministic algorithm, and in O(n) expected time by a randomized algorithm.

Original languageEnglish (US)
Title of host publicationPrinciples of Distributed Systems - 16th International Conference, OPODIS 2012, Proceedings
Number of pages15
StatePublished - 2012
Externally publishedYes
Event16th International Conference on Principles of Distributed Systems, OPODIS 2012 - Rome, Italy
Duration: Dec 18 2012Dec 20 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7702 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference16th International Conference on Principles of Distributed Systems, OPODIS 2012


  • distributed algorithm
  • gossiping
  • leader election
  • lower bound
  • radio network
  • randomization

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Electing a leader in multi-hop radio networks'. Together they form a unique fingerprint.

Cite this