Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks
Artur Czumaj, Peter Maxwell Davies · 2017
We study two fundamental communication primitives: broadcasting and leader election in the classical model of multi-hop radio networks with unknown topology and without collision detection mechanisms. It has been known for almost 20 years that in undirected networks with n nodes and diameter D, randomized broadcasting requires Ω(D log t n/D + log2n) rounds in expectation, assuming that uninformed nodes are not allowed to communicate (until they are informed). Only very recently, Haeupler and Wajc (PODC'2016) showed that this bound can be slightly improved for the model with spontaneous transmissions, providing an O(D(log n log log n)/(log D) + logO(1)n)-time broadcasting algorithm. In this paper, we give a new and faster algorithm that completes broadcasting in O(D(log n)/(log D) + logO(1)n) time, with high probability. This yields the first optimal O(D)-time broadcasting algorithm whenever D is polynomial in n.