Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR19-132 | 26th September 2019 23:18

Radio Network Coding Requires Logarithmic Overhead


Authors: Klim Efremenko, Gillat Kol, Raghuvansh Saxena
Publication: 30th September 2019 20:48
Downloads: 175


We 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.

ISSN 1433-8092 | Imprint