An Ω(D log(N/D)) lower bound for broadcast in radio networks

被引：178

作者：

Kushilevitz, E

Mansour, Y

机构：

[1] Harvard Univ, Aiken Computat Lab, Cambridge, MA 02138 USA

[2] Tel Aviv Univ, Dept Comp Sci, IL-69978 Tel Aviv, Israel

[3] IBM Corp, TJ Watson Res Ctr, Armonk, NY 10504 USA

来源：

SIAM JOURNAL ON COMPUTING | 1998年 / 27卷 / 03期

关键词：

radio networks; broadcast; lower bounds;

D O I：

10.1137/S0097539794279109

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show that for any randomized broadcast protocol for radio networks, there exists a network in which the expected time to broadcast a message is Omega(Dlog(N/D)), where D is the diameter of the network and N is the number of nodes. This implies a tight lower bound of Omega(Dlog N) for any D less than or equal to N1-epsilon, where epsilon > 0 is any constant.

引用

页码：702 / 712

页数：11

共 14 条

[11]

GABER I, 1995, PROCEEDINGS OF THE SIXTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P577

[12] A PERSPECTIVE ON MULTIACCESS CHANNELS [J].

GALLAGER, RG .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1985, 31 (02) :124-142

[13]

Kushilevitz E., 1993, Proceedings of the Twelfth Annual ACM Symposium on Principles of Distributed Computing, P65, DOI 10.1145/164051.164059

[14] LOG-LOGARITHMIC SELECTION RESOLUTION PROTOCOLS IN A MULTIPLE ACCESS CHANNEL [J].

WILLARD, DE .

SIAM JOURNAL ON COMPUTING, 1986, 15 (02) :468-477

← 1 2 →