A LOWER BOUND FOR RADIO BROADCAST

被引：231

作者：

ALON, N

BARNOY, A

LINIAL, N

PELEG, D

机构：

[1] BELL COMMUN RES INC,MORRISTOWN,NJ 07060

[2] STANFORD UNIV,STANFORD,CA 94305

[3] IBM CORP,ALMADEN RES CTR,SAN JOSE,CA 95120

[4] HEBREW UNIV JERUSALEM,IL-91904 JERUSALEM,ISRAEL

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 1991年 / 43卷 / 02期

关键词：

D O I：

10.1016/0022-0000(91)90015-W

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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. © 1991.

引用

页码：290 / 298

页数：9

共 10 条

[1]

BARYEHUDA R, COMMUNICATION

[2]

BARYEHUDA R, 1986, 4TH P ACM S PRINC DI, P98

[3]

Bollobas B., 1986, COMBINATORICA

[4] A MEASURE OF ASYMPTOTIC EFFICIENCY FOR TESTS OF A HYPOTHESIS BASED ON THE SUM OF OBSERVATIONS [J].

CHERNOFF, H .

ANNALS OF MATHEMATICAL STATISTICS, 1952, 23 (04) :493-507

[5]

CHLAMTAC I, 1985, IEEE T COMM, V33

[6]

GITMAN I, 1976, IEEE T COMMUN, P926

[7]

KAHN RE, 1978, P IEEE, V66

[8]

Kunzelman R. C., 1978, Proceedings of Spring Compcon 78, P157

[9]

SHACHAM N, 1982, P INFOCOM

[10]

[No title captured]

← 1 →