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