Exploiting Spontaneous Transmissions for Broadcasting and Leader\n Election in Radio Networks

We study two fundamental communication primitives: broadcasting and leader\nelection in the classical model of multi-hop radio networks with unknown\ntopology and without collision detection mechanisms.\n It has been known for almost 20 years that in undirected networks with n\nnodes and diameter D, randomized broadcasting requires Omega(D log n/D + log^2\nn) rounds in expectation, assuming that uninformed nodes are not allowed to\ncommunicate (until they are informed). Only very recently, Haeupler and Wajc\n(PODC'2016) showed that this bound can be slightly improved for the model with\nspontaneous transmissions, providing an O(D log n loglog n / log D + log^O(1)\nn)-time broadcasting algorithm. In this paper, we give a new and faster\nalgorithm that completes broadcasting in O(D log n/log D + log^O(1) n) time,\nwith high probability. This yields the first optimal O(D)-time broadcasting\nalgorithm whenever D is polynomial in n.\n Furthermore, our approach can be applied to design a new leader election\nalgorithm that matches the performance of our broadcasting algorithm.\nPreviously, all fast randomized leader election algorithms have been using\nbroadcasting as their subroutine and their complexity have been asymptotically\nstrictly bigger than the complexity of broadcasting. In particular, the fastest\npreviously known randomized leader election algorithm of Ghaffari and Haeupler\n(SODA'2013) requires O(D log n/D min{loglog n, log n/D} + log^O(1) n)-time with\nhigh probability. Our new algorithm requires O(D log n / log D + log^O(1) n)\ntime with high probability, and it achieves the optimal O(D) time whenever D is\npolynomial in n.\n