Re-Rooting-Based Fault-Tolerant One-to-All Broadcasting in Dense Eisenstein–Jacobi Networks

Dense Eisenstein–Jacobi networks are degree-six algebraic interconnection topologies with regular structure, vertex symmetry, small diameter, and efficient communication algorithms. These properties make them suitable for parallel and on-chip communication systems in which collective operations such as one-to-all broadcasting are frequent. Existing optimal broadcasting algorithms for dense hexagonal/Eisenstein–Jacobi networks assume fault-free operation. However, a faulty internal forwarding node may interrupt message propagation and prevent complete delivery. This paper proposes a lightweight re-rooting-based fault-tolerant broadcasting method for dense Eisenstein–Jacobi networks. The main idea is to relocate the effective broadcast source to a new source node such that each faulty node is located at graph distance equal to the network diameter from the new source. Consequently, faulty nodes become leaf-level nodes in the broadcast process and are not required to forward the message. We present source-selection algorithms for one- and two-node failures and prove that for any pair of faulty nodes in a dense Eisenstein–Jacobi network there exists a common distance-diameter node that can serve as a valid re-rooted source. The source-selection procedure requires linear time in the network diameter. Equivalently, since N = 3t2+3t+1, the selection cost is O(√N) in the number of nodes. Since the standard one-to-all broadcast completes in onediameter time and the relocation phase is also bounded by one diameter, the proposed method completes in at most twice the network diameter. We also show that the two-fault guarantee does not generally extend to arbitrary three-fault configurations by giving an explicit counterexample. The proposed approach improves broadcast reliability without constructing redundant spanning trees, backup paths, or additional broadcast structures.