Overview
A lightweight, re-rooting-based fault-tolerant broadcasting method has been proposed for dense Eisenstein–Jacobi networks. This method aims to improve broadcast reliability in the presence of internal forwarding node failures without requiring additional broadcast structures, redundant spanning trees, or backup paths. It tackles scenarios involving one and two faulty nodes by dynamically relocating the effective broadcast source.
Research Context
Dense Eisenstein–Jacobi networks are characterized as degree-six algebraic interconnection topologies. They exhibit regular structure, vertex symmetry, a small diameter, and are associated with efficient communication algorithms. These properties position them as suitable candidates for parallel and on-chip communication systems, especially where collective operations like one-to-all broadcasting are frequently employed. While existing optimal broadcasting algorithms for dense hexagonal/Eisenstein–Jacobi networks typically assume fault-free operation, the functional integrity of such systems can be compromised by faulty internal forwarding nodes. A single faulty node can disrupt message propagation, potentially preventing complete delivery of broadcast messages.
Approach
The proposed fault-tolerant broadcasting method is based on a re-rooting strategy. The core idea involves relocating the effective broadcast source to a new source node. This relocation ensures that each faulty node is positioned at a graph distance equivalent to the network diameter from the newly designated source. Consequently, these faulty nodes become leaf-level nodes within the broadcast process, thereby eliminating their requirement to forward the message. This mechanism allows the broadcast to circumvent the faulty nodes effectively.
Source-selection algorithms were developed for cases involving one- and two-node failures. The research proves the existence of a common distance-diameter node for any pair of faulty nodes in a dense Eisenstein–Jacobi network. This common node can serve as a valid re-rooted source. The procedure for selecting this re-rooted source requires linear time in relation to the network diameter. Given that $N=3t^2+3t+1$ (where $N$ is the number of nodes), the computational cost for source selection is expressed as $O(\sqrt{N})$ in terms of the number of nodes. The standard one-to-all broadcast completes in one diameter time, and the relocation phase of the re-rooting method also completes within one diameter. Therefore, the total completion time for the proposed method is at most twice the network diameter.
The study also includes an explicit counterexample to demonstrate that the two-fault guarantee offered by this method does not generally extend to arbitrary three-fault configurations.
Findings
- A re-rooting based fault-tolerant broadcasting method is proposed specific to dense Eisenstein–Jacobi networks.
- This method operates by relocating the effective broadcast source to ensure faulty nodes are at a distance equal to the network's diameter from the new source, rendering them leaf-level.
- Source-selection algorithms were developed for one- and two-node failure scenarios.
- For any pair of faulty nodes in a dense Eisenstein–Jacobi network, a common distance-diameter node exists that can function as a valid re-rooted source.
- The source-selection procedure exhibits a linear time complexity relative to the network diameter, equating to $O(\sqrt{N})$ in terms of the number of nodes ($N$).
- The proposed method completes within at most twice the network diameter, considering that both standard broadcast and relocation phases are bounded by one diameter.
- The two-fault guarantee of the method does not generally extend to arbitrary three-fault configurations, evidenced by a counterexample.
- The approach improves broadcast reliability without requiring redundant spanning trees, backup paths, or additional broadcast structures.
Why This Matters
This method offers a strategy for maintaining broadcast integrity in dense Eisenstein–Jacobi networks despite the presence of internal node failures, which can interrupt message propagation. By avoiding the need for redundant infrastructure, it provides a lightweight solution for enhancing system reliability in communication systems where broadcast operations are frequent.