@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.",
}