Frank R. Libsch, S.C. Lien
IBM J. Res. Dev
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 Ω(D log(N/D)), where D is the diameter of the network and N is the number of nodes. This implies a tight lower bound of Ω(D log N) for any D ≤ N1-ε, where ε > 0 is any constant.
Frank R. Libsch, S.C. Lien
IBM J. Res. Dev
Charles H. Bennett, Aram W. Harrow, et al.
IEEE Trans. Inf. Theory
Alfonso P. Cardenas, Larry F. Bowman, et al.
ACM Annual Conference 1975
Maurice Hanan, Peter K. Wolff, et al.
DAC 1976