ECCC-Report TR19-132https://eccc.weizmann.ac.il/report/2019/132Comments and Revisions published for TR19-132en-usMon, 30 Sep 2019 20:48:38 +0300
Paper TR19-132
| Radio Network Coding Requires Logarithmic Overhead |
Raghuvansh Saxena,
Klim Efremenko,
Gillat Kol
https://eccc.weizmann.ac.il/report/2019/132We consider the celebrated radio network model for abstracting communication in wireless networks. In this model, in any round, each node in the network may broadcast a message to all its neighbors. However, a node is able to hear a message broadcast by a neighbor only if no collision occurred, meaning that it was the only neighbor broadcasting.
While the (noiseless) radio network model received a lot of attention over the last few decades, the effect of noise on radio networks is still not well understood. In this paper, we take a step forward and show that making radio network protocols resilient to noise may require a substantial performance overhead. Specifically, we construct a multi-hop network and a communication protocol over this network that works in $T$ rounds when there is no noise. We prove that any scheme that simulates our protocol and is resilient to stochastic noise, requires $\Omega(T \log n)$ rounds.
This stands in contrast to our previous result (STOC, 2018), showing that protocols over the single-hop (clique) network can be made noise resilient with only a constant overhead. Our result also settles a recent conjecture by Censor{-}Hillel, Haeupler, Hershkowitz, Zuzic (2018).
We complement the above result by giving a scheme to simulate any protocol with a fixed order of transmissions with only an $\mathcal{O}(\log n)$ overhead.Mon, 30 Sep 2019 20:48:38 +0300https://eccc.weizmann.ac.il/report/2019/132