A Gossiping Protocol for Sparse Ad-Hoc Radio Networks

We study the problem of gossiping (all-to-all information exchange) in ad-hoc radio networks. Such a network is represented by a strongly-connected directed graph with $n$ vertices, whose topology is initially unknown to the protocol. In 2004, Gasieniec, Radzik, and Xin gave a $\tilde{O}(n^{4\mathrm{/}3})$-time deterministic protocol for this problem, and closing the gap between their upper bound and the $\tilde{\mathrm{\Omega }}(n)$ lower bound on the time complexity of gossiping remains a central open problem. We develop a deterministic protocol for gossiping in ad-hoc radio networks that achieves running time $\tilde{O}((mn{)}^{3\mathrm{/}5})$ for directed graphs with at most $m$ edges. Our protocol improves on the $\tilde{O}(n^{4\mathrm{/}3})$ bound when $m=O(n^c)$, for $c<11\mathrm{/}9$. We also present a $\tilde{O}({\mathrm{\Delta }}^{1\mathrm{/}2}n)$-time gossiping protocol for $\mathrm{\Delta }$-regular graphs.