@inproceedings{c4040b7081e8407faa2abb6310c05820,
title = "Lower bounds for clear transmissions in radio networks",
abstract = "We show new lower bounds for collision-free transmissions in Radio Networks. Our main result is a tight lower bound of Ω(log n log(1/ε)) on the time required by a uniform randomized protocol to achieve a clear transmission with success probability 1 - ε in a one-hop setting. This result is extended to non-uniform protocols as well. A new lower bound is proved for the important multi-hop setting of nodes distributed as a connected Random Geometric Graph. Our main result is tight for a variety of problems.",
keywords = "Ad-hoc network, Broadcast, Contention resolution, Dominating set, Leader election, Lower bound, Maximal independent set, Radio network, Random geometric graphs, Sensor network, Station selection, Wake up, Weak Sensor Model. ACM-class: F.2.2",
author = "Mart{\'i}n Farach-Colton and Fernandes, {Rohan J.} and Mosteiro, {Miguel A.}",
year = "2006",
doi = "10.1007/11682462_42",
language = "English (US)",
isbn = "354032755X",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "447--454",
booktitle = "LATIN 2006",
note = "LATIN 2006: Theoretical Informatics - 7th Latin American Symposium ; Conference date: 20-03-2006 Through 24-03-2006",
}