An Ω(D log(N/D)) Lower Bound for Broadcast in Radio Networks

Abstract

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.