License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2018.15
URN: urn:nbn:de:0030-drops-98047
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9804/
Czumaj, Artur ;
Davies, Peter
Deterministic Blind Radio Networks
Abstract
Ad-hoc radio networks and multiple access channels are classical and well-studied models of distributed systems, with a large body of literature on deterministic algorithms for fundamental communications primitives such as broadcasting and wake-up. However, almost all of these algorithms assume knowledge of the number of participating nodes and the range of possible IDs, and often make the further assumption that the latter is linear in the former. These are very strong assumptions for models which were designed to capture networks of weak devices organized in an ad-hoc manner. It was believed that without this knowledge, deterministic algorithms must necessarily be much less efficient.
In this paper we address this fundamental question and show that this is not the case. We present deterministic algorithms for blind networks (in which nodes know only their own IDs), which match or nearly match the running times of the fastest algorithms which assume network knowledge (and even surpass the previous fastest algorithms which assume parameter knowledge but not small labels).
Specifically, in multiple access channels with k participating nodes and IDs up to L, we give a wake-up algorithm requiring O((k log L log k)/(log log k)) time, improving dramatically over the O(L^3 log^3 L) time algorithm of De Marco et al. (2007), and a broadcasting algorithm requiring O(k log L log log k) time, improving over the O(L) time algorithm of Gasieniec et al. (2001) in most circumstances. Furthermore, we show how these same algorithms apply directly to multi-hop radio networks, achieving even larger running time improvements.
BibTeX - Entry
@InProceedings{czumaj_et_al:LIPIcs:2018:9804,
author = {Artur Czumaj and Peter Davies},
title = {{Deterministic Blind Radio Networks}},
booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)},
pages = {15:1--15:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-092-7},
ISSN = {1868-8969},
year = {2018},
volume = {121},
editor = {Ulrich Schmid and Josef Widder},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9804},
URN = {urn:nbn:de:0030-drops-98047},
doi = {10.4230/LIPIcs.DISC.2018.15},
annote = {Keywords: Broadcasting, Deterministic Algorithms, Radio Networks}
}
|
Keywords: |
|
Broadcasting, Deterministic Algorithms, Radio Networks |
|
Collection: |
|
32nd International Symposium on Distributed Computing (DISC 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
04.10.2018 |
