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.2019.8
URN: urn:nbn:de:0030-drops-113152
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11315/
Braverman, Mark ;
Kol, Gillat ;
Oshman, Rotem ;
Tal, Avishay
On the Computational Power of Radio Channels
Abstract
Radio networks can be a challenging platform for which to develop distributed algorithms, because the network nodes must contend for a shared channel. In some cases, though, the shared medium is an advantage rather than a disadvantage: for example, many radio network algorithms cleverly use the shared channel to approximate the degree of a node, or estimate the contention. In this paper we ask how far the inherent power of a shared radio channel goes, and whether it can efficiently compute "classicaly hard" functions such as Majority, Approximate Sum, and Parity.
Using techniques from circuit complexity, we show that in many cases, the answer is "no". We show that simple radio channels, such as the beeping model or the channel with collision-detection, can be approximated by a low-degree polynomial, which makes them subject to known lower bounds on functions such as Parity and Majority; we obtain round lower bounds of the form Omega(n^{delta}) on these functions, for delta in (0,1). Next, we use the technique of random restrictions, used to prove AC^0 lower bounds, to prove a tight lower bound of Omega(1/epsilon^2) on computing a (1 +/- epsilon)-approximation to the sum of the nodes' inputs. Our techniques are general, and apply to many types of radio channels studied in the literature.
BibTeX - Entry
@InProceedings{braverman_et_al:LIPIcs:2019:11315,
author = {Mark Braverman and Gillat Kol and Rotem Oshman and Avishay Tal},
title = {{On the Computational Power of Radio Channels}},
booktitle = {33rd International Symposium on Distributed Computing (DISC 2019)},
pages = {8:1--8:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-126-9},
ISSN = {1868-8969},
year = {2019},
volume = {146},
editor = {Jukka Suomela},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11315},
URN = {urn:nbn:de:0030-drops-113152},
doi = {10.4230/LIPIcs.DISC.2019.8},
annote = {Keywords: radio channel, lower bounds, approximate majority}
}
|
Keywords: |
|
radio channel, lower bounds, approximate majority |
|
Collection: |
|
33rd International Symposium on Distributed Computing (DISC 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
08.10.2019 |
