MIT

We present a randomized distributed algorithm that in radio networks with collision detection broadcasts a single message in O(D + log6 n) rounds, with high probability1. 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 n D + log2 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 challeng-ing 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+log2 n) rounds, with high probability. If the topology is not known, but col-lision detection is available, then a k-message broadcast can be performed in O(D + k log n + log6 n) rounds, with high probability. The first bound is optimal and the second is optimal modulo the additive O(log6 n) term