AI summaryⓘ
The authors study a special type of network called dense Gaussian networks, which are good for spreading messages quickly. They address the problem that if some nodes fail in the network, the message might not reach everyone. Instead of building extra backup routes, they suggest moving the message starting point to a new node that keeps the failed nodes at the network's edge, so these faulty nodes don't need to pass the message on. Their method works well for one or two faulty nodes and finishes in roughly twice the normal time, but it doesn't always work with three or more faults. Their simulations show their approach reliably delivers messages when there are one or two faults, unlike the usual method which can fail.
dense Gaussian networksdegree-4 interconnection topologynetwork diameterbroadcastingfault tolerancedynamic source relocationspanning treegraph distanceparallel stepsnode failure
Authors
Bader Albader, Mohamed R. Al-Mulla, Galal Hassan
Abstract
Dense Gaussian networks provide degree-4 interconnection topologies with small diameter and regular structure, making them suitable for efficient one-to-all broadcasting. However, node failures can disrupt the broadcast process when faulty nodes occupy internal forwarding positions. This paper proposes a lightweight fault-tolerant broadcasting method based on dynamic source relocation, or re-rooting. Instead of constructing redundant spanning trees or backup routing structures, the proposed method selects a new source node so that the faulty nodes are located at graph distance \(k\), 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. For the single-fault case, the new source is selected directly from the graph-distance-\(k\) boundary of the faulty node. For the two-fault case, we prove that for any pair of faulty nodes in \(G(k+(k+1)i)\), there exists a node whose graph distance from both faulty nodes is exactly \(k\). The source-selection procedure requires \(O(k)\) time. Since the original one-to-all broadcast completes in \(k\) parallel steps and the relocation distance is at most \(k\), the proposed method completes in at most \(2k\) steps in the worst case. We also show that the two-fault guarantee does not generally extend to arbitrary three-fault configurations by giving a counterexample in \(G(3+4i)\). Simulation results confirm complete delivery to all non-faulty nodes under the tested one- and two-node failure scenarios, while the baseline broadcast may fail when faulty nodes occur at internal forwarding positions.