On the Time-Complexity of Broadcast in Radio Networks: An Exponential Gap Between Determinism and Randomization.

Reuven Bar-Yehuda, Oded Goldreich, Alon Itai

Browse the full PODC paper archive.