@inproceedings{df55c12146c14ef5bd34c896509d3464,
title = "Electing a leader in multi-hop radio networks",
abstract = "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.",
keywords = "distributed algorithm, gossiping, leader election, lower bound, radio network, randomization",
author = "Chlebus, {Bogdan S.} and Kowalski, {Dariusz R.} and Andrzej Pelc",
year = "2012",
doi = "10.1007/978-3-642-35476-2_8",
language = "English (US)",
isbn = "9783642354755",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "106--120",
booktitle = "Principles of Distributed Systems - 16th International Conference, OPODIS 2012, Proceedings",
note = "16th International Conference on Principles of Distributed Systems, OPODIS 2012 ; Conference date: 18-12-2012 Through 20-12-2012",
}