An O(n(1.5)) deterministic gossiping algorithm for radio networks

We consider the problem of distributed gossiping in radio networks of unknown topology. For radio networks of size n and diameter D, we present an adaptive deterministic gossiping algorithm of time O(NrootDn + n log(2) n) or O(n(1.5)). This algorithm is a tuned version of the fastest previously known gossiping algorithm due to Gasieniec and Lingas [1], and improves the time complexity by a poly-logarithmic factor.Computer Science, Software EngineeringMathematics, AppliedSCI(E)EI20ARTICLE193-963