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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/88/1195/CS-TR-88-1195.pdf