An Ω(D log(N/D)) lower bound for broadcast in radio networks
作者： Eyal Kushilevitz , Yishay Mansour
关键词:
摘要: We show that for any randomized broadcast protocol radio networks, there exists a network in which the expected time to message is Q(ll log(N/11)), where D diameter of and N number nodes. This implies tight lower bound Q( log N) all S N1-e, s >0 constant.
acm.org
sci-hub.se 参考文章(10)
Chlamtac, Kutten, Tree-Based Broadcasting in Multihop Radio Networks IEEE Transactions on Computers. ,vol. 36, pp. 1209- 1223 ,(1987) , 10.1109/TC.1987.1676861
Noga Alon, Amotz Bar-Noy, Nathan Linial, David Peleg, Single round simulation on radio networks Journal of Algorithms. ,vol. 13, pp. 188- 210 ,(1992) , 10.1016/0196-6774(92)90015-5
Reuven Bar-Yehuda, Oded Goldreich, Alon Itai, Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection Distributed Computing. ,vol. 5, pp. 67- 71 ,(1991) , 10.1007/BF02259748
Dan E. Willard, Log-logarithmic selection resolution protocols in a multiple access channel SIAM Journal on Computing. ,vol. 15, pp. 468- 477 ,(1986) , 10.1137/0215032
R. Bar-Yehuda, A. Israeli, Multiple communication in multi-hop radio networks Proceedings of the eighth annual ACM Symposium on Principles of distributed computing - PODC '89. pp. 329- 338 ,(1989) , 10.1145/72981.73005
A perspective on multiaccess channels IEEE Transactions on Information Theory. ,vol. 31, pp. 124- 142 ,(1985) , 10.1109/TIT.1985.1057022
Noga Alon, Amotz Bar-Noy, Nathan Linial, David Peleg, A lower bound for radio broadcast Journal of Computer and System Sciences. ,vol. 43, pp. 290- 298 ,(1991) , 10.1016/0022-0000(91)90015-W
I. Chlamtac, The wave expansion approach to broadcasting in multihop radio networks IEEE Transactions on Communications. ,vol. 39, pp. 426- 433 ,(1991) , 10.1109/26.79285
Reuven Bar-Yehuda, Oded Goldreich, Alon Itai, On the time-complexity of broadcast in multi-hop radio networks: an exponential gap between determinism and randomization Journal of Computer and System Sciences. ,vol. 45, pp. 104- 126 ,(1992) , 10.1016/0022-0000(92)90042-H
I. Chlamtac, S. Kutten, On Broadcasting in Radio Networks--Problem Analysis and Protocol Design IEEE Transactions on Communications. ,vol. 33, pp. 1240- 1246 ,(1985) , 10.1109/TCOM.1985.1096245