A lower bound for radio broadcast
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 Ω (log 2 n) rounds of transmissions. This matches an upper bound
of O (log 2 n) rounds for networks of radius 2 proved earlier by Bar-Yehuda, Goldreich, and …
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 Ω (log 2 n) rounds of transmissions. This matches an upper bound
of O (log 2 n) rounds for networks of radius 2 proved earlier by Bar-Yehuda, Goldreich, and …
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 Ω(log2n) rounds of transmissions. This matches an upper bound of O(log2n) rounds for networks of radius 2 proved earlier by Bar-Yehuda, Goldreich, and Itai, in “Proceedings of the 4th ACM Symposium on Principles of Distributed Computing, 1986,” pp. 98–107.
Elsevier
