Re-rooting method makes Eisenstein-Jacobi networks fault-tolerant

Dense Eisenstein–Jacobi networks are degree-6 algebraic interconnection topologies with vertex symmetry, small diameter, and efficient communication, making them attractive for parallel and on-chip systems. One-to-all broadcasting is a common collective operation, but existing optimal algorithms assume fault-free operation. A single faulty internal node can halt message propagation and prevent full delivery. Bader Albader's new paper introduces a lightweight re-rooting strategy to handle one or two node failures without constructing redundant spanning trees, backup paths, or additional broadcast structures.

The core idea is to relocate the broadcast source to a new node such that each faulty node sits at exactly the network diameter from the new source—making them leaf-level nodes that do not forward the message. For any pair of faulty nodes, the author proves a common distance-diameter node always exists. Source selection runs in linear time relative to the diameter, which is O(√N) for N = 3t²+3t+1 nodes. The complete broadcast (relocation plus standard broadcast) finishes within two network diameter times. However, the two-fault guarantee does not extend to arbitrary three-fault configurations, as shown by a counterexample. The work significantly boosts broadcast reliability with minimal overhead.