AN OMEGA(D LOG(N D)) LOWER-BOUND FOR BROADCAST IN RADIO NETWORKS/

Authors
KUSHILEVITZ E MANSOUR Y
Citation
E. Kushilevitz et Y. Mansour, AN OMEGA(D LOG(N D)) LOWER-BOUND FOR BROADCAST IN RADIO NETWORKS/, SIAM journal on computing, 27(3), 1998, pp. 702-712
Citations number
14
Categorie Soggetti
Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing → ACNP
ISSN journal
00975397
Volume
27
Issue
3
Year of publication
1998
Pages
702 - 712
Database
ISI
SICI code
0097-5397(1998)27:3<702:AOLDLF>2.0.ZU;2-M
Abstract
We show that for any randomized broadcast protocol for radio networks, there exists a network in which the expected time to broadcast a mess age 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 a ny constant.