Backend
Amplified Pruning and Path Selectors for Deterministic Radio Gossiping
arXiv cs.DC0 views
arXiv:2610.28930v1 Announce Type: cross 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 $\Delta$, our strategy achieves $\widetilde{\mathcal O}(\min\{n\sqrt\Delta,n^2/\Delta\})$, 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\tau+\min\{u^2,(nu)^{2/3}\})$ for an original path cover of scale $k$, weight $\tau$, 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.
Source:https://arxiv.org/abs/2610.28930PreviousSAT Sampling at Scale via GPU-based Boolean Constraint PropagationNextReorienting the Vector Axis: Restructuring FlashAttention for Long-Vector Processors
Related posts
Turn Today’s Messy Notes Into Tomorrow’s Checklist With AI
0dev.to AI
A 763B MoE at "2 Bits": Where the Bytes Really Go in the GSQ-RCO GGUFs, and Why 100% Recovery Sits Inside the Noise
0dev.to AI
How I ship fixes to open-source projects maintainers actually merge (with AI in the loop)
0dev.to AI
Prompt Injection Through Documents: How to Harden an LLM Extraction Pipeline
0dev.to AI
Keeping noindex, the sitemap and the image sitemap in agreement for programmatic pages
0dev.to AI
3 Things in AI You Should Know: Character.AI Files for Bankruptcy
0dev.to AI