@Article{BarGol92, author = "R. Bar-Yehuda and O. Goldreich and A. Itai", title = "On the Time-Complexity of Broadcast in Multi-hop Radio Networks: An Exponential Gap between Determinism and Randomization", journal = "Journal of Computer and System Sciences", volume = "45", year = "1992", pages = "104--126", abstract = "The time-complexity of deterministic and randomized protocols for achieving broadcast (distributing a message from a source to all other nodes) in arbitrary multi-hop radio networks is investigated. In many such networks, communication takes place in synchronous time-slots. A processor receives a message at a certain time-slot if exactly one of its neighbors transmits at that time-slot. We assume no collision-detection mechanism; i.e., it is not always possible to distinguish the case where no neighbor transmits from the case where several neighbors transmit simultaneously. We present a randomized protocol that achieves broadcast in time which is optimal up to a logarithmic factor. In particular, with probability $1-\epsilon$, the protocol achieves broadcast within $O((D+\log n/\epsilon) \cdot \log n)$ time-slots, where $n$ is the number of processors in the network and $D$ its diameter. On the other hand, we prove a linear lower bound on the deterministic time-complexity of broadcast in this model. Namely, we show that diameter 3, and $n$ is known to all processors. These two results demonstrate an exponential gap in complexity between randomization and determinism.", }