Deterministic methods speed up information spread in radio networks
Amplified Pruning and Path Selectors for Deterministic Radio Gossiping
Data Structures and AlgorithmsComputational ComplexityDistributed, Parallel, and Cluster Computing
Summary
Broadcasting information in wireless networks where messages can collide is challenging, especially when the network layout is unknown. The authors present a new step-by-step approach to ensure messages from all sources reach every node efficiently without random guessing. Their protocol carefully prunes communication paths and uses smart selections to reduce delays. This advances understanding for networks with certain structures and address ranges but leaves more complex cases open.
What this means in practice
- •For wireless network engineers: Develop algorithms for efficient message broadcast in strongly connected directed radio networks without collision detection.
- •For distributed systems developers: Implement deterministic protocols for data dissemination in directed networks with limited knowledge of network topology.
A theory result. No direct application yet.
Authors
Qin Xin
Abstract
We study deterministic gossiping in unknown strongly connected directed radio networks with $n$ vertices, $m$ arcs, and distinct identifiers in $\{1,\ldots,N\}$, where $N=n^{\mathcal O(1)}$. Messages are unrestricted; collision detection is unavailable. Our protocol combines amplified reception certificates, adaptive pruning, and permutation selectors. Each pruning iteration costs $\mathcal O(n\log^2n\log\log n)$ rounds. A two-step quadratic contraction limits each receiver and each class of identical closed in-neighborhoods to $\mathcal O(\log\log n)$ qualifying selections. Under an explicit degree-concentration condition, our protocol takes $\mathcal O(m\log^2n(\log\log n)^2)$ rounds. For directed regular graphs with common in- and out-degree $Δ$, our strategy achieves $\widetilde{\mathcal O}(\min\{n\sqrtΔ,n^2/Δ\})$, extending the identifier range of Wu and Chrobak and improving their high-degree bound. At completion entry, let $a\ge1$ count original sources not yet credited as globally disseminated. Permutation selectors reduce our balanced completion budget by a factor of $\log^{2/3}(a+1)$ relative to interleaved path selectors. Our geometric protocol attains $\widetilde{\mathcal O}(k^2+nτ+\min\{u^2,(nu)^{2/3}\})$ for an original path cover of scale $k$, weight $τ$, and $u$ exceptions. Every graph also admits $\widetilde{\mathcal O}(\min\{n^{4/3},N+(mn)^{3/5}\})$ rounds. Only $n,N$ are inputs. Within the stated graph classes and identifier ranges, these results answer the polynomial-identifier and average-degree questions of Wu and Chrobak. The unrestricted general-graph cases remain open.