Re-Rooting-Based Fault-Tolerant Broadcasting in Dense Gaussian Networks

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 newsource 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 forwardthe 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 occurat internal forwarding positions.