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 $\Omega(T \log n)$ rounds.

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 $\mathcal{O}(\log n)$ overhead.

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 $\Omega(T \log n)$ rounds.

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 $\mathcal{O}(\log n)$ overhead.