The most basic distributed radio network broadcasting primitive - called Decay - dates back to a PODC'87 result of Bar-Yehuda, Goldreich, and Itai. In any radio network with some informed source nodes, running Decay for O(d \log n + \log^2 n) rounds informs all nodes at most $d$ hops away from a source with high probability. Since 1987 this primitive has been the most important building block for implementing many other functionalities in radio networks. The only improvements to this decades-old algorithm are slight variations due to [Czumaj, Rytter; FOCS'03] and [Kowalski and Pelc, PODC'03] which achieve the same functionality in O(d \log \frac{n}{d} + \log^2 n) rounds. To obtain a speedup from this, $d$ and thus also the network diameter need to be near linear, i.e., larger than n^{1-\eps}.
Our new distributed primitive spreads messages for $d$ hops in O(d \frac{\log n \log \log n}{\log d} + \log^{O(1)} n) rounds. This improves over Decay for any super-polylogarithmic d = \log^{\omega(1)} n and achieves a near-optimal O(d \log \log n) running time for d = n^{\eps}. This also makes progress on an open question of Peleg.
Based on joint work with Bernhard Haeupler.
BIO:
David Wajc is a second-year PhD student in the computer science department at CMU, advised by Bernhard Haeupler. He is broadly interested in algorithmic aspects of theoretical computer science, and has worked on online algorithms, distributed algorithms, and AGT, among others.