A randomized algorithm for gossiping in radio networks
Marek Chrobák, Leszek Antoni Gąsieniec, Wojciech Rytter · Networks · 2004
Abstract We present an O ( n log 4 n )‐time randomized algorithm for gossiping in radio networks with unknown topology. This is the first algorithm for gossiping in this model whose running time is only a polylogarithmic factor away from the optimum. The fastest previously known (deterministic) algorithm for this problem works in time O ( n 3/2 log 2 n ). © 2004 Wiley Periodicals, Inc.