A lower bound for radio broadcast

Noga Alon, Amotz Bar-Noy, Nathan Linial, David Pelegi

Research output: Contribution to journalArticle

270 Scopus citations

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 Ω(log2 n) rounds of transmissions. This matches an upper bound of O(log2 n) 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.

Original languageEnglish (US)
Pages (from-to)290-298
Number of pages9
JournalJournal of Computer and System Sciences
Volume43
Issue number2
DOIs
StatePublished - Oct 1991
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A lower bound for radio broadcast'. Together they form a unique fingerprint.

  • Cite this