On the time-complexity of broadcast in multi-hop radio networks: an exponential gap between determinism and randomization
作者： Reuven Bar-Yehuda , Oded Goldreich , Alon Itai
DOI: 10.1016/0022-0000(92)90042-H
关键词: Binary logarithm 、 Exponential function 、 Upper and lower bounds 、 Determinism 、 Time complexity 、 Hop (networking) 、 Atomic broadcast 、 Computer science 、 Computer network 、 Logarithm 、 Algorithm
摘要: The time-complexity of deterministic and randomized protocols for achieving broadcast (distributing a message from source to all other nodes) in arbitrary multi-hop radio networks is investigated. In many such networks, communication takes place synchronous time-slots. A processor receives at certain time-slot if exactly one its neighbors transmits that time-slot. We assume no collision-detection mechanism; i.e., it not always possible distinguish the case where neighbor several transmit simultaneously. present protocol achieves time which optimal up logarithmic factor. particular, with probability 1 --E, within O((D + log n/s) ‘log n) time-slots, n number processors network D diameter. On hand, we prove linear lower bound on this model. Namely, show any requires 8(n) even has diameter 3, known processors. These two results demonstrate an exponential gap complexity between randomization determinism.
elsevier.com
sci-hub.se 参考文章(17)
Richard E. Ladner, Albert G. Greenberg, Estimating the Multiplicities of Conflicts in Multiple Access Channels (Preliminary Report) foundations of computer science. pp. 383- 392 ,(1983)
Micha Hofri, A Feedback-less Distributed Broadcast Algorithm for Multihop Radio Networks with Time-Varying Structure. Computer Performance and Reliability. pp. 353- 368 ,(1987)
Joel Spencer, Probabilistic Methods in Combinatorics ,(1974)
Lawrence G. Roberts, ALOHA packet system with and without slots and capture ACM SIGCOMM Computer Communication Review. ,vol. 5, pp. 28- 42 ,(1975) , 10.1145/1024916.1024920
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
Albert G. Greenberg, Schmuel Winograd, A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels Journal of the ACM. ,vol. 32, pp. 589- 596 ,(1985) , 10.1145/3828.214125
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
S. Even, O. Goldreich, S. Moran, P. Tong, On the np‐completeness of certain network testing problems Networks. ,vol. 14, pp. 1- 24 ,(1984) , 10.1002/NET.3230140102
Reuven Bar-Yehuda, Oded Goldreich, Alon Itai, On the time-complexity of broadcast in radio networks: an exponential gap between determinism randomization Proceedings of the sixth annual ACM Symposium on Principles of distributed computing - PODC '87. pp. 98- 108 ,(1987) , 10.1145/41840.41849
A perspective on multiaccess channels IEEE Transactions on Information Theory. ,vol. 31, pp. 124- 142 ,(1985) , 10.1109/TIT.1985.1057022