On the communication complexity of Bar-Yehuda, Goldreich and Itai's randomized broadcasting algorithm

The algorithm by Bar-Yehuda, Goldreich and Itai is one of the best known randomized broadcast algorithms for radio networks. Its probability of success and time complexity are nearly optimal. We propose a modification of this algorithm, which decreases the communication complexity, preserving other properties. Moreover, we show that the local communication complexity of the modified algorithm is deterministic.