A Gossiping Protocol for Sparse Ad-Hoc Radio Networks
This work advances the state of the art for deterministic gossiping in ad-hoc radio networks, a fundamental problem in distributed computing, by providing improved upper bounds for sparse and regular graphs.
The paper presents a deterministic gossiping protocol for ad-hoc radio networks with running time \( ilde O((mn)^{3/5})\), improving on the previous \( ilde O(n^{4/3})\) bound for sparse graphs with \(m = O(n^c)\) for \(c < 11/9\). It also gives a \( ilde O(\Delta^{1/2} n)\)-time protocol for \(\Delta\)-regular graphs.
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/3})\)-time deterministic protocol for this problem, and closing the gap between their upper bound and the \(\tildeΩ(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/5})\) for directed graphs with at most \(m\) edges. Our protocol improves on the \(\tilde O(n^{4/3})\) bound when \(m = O(n^c)\), for \(c < 11/9\). We also present a \(\tilde O(Δ^{1/2} n)\)-time gossiping protocol for \(Δ\)-regular graphs.