We present a faster distributed broadcasting primitive for the classical radio network model. 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 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− . Our new distributed primitive spreads messages for d hops in O(d log n log log n log d + log O(1) n) rounds with high probability. This improves over Decay for any super-polylogarithmic d = log ω(1) n and achieves near-optimal O(d log log n) running time for d = n . This also makes progress on an open question of Peleg.
D. Note that Haeupler and Wajc REF conceived a radio broadcast primitive with complexity O(D log n log log n log D + log O(1) n) w.h.p.
A Faster Distributed Radio Broadcast Primitive: Extended Abstract
PODC '16
Computer Science