Skip to main content

Radio Network Coding Requires Logarithmic Overhead

Author(s): Efremenko, Klim; Kol, Gillat; Saxena, Raghuvansh

To refer to this page use:
Abstract: 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 at least cT log(n) rounds, for some constant c. 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 O(log (n)) overhead.
Publication Date: 2019
Citation: Efremenko, Klim, Gillat Kol, and Raghuvansh Saxena. "Radio Network Coding Requires Logarithmic Overhead." IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) (2019), pp. 348-369. doi:10.1109/FOCS.2019.00030
DOI: 10.1109/FOCS.2019.00030
ISSN: 1523-8288
EISSN: 2575-8454
Pages: 348 - 369
Type of Material: Conference Article
Journal/Proceeding Title: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.