On the computational power of radio channels

Mark Braverman, Gillat Kol, Rotem Oshman, Avishay Tal

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

Abstract

Radio networks can be a challenging platform for which to develop distributed algorithms, because the network nodes must contend for a shared channel. In some cases, though, the shared medium is an advantage rather than a disadvantage: for example, many radio network algorithms cleverly use the shared channel to approximate the degree of a node, or estimate the contention. In this paper we ask how far the inherent power of a shared radio channel goes, and whether it can efficiently compute “classicaly hard” functions such as Majority, Approximate Sum, and Parity. Using techniques from circuit complexity, we show that in many cases, the answer is “no”. We show that simple radio channels, such as the beeping model or the channel with collision-detection, can be approximated by a low-degree polynomial, which makes them subject to known lower bounds on functions such as Parity and Majority; we obtain round lower bounds of the form Ω(nδ) on these functions, for δ ∈ (0, 1). Next, we use the technique of random restrictions, used to prove AC0 lower bounds, to prove a tight lower bound of Ω(1/ϵ2) on computing a (1 ± ϵ)-approximation to the sum of the nodes’ inputs. Our techniques are general, and apply to many types of radio channels studied in the literature.

Original languageEnglish (US)
Title of host publication33rd International Symposium on Distributed Computing, DISC 2019
EditorsJukka Suomela
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771269
DOIs
StatePublished - Oct 2019
Event33rd International Symposium on Distributed Computing, DISC 2019 - Budapest, Hungary
Duration: Oct 14 2019Oct 18 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume146
ISSN (Print)1868-8969

Conference

Conference33rd International Symposium on Distributed Computing, DISC 2019
CountryHungary
CityBudapest
Period10/14/1910/18/19

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Approximate majority
  • Lower bounds
  • Radio channel

Fingerprint Dive into the research topics of 'On the computational power of radio channels'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M., Kol, G., Oshman, R., & Tal, A. (2019). On the computational power of radio channels. In J. Suomela (Ed.), 33rd International Symposium on Distributed Computing, DISC 2019 [8] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 146). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.DISC.2019.8