Skip to main content

On the Computational Power of Radio Channels

Author(s): Braverman, Mark; Kol, Gillat; Oshman, Rotem; Tal, Avishay

To refer to this page use:
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.
Publication Date: 2019
Citation: Braverman, Mark, Gillat Kol, Rotem Oshman, and Avishay Tal. "On the Computational Power of Radio Channels." 33rd International Symposium on Distributed Computing (DISC) 146 (2019): pp. 8:1-8:17. doi:10.4230/LIPIcs.DISC.2019.8
DOI: 10.4230/LIPIcs.DISC.2019.8
ISSN: 1868-8969
Pages: 8:1 - 8:17
Type of Material: Conference Article
Journal/Proceeding Title: 33rd International Symposium on Distributed Computing (DISC)
Version: Final published version. This is an open access article.

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