Radio network coding requires logarithmic overhead

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019
PublisherIEEE Computer Society
Pages348-369
Number of pages22
ISBN (Electronic)9781728149523
DOIs
StatePublished - Nov 2019
Event60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019 - Baltimore, United States
Duration: Nov 9 2019Nov 12 2019

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2019-November
ISSN (Print)0272-5428

Conference

Conference60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019
CountryUnited States
CityBaltimore
Period11/9/1911/12/19

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Communication Complexity
  • Interactive Coding
  • Lower Bounds
  • Wireless Broadcast

Fingerprint Dive into the research topics of 'Radio network coding requires logarithmic overhead'. Together they form a unique fingerprint.

  • Cite this

    Efremenko, K., Kol, G., & Saxena, R. (2019). Radio network coding requires logarithmic overhead. In Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019 (pp. 348-369). [8948679] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2019-November). IEEE Computer Society. https://doi.org/10.1109/FOCS.2019.00030