On the complexity of radio communication
Noga Alon, Amotz Bar-Noy, Nathan Linial, David Peleg · 1989
A radio network is a synchronous network of processors that communicate by transmitting messages to their neighbors. A processor receives a message in a given step if and only if it is silent then and precisely one of its neighbors transmits. This stringent rule poses serious difficulties in performing even the simplest tasks. This is true even under the overly optimistic assumptions of centralized coordination and complete knowledge of the network topology. This paper is concerned with lower and upper bounds for the complexity of realizing various communication primitives for radio networks.