An Optimal Randomized Broadcasting Algorithm in Radio Networks with Collision Detection

2017/01/06 by Andriambolamalala, Ny Aina, Ravelomanana, Vlady
#Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)

paper · doi:10.48550/arxiv.1701.01587

Abstract

We present a randomized distributed algorithm that in radio networks with collision detection broadcasts a single message in O(D+log² n) time slots, with high probability. In view of the lower-bound Ω(D+log² n), our algorithm is optimal in the considered model answering the decades-old question of Alon, Bar-Noy, Linial and Peleg [JCSS 1991].

Related

• Randomized Broadcast in Radio Networks with Collision Detection
• Exactly Optimal Deterministic Radio Broadcasting with Collision Detection
• Radio Network Lower Bounds Made Easy
• Randomized Communication Without Network Knowledge
• Exploiting Spontaneous Transmissions for Broadcasting and Leader\n Election in Radio Networks