Amplified Pruning and Path Selectors for Deterministic Radio Gossiping

Abstract

We study deterministic gossiping in unknown strongly connected directed radio networks with $n$ vertices, $m$ arcs, and distinct identifiers in $[N]$, where $N=n^{\mathcal O(1)}$. Messages are unrestricted and collision detection is unavailable. Our neighborhood-clearing procedure reuses an elected receiver to secure its entire closed in-neighborhood in $\mathcal O(n\log^2n\log\log n)$ rounds. Charging each distinct closed neighborhood once yields $\mathcal O(m\log^2n\log\log n)$ rounds under an explicit degree-concentration condition, for every polynomial identifier range. A complementary adaptive-pruning procedure combines quadratic contraction with completion sensitive to the number of unsecured sources. If $a\ge1$ sources remain at completion entry, permutation selectors reduce the balanced completion budget by a factor of $\log^{2/3}(a+1)$ relative to interleaved path selectors. A geometric execution attains $\widetilde{\mathcal O}(k^2+nτ+\min\{u^2,(nu)^{2/3}\})$ for a path cover of scale $k$, weight $τ$, and $u$ exceptions. For directed graphs with common in- and out-degree $Δ$, the portfolio achieves $\widetilde{\mathcal O}(\min\{n\sqrtΔ,n^2/Δ\})$. Every graph also admits $\widetilde{\mathcal O}(\min\{n^{4/3},N+(mn)^{3/5}\})$ rounds. Only $n,N$ are inputs; degrees, covers, and structural constants are used solely in the analysis. The unrestricted polynomial-identifier density extension remains open.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.