Report Number: CS-TR-88-1195
Institution: Stanford University, Department of Computer Science
Title: A Lower Bound for Radio Broadcast
Author: Bar-Noy, A.
Author: Linial, N.
Author: Peleg, D.
Date: February 1988
Abstract: A radio network is a synchronous network of processors that
communicate by transmitting messages to their neighbors,
where a processor receives a message in a given step if and
only if it is silent in this step and precisely one of its
neighbors transmits. In this paper we prove the existence of
a family of radius-2 networks on n vertices for which any
broadcast schedule requires at least Omega((log n/ log log
n)2) rounds of transmissions. This almost matches an upper
bound of O(log2 n) rounds for networks of radius 2 proved
earlier by Bar-Yehuda, Goldreich, and Itai.