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.|
|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|
|Pages:||348 - 369|
|Type of Material:||Conference Article|
|Journal/Proceeding Title:||Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.