License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2023.46
URN: urn:nbn:de:0030-drops-175499
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17549/
Efremenko, Klim ;
Kol, Gillat ;
Paramonov, Dmitry ;
Saxena, Raghuvansh R.
Noisy Radio Network Lower Bounds via Noiseless Beeping Lower Bounds
Abstract
Much of today’s communication is carried out over large wireless systems with different input-output behaviors. In this work, we compare the power of central abstractions of wireless communication through the general notion of boolean symmetric f-channels: In every round of the f-channel, each of its n parties decides to either broadcast or not, and the channel outputs f(m), where m is the number of broadcasting parties.
Our first result is that the well studied beeping channel, where f is the threshold-1 function, is not stronger than any other f-channel. To this end, we design a protocol over the f-channel and prove that any protocol that simulates it over the beeping channel blows up the round complexity by a factor of Ω(log n). Our lower bound technique may be of independent interest, as it essentially generalizes the popular fooling set technique by exploiting a "local" relaxation of combinatorial rectangles.
Curiously, while this result shows the limitations of a noiseless channel, namely, the beeping channel, we are able to use it to show the limitations of the noisy version of many other channels. This includes the extensively studied single-hop radio network model with collisions-as-silence (CAS), which is equivalent to the f-channel with f(m) = 1 iff m = 1.
In particular, our second and main result, obtained from the first, shows that converting CAS protocols to noise resilient ones may incur a large performance overhead, i.e., no constant rate interactive code exists. To this end, we design a CAS protocol and prove that any protocol that simulates it over the noisy CAS model with correlated stochastic noise, blows up the round complexity by a factor of Ω(log n). We mention that the Ω(log n) overhead in both our results is tight.
BibTeX - Entry
@InProceedings{efremenko_et_al:LIPIcs.ITCS.2023.46,
author = {Efremenko, Klim and Kol, Gillat and Paramonov, Dmitry and Saxena, Raghuvansh R.},
title = {{Noisy Radio Network Lower Bounds via Noiseless Beeping Lower Bounds}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {46:1--46:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-263-1},
ISSN = {1868-8969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17549},
URN = {urn:nbn:de:0030-drops-175499},
doi = {10.4230/LIPIcs.ITCS.2023.46},
annote = {Keywords: Beeping Model, Radio Networks}
}
|
Keywords: |
|
Beeping Model, Radio Networks |
|
Collection: |
|
14th Innovations in Theoretical Computer Science Conference (ITCS 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
01.02.2023 |
