Search papers, labs, and topics across Lattice.
This paper introduces a closed-form, constant-time algorithm for selecting a valid new source in dense Eisenstein--Jacobi networks disrupted by two faulty nodes, addressing a significant challenge in fault-tolerant broadcasting. By reformulating the two-fault problem as a boundary-intersection problem, the authors efficiently determine valid new sources without exhaustive network scanning. Computational validation demonstrates that the proposed method consistently identifies valid sources, ensuring complete recovery of broadcasts to non-faulty nodes.
A constant-time algorithm for fault-tolerant broadcasting guarantees recovery from two node failures without the need for network-wide scans.
Fault-tolerant broadcasting in dense Eisenstein--Jacobi networks requires efficient recovery when faulty nodes disrupt the original broadcast structure. A re-rooting-based method guarantees that, for any two faulty nodes, a valid new source exists at maximum graph distance from both faults. However, identifying such a source without scanning the network or testing all boundary candidates remains an open practical problem. This paper presents a closed-form, constant-time algorithm for counting and selecting a valid new source in dense Eisenstein--Jacobi networks under two node faults. The two-fault problem is reduced to a boundary-intersection problem involving the origin and a difference node. The distance-$t$ boundary, where $t$ is the network diameter, is partitioned into six directed sides of the Eisenstein--Jacobi hexagon. Since the network is a quotient structure, intersection equations are solved modulo the defining lattice, requiring evaluation of seven quotient-lattice shifts across all $6\times 6$ side pairs, yielding at most $252$ algebraic systems. The first algorithm counts all valid new sources for faults at $0$ and $A$. The second algorithm selects one valid new source for arbitrary fault pairs by solving translated side-pair systems, verifying each candidate, and shifting back. Each system is either a non-parallel $2\times 2$ linear system with at most one candidate, or a parallel system whose feasible candidates form an integer interval. Both algorithms run in $O(1)$ time under the fixed-word arithmetic model. Computational validation over $500{,}000$ sampled fault pairs and $40{,}000$ re-rooting trials confirms correctness: the selector always returns a valid new source, and the recovered broadcast reaches all non-faulty nodes.
