  We present a randomized distributed algorithm that in radio networks with
collision detection broadcasts a single message in $O(D + \log^6 n)$ rounds,
with high probability. This time complexity is most interesting because of its
optimal additive dependence on the network diameter $D$. It improves over the
currently best known $O(D\log\frac{n}{D}\,+\,\log^2 n)$ algorithms, due to
Czumaj and Rytter [FOCS 2003], and Kowalski and Pelc [PODC 2003]. These
algorithms where designed for the model without collision detection and are
optimal in that model. However, as explicitly stated by Peleg in his 2007
survey on broadcast in radio networks, it had remained an open question whether
the bound can be improved with collision detection.
  We also study distributed algorithms for broadcasting $k$ messages from a
single source to all nodes. This problem is a natural and important
generalization of the single-message broadcast problem, but is in fact
considerably more challenging and less understood. We show the following
results: If the network topology is known to all nodes, then a $k$-message
broadcast can be performed in $O(D + k\log n + \log^2 n)$ rounds, with high
probability. If the topology is not known, but collision detection is
available, then a $k$-message broadcast can be performed in $O(D + k\log n +
\log^6 n)$ rounds, with high probability. The first bound is optimal and the
second is optimal modulo the additive $O(\log^6 n)$ term.
