Search papers, labs, and topics across Lattice.
This paper introduces a novel approach to fault-tolerant broadcasting in dense Gaussian networks by implementing a constant-time new-source selection method that leverages algebraic constructions. The authors replace the traditional boundary-search source-selection step with a quotient-lattice-aware technique, allowing for efficient counting of valid new sources without the need for network scanning. Key results demonstrate a significant speedup in source selection, achieving a 5.92脳 improvement over previous methods while maintaining accuracy across extensive testing scenarios.
Achieving constant-time new-source selection for fault-tolerant broadcasting could revolutionize efficiency in dense Gaussian networks.
Fault-tolerant broadcasting in dense Gaussian networks is recovered by re-rooting the broadcast at a new source at maximum graph distance from the faulty nodes. This paper extends the re-rooting framework by replacing its boundary-search source-selection step with a quotient-lattice-aware algebraic construction. The first contribution is a constant-time counting method for valid new sources, formulated as an intersection of two diameter-$k$ boundary sets in the Gaussian quotient. The exact count is obtained by a fixed union of side-pair intervals over nine quotient-lattice copies, giving a closed-form procedure without scanning the network or boundary. The second contribution is a shifted direct selector for two arbitrary faulty nodes. Given faulty nodes $A$ and $B$, the problem is translated to $C=\operatorname{mod}_{G_k}(B-A)$, and the selector finds $P$ satisfying $d(P,0)=d(P,C)=k$. For each of nine quotient-lattice shifts, sixteen signed linear systems are checked. Nonparallel systems are solved via Cramer's rule; parallel systems are handled by interval-endpoint selection. At most $9\times16=144$ shifted sign cases are evaluated, giving $O(1)$ selection under the word-RAM model. Validation reports zero count mismatches over $26{,}623$ tested nodes, $500{,}000$ valid outputs over $500{,}000$ sampled fault pairs, and $40{,}000$ successful re-rooted broadcast trials. The shifted selector achieves a $5.92\times$ speedup over boundary search at $k=200$, remaining stable as $k$ increases. These results make new-source selection algebraic, bounded, and independent of network size.
