An Ω( D log( N/D )) lower bound for broadcast in radio networks
Eyal Kushilevitz, Yishay Mansour · 1993
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 Q(ll log(N/11)), where D is the diameter of the network and N is the number of nodes.This implies a tight lower bound of Q( D log N) for all D S N1-e, where s >0 is any constant.