A lower bound for radio broadcast

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

doi:10.1016/0022-0000(91)90015-W

A lower bound for radio broadcast

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

Research output: Contribution to journal › Article › peer-review

296 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 Ω(log² n) rounds of transmissions. This matches an upper bound of O(log² 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 language	English (US)
Pages (from-to)	290-298
Number of pages	9
Journal	Journal of Computer and System Sciences
Volume	43
Issue number	2
DOIs	https://doi.org/10.1016/0022-0000(91)90015-W
State	Published - Oct 1991
Externally published	Yes

All Science Journal Classification (ASJC) codes

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

Access to Document

10.1016/0022-0000(91)90015-W

Cite this

@article{03aa1e7f74c34bf3a5ef4d2e238816aa,

title = "A lower bound for radio broadcast",

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.",

author = "Noga Alon and Amotz Bar-Noy and Nathan Linial and David Pelegi",

note = "Funding Information: * Supported in part by an Allon Fellowship, by a Bat-Sheva de Rothschild Grant, and by a Bergmann Memorial Grant. + Supported in part by a Weizmann Fellowship and by Contract ONR NOOOl4-85-C-0731. Current address: IBM, T. J. Watson Research Center, Yorktown Heights, NY 10598. : Supported in part by Contract ONR NOOOl4-85-C-0731. Current address: The Weizmann Institute, Rehovot 76100, Israel.",

year = "1991",

month = oct,

doi = "10.1016/0022-0000(91)90015-W",

language = "English (US)",

volume = "43",

pages = "290--298",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - A lower bound for radio broadcast

AU - Alon, Noga

AU - Bar-Noy, Amotz

AU - Linial, Nathan

AU - Pelegi, David

N1 - Funding Information: * Supported in part by an Allon Fellowship, by a Bat-Sheva de Rothschild Grant, and by a Bergmann Memorial Grant. + Supported in part by a Weizmann Fellowship and by Contract ONR NOOOl4-85-C-0731. Current address: IBM, T. J. Watson Research Center, Yorktown Heights, NY 10598. : Supported in part by Contract ONR NOOOl4-85-C-0731. Current address: The Weizmann Institute, Rehovot 76100, Israel.

PY - 1991/10

Y1 - 1991/10

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0026238585&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026238585&partnerID=8YFLogxK

U2 - 10.1016/0022-0000(91)90015-W

DO - 10.1016/0022-0000(91)90015-W

M3 - Article

AN - SCOPUS:0026238585

SN - 0022-0000

VL - 43

SP - 290

EP - 298

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 2

ER -

A lower bound for radio broadcast

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this