Re-Rooting-Based Fault-Tolerant One-to-All Broadcasting in Dense Eisenstein–Jacobi Networks Bader Albader Department of Computer Science, Kuwait University, Kuwait
arXiv:2606.18712v1 [cs.DC] 17 Jun 2026
Abstract 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 leaflevel 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 sourceselection procedure requires linear time in the √ network diameter. Equivalently, since 2 N = 3t + 3t + 1, the selection cost is O( N ) in the number of nodes. Since the standard one-to-all broadcast completes in one diameter 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.
Keywords: Broadcasting, Eisenstein–Jacobi networks, fault tolerance, hexagonal mesh networks, interconnection networks, re-rooting, source relocation.
1
Introduction
Interconnection networks play a central role in the design of parallel computers, networkon-chip architectures, multicore systems, distributed accelerators, and embedded communication fabrics. In such systems, processors or routers must exchange control information, 1
synchronization messages, configuration data, and application data efficiently. Among the most important collective communication primitives is one-to-all broadcasting, in which a source node disseminates a message to every other node in the network. Two-dimensional toroidal and mesh-based networks have been widely studied because of their simple layout and efficient local communication. However, alternative algebraic networks can provide better degree-diameter trade-offs and more symmetric communication patterns. Dense Gaussian networks and Eisenstein–Jacobi (EJ) networks are two such families. Gaussian networks provide degree-four topologies based on Gaussian integers, whereas EJ networks provide degree-six topologies based on Eisenstein–Jacobi integers. The degreesix EJ structure is closely related to wrap-around hexagonal meshes and admits efficient routing and broadcasting algorithms. Dense EJ networks are especially attractive because they combine algebraic regularity with a natural hexagonal geometry. The network is vertex-transitive, every node has six neighbors, and the nodes at each distance form a regular hexagonal boundary. For the dense hexagonal network with parameter n, the number of nodes is N = 3n2 − 3n + 1,
(1)
t = n − 1.
(2)
and the diameter is The standard one-to-all broadcast in this network completes in exactly t parallel steps by propagating the message through six directional sectors. Although the existing broadcast algorithm is optimal in the fault-free case, it is vulnerable to node failures. If a faulty node appears on an internal forwarding position of the broadcast tree, then all nodes depending on that forwarding node may fail to receive the message. This motivates a fault-tolerant approach that preserves the simplicity of the original broadcast while avoiding the need for redundant spanning trees or adaptive rerouting. This paper proposes a re-rooting-based fault-tolerant broadcasting method for dense EJ networks. Rather than modifying the broadcast tree or maintaining multiple backup structures, the method dynamically relocates the effective broadcast source. The new source node is selected so that each faulty node lies at graph distance t, the network diameter, from the new source. Since nodes at distance t are leaf-level nodes in the standard broadcast process, faulty nodes placed on this boundary are not required to forward packets. The contribution of this work is specific to the dense Eisenstein–Jacobi topology. Dense EJ networks have a degree-six neighborhood structure, a hexagonal graph-distance geometry, and a six-sector broadcast tree. The proposed method exploits these EJ-specific properties by using the graph-distance-t hexagonal boundary as a relocation target for faulty nodes. The main theoretical argument is based on a boundary-difference coverage property for the EJ network, namely that every node displacement can be represented as the difference of two distance-t boundary nodes. This allows the two-fault source-selection problem to be solved directly within the EJ geometry without modifying the underlying broadcast algorithm. The main contributions of this paper are as follows: • We propose a lightweight source-relocation method for fault-tolerant one-to-all broadcasting in dense Eisenstein–Jacobi networks. 2
• We develop source-selection algorithms for one-node and two-node failure scenarios. • We prove that for any two faulty nodes in a dense EJ network there exists a node whose graph distance from both faulty nodes is equal to the network diameter. • We show that this guarantee does not generally extend to arbitrary three-node failures by presenting an explicit counterexample. • We analyze the communication and computational complexity of the method and show that the total broadcast time is bounded by 2t, where t is the network diameter. • We position the proposed method relative to common fault-tolerant broadcasting approaches and discuss its limitations and practical implications. The remainder of this paper is organized as follows. Section 2 reviews related work. Section 3 introduces dense EJ networks and their distance structure. Section 4 reviews the standard one-to-all broadcasting algorithm. Section 5 presents the proposed re-rooting method. Section 6 proves the two-fault existence result and gives a three-fault counterexample. Section 7 analyzes the cost of the method. Section 8 presents the experimental evaluation. Section 9 concludes the paper.
2
Related Work
Interconnection-network topology plays an important role in the design of scalable parallel and distributed systems. Regular topologies such as meshes, tori, circulant graphs, Gaussian networks, and Eisenstein–Jacobi networks have been widely studied because their algebraic structure supports efficient routing, broadcasting, and collective communication. Among these topologies, Eisenstein–Jacobi networks are particularly attractive because they provide a degree-six hexagonal structure with small diameter, high symmetry, and efficient communication behavior. Hexagonal mesh networks were studied in early work on parallel architectures and reliable communication. Chen, Shin, and Kandlur investigated addressing, routing, and broadcasting in hexagonal mesh multiprocessors, while Kandlur and Shin developed reliable broadcast algorithms for HARTS, a hexagonal mesh multicomputer. These works showed that the hexagonal topology provides a natural six-directional communication structure suitable for efficient broadcast and routing. Later work showed that these hexagonal mesh networks can be interpreted algebraically as a special class of Eisenstein–Jacobi networks. In particular, the network Hn is generated by α = n + (n − 1)ω, has 3n2 − 3n + 1 nodes, and has diameter n − 1. This algebraic formulation provides a compact two-coordinate addressing scheme and simplifies shortest-path routing and collective communication. Eisenstein–Jacobi networks were further studied as algebraic interconnection networks based on the ring of EJ integers. In such networks, nodes are represented as congruence classes modulo an EJ integer, and adjacency is defined by the six unit directions ±1, ±ω, and ±ω 2 . This yields a regular degree-six topology. The dense family generated by α = n + (n − 1)ω is especially important because it achieves the maximum number of nodes for the given degree and diameter. 3
Collective communication algorithms on hexagonal and EJ networks have also been studied extensively. The basic one-to-all broadcast operation sends one message from a source node to all other nodes in the network. Fault tolerance is a central concern in interconnection networks because node or link failures can interrupt message propagation and reduce communication reliability. Classical fault-tolerant broadcasting methods often rely on redundant communication structures, such as multiple spanning trees, independent spanning trees, edge-independent spanning trees, backup paths, or adaptive rerouting. Fault-tolerant routing has also been widely investigated in Network-on-Chip systems and many-core architectures. These systems often require predictable latency, low routing complexity, and robustness against defective components. Existing methods include adaptive routing around faulty regions, priority-based quality-of-service routing, protection routing, machine-learning-assisted routing, and reinforcement-learning-based mapping. The method proposed in this paper follows a different approach. Instead of constructing redundant broadcast trees or continuously adapting the route during propagation, the proposed method changes the effective source of the broadcast. The new source N S is selected so that the faulty nodes lie on the graph-distance-t boundary of N S, where t = n − 1 is the diameter of the dense EJ network. Under the standard one-to-all broadcast tree, boundary nodes are leaf-level nodes and are not required to forward the message. Therefore, once the faulty nodes are placed on this boundary, the original broadcast algorithm can be reused without modification. This re-rooting approach is topology-specific. It exploits the vertex transitivity, sixdirectional symmetry, and boundary structure of dense EJ networks. Unlike redundant spanning-tree methods, the proposed method does not require constructing or storing multiple delivery structures. Unlike multiple-path routing, it does not duplicate the broadcast message along several paths. Unlike adaptive routing, it does not require runtime fault-status propagation or local route recomputation during the broadcast.
3
Dense Eisenstein–Jacobi Networks
This section introduces the dense EJ network model used throughout the paper.
3.1
Eisenstein–Jacobi Integers
Let
√ 1+i 3 . ω= 2 The Eisenstein–Jacobi integers are numbers of the form Z[ω] = {x + yω | x, y ∈ Z}.
(3)
(4)
The six natural directions in the triangular lattice are represented by the units ±1,
±ω,
±ω 2 .
(5)
A node can therefore be represented by the two integer coordinates (x, y) corresponding to the EJ number x + yω. 4
3.2
Dense Hexagonal/EJ Network
Let α = n + (n − 1)ω,
(6)
where n ≥ 2. The dense EJ network generated by α is the graph Hn = (V, E),
(7)
where the node set is the set of residue classes modulo α, V = Z[ω]/(α),
(8)
and two nodes u, v ∈ V are adjacent if v − u ≡ ±1, ±ω, ±ω 2
(mod α).
(9)
Thus, each node has degree six. The network has N = 3n2 − 3n + 1
(10)
t = n − 1.
(11)
nodes and diameter Equivalently, in terms of the diameter t, the number of nodes is N = 3t2 + 3t + 1.
(12)
The dense EJ network is vertex-transitive. Therefore, distance-based arguments can be carried out with respect to the origin without loss of generality and then translated to any other node.
3.3
Distance in the Hexagonal Lattice
For a node represented by x+yω, the graph distance from the origin in the infinite triangular lattice is ( |x + y|, xy ≥ 0, D(x, y) = (13) max{|x|, |y|}, xy < 0. Equivalently, D(x, y) = max{|x|, |y|, |x + y|}.
(14)
The nodes at distance j from any fixed node form a hexagonal boundary of size 6j, for 1 ≤ j ≤ t. In particular, the graph-distance-t boundary contains 6t nodes. We define the boundary of the origin by Bt = {z ∈ Hn | d(0, z) = t}.
(15)
By vertex transitivity, the boundary of a node u is Bt (u) = u + Bt . 5
(16)
3.4
Circulant Representation
The dense EJ network Hn is isomorphic to a degree-six circulant graph with N = 3n2 − 3n + 1
(17)
n − 1,
nodes and jumps n,
2n − 1.
(18)
t + 1,
2t + 1.
(19)
In terms of t = n − 1, the jumps are t,
This representation is useful for implementation and simulation, while the EJ representation is useful for geometric reasoning and proof construction.
3.5
Integer Labeling of EJ Nodes
Although the EJ coordinate representation x + yω is geometrically convenient, an integerlabel representation is useful for simulations, examples, and comparison with circulantnetwork descriptions. In the dense EJ network generated by α = n + (n − 1)ω,
(20)
N = 3n2 − 3n + 1.
(21)
t = n − 1.
(22)
the total number of nodes is The corresponding diameter is We define the integer-labeling function ϕ : Hn → ZN
(23)
by ϕ(x + yω) ≡ (n − 1)x + (2n − 1)y
(mod N ).
(24)
Thus, each EJ coordinate node x + yω is assigned a unique integer label modulo N . This labeling is consistent with the degree-six circulant representation of the dense EJ network. Indeed, ϕ(1) = n − 1, (25) and ϕ(ω) = 2n − 1.
(26)
ω 2 = ω − 1,
(27)
ϕ(ω 2 ) = ϕ(ω − 1) = (2n − 1) − (n − 1) = n.
(28)
Since we also have
6
Therefore, the six EJ adjacency directions ±1, ±ω, ±ω 2
(29)
correspond in the integer representation to the six circulant jumps ±(n − 1), ±(2n − 1), ±n
(30)
modulo N . Hence, the EJ network Hn is equivalently represented as the degree-six circulant graph CN (n − 1, n, 2n − 1). (31) The labeling function also preserves relative node differences. For any two EJ nodes U, V ∈ Hn , ϕ(U − V ) ≡ ϕ(U ) − ϕ(V ) (mod N ). (32) This property allows relative positions, wrap-around adjacency, and source-selection conditions to be expressed using modular integer arithmetic.
(a) EJ coordinate representation
(b) Integer-label representation
Figure 1: Dense Eisenstein–Jacobi network H4 generated by α = 4 + 3ω. The network has diameter t = 3 and N = 37 nodes. The left figure shows the EJ coordinate representation x + yω, while the right figure shows the corresponding integer-label representation obtained from ϕ(x + yω) ≡ 3x + 7y (mod 37). The blue curves represent wrap-around links induced by the modular EJ topology. For example, consider H4 . In this case, n = 4,
t = 3,
N = 3(4)2 − 3(4) + 1 = 37.
7
(33)
Using (24), the six neighbors of node 0 are labeled as follows: ϕ(1) ≡ 3 (mod 37), ϕ(ω) ≡ 7 (mod 37), 2 ϕ(ω ) = ϕ(−1 + ω) ≡ 4 (mod 37), ϕ(−1) ≡ 34 (mod 37), ϕ(−ω) ≡ 30 (mod 37), 2 ϕ(−ω ) = ϕ(1 − ω) ≡ 33 (mod 37).
(34) (35) (36) (37) (38) (39)
Thus, node 0 is adjacent to nodes 3, 4, 7, 30, 33, 34
(40)
in the integer-label representation, which are exactly the jumps ±3, ±4, ±7
(41)
modulo 37. Figure 1 illustrates the same H4 network using both EJ coordinates and integer labels. The left representation is useful for geometric reasoning, while the right representation is useful for simulations and circulant-graph implementation.
4
One-to-All Broadcasting in Dense EJ Networks
In this section, we review the standard one-to-all broadcasting procedure in dense Eisenstein– Jacobi networks. Let Hn be the dense EJ network generated by α = n + (n − 1)ω.
(42)
t = n − 1.
(43)
The network diameter is Since Hn is homogeneous and vertex-transitive, the one-to-all broadcast can be described without loss of generality from source node 0. The EJ network has six natural communication directions: 1, ω, ω 2 , −1, −ω, −ω 2 .
(44)
These correspond to the six geometric directions E, N E, N W, W, SW, SE,
(45)
respectively. Thus, the broadcast expands from the source through six sectors of the hexagonal topology. At the beginning of the broadcast, the source sends the message to its six neighbors. Each neighbor becomes the root of one sector of the broadcast tree. The broadcast then 8
proceeds outward in parallel through the six sectors. In each sector, the forwarding pattern follows the shortest-path structure of the hexagonal lattice. Nodes on the main sector axis forward the packet to two outward directions, while internal sector nodes forward the packet along one direction. This prevents duplicate packet reception and ensures that every node receives the message exactly once.
Figure 2: One-to-all broadcasting tree in the dense Eisenstein–Jacobi network H4 , where the source node is 0. The broadcast expands through the six EJ directions and covers the six sectors of the hexagonal topology. Boundary nodes at graph distance t = 3 are leaf-level nodes and do not forward the message further. Figure 2 illustrates the six-sector structure of the broadcast process. The important property for the proposed fault-tolerant method is that nodes at graph distance t from the source are leaf-level nodes. Such nodes may receive the message, but they are not required to forward it to any other node. Therefore, a faulty node located at distance t from the source does not disrupt the broadcast process. A simple packet-header structure can be used to implement the broadcast. The packet contains a broadcast-control field, a distance field, and a six-bit direction field. The distance field is initialized to the network diameter t. The six-bit direction field, denoted by DIR, indicates which of the six output ports are enabled for forwarding. In this paper, the bits of DIR are ordered as (E, SE, SW, W, N W, N E). (46) Thus, the one-direction masks are interpreted as 100000 = E,
010000 = SE,
001000 = SW,
(47)
000100 = W,
000010 = N W,
000001 = N E.
(48)
9
At each hop, the distance field is decremented. When the distance field reaches zero, the packet is consumed but not forwarded. Thus, the broadcast terminates exactly at the graphdistance-t boundary. The forwarding rule is summarized in Algorithm 1, and the corresponding direction-mask actions are listed in Table 1. Algorithm 1 One-to-all broadcast forwarding in Hn Require: Distance field dist, direction field DIR 1: The six-bit direction field is ordered as (E, SE, SW, W, N W, N E). 2: if dist = t then 3: Send to E, N E, N W, W, SW, SE using initial sector masks 4: 110000, 100001, 000011, 000110, 001100, 011000, respectively 5: else if dist = 0 then 6: Consume packet and stop forwarding 7: else 8: Consume packet and set dist ← dist − 1 9: Apply the sector forwarding rules in Table 1 10: end if
Table 1: Direction-mask forwarding rules used by Algorithm 1. Incoming mask Forwarding action 110000 E : 110000, SE : 010000 100001 N E : 100001, E : 100000 000011 N W : 000011, N E : 000001 000110 W : 000110, N W : 000010 001100 SW : 001100, W : 000100 011000 SE : 011000, SW : 001000 100000 E : 100000 010000 SE : 010000 001000 SW : 001000 000100 W : 000100 000010 N W : 000010 000001 N E : 000001 Table 1 lists the forwarding actions used by Algorithm 1. In each two-direction forwarding case, the first outgoing copy preserves the current sector-axis mask, while the second outgoing copy uses a one-direction mask.
10
(A)
(B)
Figure 3: Fault classification in the dense Eisenstein–Jacobi network H4 with diameter t = 3, rooted at the source node (0, 0). (A) A faulty node located on the graph-distance-t boundary. (B) A faulty node located at graph distance less than t. The algorithm is independent of the identity of the source node. If the source is S instead of 0, the same forwarding structure is obtained by translating all nodes by S. The broadcast completes in exactly t = n − 1 parallel steps. At step j, for 1 ≤ j ≤ t, the broadcast reaches the nodes at graph distance j from the source. Since the dense EJ network has 6j nodes at graph distance j, the number of newly reached nodes at each step grows linearly with j. At the final step, the broadcast reaches the boundary nodes at distance t. These boundary nodes are leaves of the broadcast tree. The total number of non-source nodes is N − 1 = 3n2 − 3n = 3t2 + 3t.
(49)
6j = 3t(t + 1) = 3t2 + 3t = N − 1.
(50)
Also, t X j=1
Therefore, the broadcast reaches every non-source node exactly once. Since no duplicate messages are generated, the broadcast uses exactly N − 1 tree edges. This is optimal for one-to-all broadcasting because any broadcast tree spanning all N nodes must use at least N − 1 edges. The communication time of the fault-free one-to-all broadcast is therefore Bbaseline (t) = t.
(51)
Bbaseline (n) = n − 1.
(52)
Equivalently, in terms of n, This baseline broadcast algorithm is efficient but not fault tolerant. If a faulty node occurs on the distance-t boundary of the source, the broadcast remains correct because the 11
faulty node is a leaf-level node and does not need to forward the message. However, if a faulty node occurs at graph distance less than t, it may be an internal forwarding node. In that case, packets that should pass through that node may not reach all downstream nodes in the corresponding sector. The proposed method addresses this problem by relocating the effective source before starting the broadcast so that the faulty nodes become distance-t boundary nodes with respect to the new source.
5
Proposed Re-Rooting Method
We now present the proposed fault-tolerant broadcasting method. The method assumes a static node-failure model: the faulty nodes are known before the broadcast begins and do not change during propagation. The original source node is assumed to be operational.
5.1
Fault Classification
Let S be the original broadcast source in the dense EJ network Hn , and let t=n−1
(53)
be the network diameter. A faulty node F can be classified according to its graph distance from the source S. The first case occurs when d(S, F ) = t. (54) In this case, the faulty node lies on the graph-distance-t boundary of the source. Under the standard EJ one-to-all broadcast, boundary nodes are leaf-level nodes. They may receive the broadcast message, but they are not required to forward it to any other node. Therefore, a faulty node at distance t from the source does not interrupt the propagation of the broadcast tree. The second case occurs when d(S, F ) < t. (55) In this case, the faulty node may lie at an internal forwarding position of the broadcast tree. If such a node fails to forward the message, then all downstream nodes that depend on that forwarding step may not receive the broadcast. Therefore, faults at distance less than t can disrupt the correctness of the original one-to-all broadcast. For multiple faulty nodes, the same classification applies to each faulty node. If all faulty nodes are located at distance t from the source, then the original broadcast can proceed without re-rooting. However, if at least one faulty node is located at distance less than t, then the broadcast source must be relocated to a new source node N S. The goal of re-rooting is to choose N S so that every faulty node becomes a graph-distance-t boundary node with respect to N S. Thus, for a faulty set F = {F1 , F2 , . . . , Fm }, the desired re-rooted source satisfies d(N S, Fi ) = t,
12
1 ≤ i ≤ m.
(56)
When this condition holds, all faulty nodes are leaf-level nodes in the broadcast tree rooted at N S, and none of them is required to forward the broadcast message. Figure 3 illustrates the two fault categories. The proposed re-rooting method addresses the disruptive case by selecting a new source N S that moves the faulty nodes to the graphdistance-t boundary.
5.2
Main Idea
Let S be the original source and let F be the set of faulty nodes. If every faulty node is already at graph distance t from S, then the standard broadcast can proceed from S because all faulty nodes are leaf-level nodes. Otherwise, the method selects a new source node N S such that d(N S, f ) = t, for every f ∈ F. (57) The message is then routed from S to N S, and the standard one-to-all broadcast is initiated from N S. Since every faulty node is located on the graph-distance-t boundary with respect to N S, faulty nodes are reached only at the final broadcast step and are not required to forward the message. Thus, the original broadcast algorithm is preserved.
5.3
Single-Fault Case
For a single faulty node F1 , a valid new source can be chosen from the boundary Bt (F1 ) = F1 + Bt .
(58)
Any node in this set is at graph distance t from F1 . If the selected node is faulty or unsuitable for implementation reasons, another boundary node can be chosen. Algorithm 2 OneFailureFindingNS Require: Faulty node F1 , network parameter n, diameter t = n − 1 Ensure: New source node N S 1: Generate the graph-distance-t boundary set Bt 2: for each boundary node U ∈ Bt do 3: N S ← F1 + U (mod α) 4: if N S is operational then 5: return N S 6: end if 7: end for Algorithm 2 gives a simple source-selection method that scans the distance-t boundary Bt , which contains exactly 6t nodes. Therefore, the worst-case running time is T1 (t) = O(6t) = O(t).
13
(59)
5.4
Two-Fault Case
For two faulty nodes F1 and F2 , the goal is to find a node N S satisfying d(F1 , N S) = d(F2 , N S) = t.
(60)
N S ∈ Bt (F1 ) ∩ Bt (F2 ).
(61)
Equivalently, The existence of such a node for every pair of faulty nodes is proved in Section 6. Algorithm 3 TwoFailureFindingNS Require: Faulty nodes F1 , F2 , network parameter n, diameter t = n − 1 Ensure: New source node N S 1: Generate the graph-distance-t boundary set Bt 2: A ← F2 − F1 (mod α) 3: for each boundary node U ∈ Bt do 4: V ← U − A (mod α) 5: if V ∈ Bt then 6: N S ← F1 + U (mod α) 7: if N S is operational then 8: return N S 9: end if 10: end if 11: end for Algorithm 3 uses translation symmetry. First, it reduces the problem to finding a boundary node for the relative difference A = F2 − F1 . (62) Then it translates the solution back to the original position. Since |Bt | = 6t, and membership in Bt can be checked in constant time using the distance formula or a precomputed boundary set, the worst-case running time is T2 (t) = O(6t) = O(t).
5.5
(63)
Worked Example
We now give a concrete example to illustrate the two-fault re-rooting idea. Consider the dense EJ network H4 , generated by α = 4 + 3ω.
(64)
In this case, n = 4,
N = 3n2 − 3n + 1 = 37.
t = n − 1 = 3,
(65)
Assume that the two faulty nodes are F1 = (0, 0) 14
(66)
and F2 = (1, 0).
(67)
Using the integer-labeling function ϕ(x + yω) ≡ 3x + 7y
(mod 37),
(68)
these nodes correspond to ϕ(F1 ) = 0
(69)
ϕ(F2 ) = 3.
(70)
and The goal is to find a new source node N S satisfying d(N S, F1 ) = d(N S, F2 ) = 3.
(71)
N S = (−3, 0).
(72)
d(F1 , N S) = D(−3, 0) = max{| − 3|, |0|, | − 3 + 0|} = 3.
(73) (74) (75)
One valid choice is For the first faulty node,
For the second faulty node, the displacement from F2 to N S is N S − F2 = (−3, 0) − (1, 0) = (−4, 0).
(76)
Modulo α = 4 + 3ω, this displacement is equivalent to (−4, 0) ≡ (0, −3)
(mod 4 + 3ω).
(77)
Therefore, d(F2 , N S) = D(0, −3) = max{|0|, | − 3|, |0 − 3|} = 3.
(78) (79) (80)
d(F1 , N S) = d(F2 , N S) = 3.
(81)
Hence, In integer labels, the selected new source is ϕ(−3, 0) ≡ 3(−3) + 7(0) ≡ −9 ≡ 28
(mod 37).
(82)
Thus, the same example can be written as F1 = 0,
F2 = 3, 15
N S = 28.
(83)
The node 28 is at graph distance 3 from both faulty nodes 0 and 3.
Figure 4: Worked example of two-fault re-rooting in H4 . The faulty nodes are F1 = 0 and F2 = 3, and one valid new source is N S = 28. The path from F2 to N S uses the wrap-around relation (−4, 0) ≡ (0, −3) (mod 4 + 3ω), showing that d(F2 , N S) = 3. Thus, both faulty nodes are at graph distance t = 3 from the new source. After N S is selected, the message is first routed from the original source S to N S. Then, the standard one-to-all EJ broadcast is executed from N S. Since both faulty nodes are now located on the graph-distance-3 boundary of N S, they are leaf-level nodes and do not participate in forwarding.
6
Existence Proof and Theoretical Boundary
This section proves the main theoretical guarantee for two faulty nodes and then shows why the guarantee cannot be extended to all three-fault configurations.
6.1
Boundary-Difference Coverage
The key step in the two-fault re-rooting argument is to show that every possible relative displacement between two faulty nodes can be represented as the difference of two boundary nodes. This property allows us to translate a two-fault problem into a common-boundary problem. Let Bt = {z ∈ Hn | d(0, z) = t} (84)
16
denote the graph-distance-t boundary around node 0, where t=n−1
(85)
is the diameter of Hn . Since Hn is vertex-transitive, the graph-distance-t boundary around any node is obtained by translating Bt . For an EJ coordinate z = x+yω, the distance from the origin in the hexagonal coordinate representation is D(x, y) = max{|x|, |y|, |x + y|}. (86) Thus, the closed hexagonal ball of radius t is Ht = {x + yω | D(x, y) ≤ t}.
(87)
Bt = {x + yω | D(x, y) = t}.
(88)
The boundary of this ball is
Lemma 1 (Boundary-Difference Coverage). For the dense Eisenstein–Jacobi network Hn generated by α = n + (n − 1)ω, (89) with diameter t = n − 1, the graph-distance-t boundary satisfies Bt − Bt = Hn .
(90)
That is, for every node A ∈ Hn , there exist two boundary nodes U, V ∈ Bt such that A = U − V.
(91)
Proof. Let A ∈ Hn be arbitrary. Because Hn is the dense EJ network generated by α = n + (n − 1)ω, every node has a representative inside the closed hexagonal ball Ht . This representative can be chosen by reducing the EJ coordinate modulo α to the canonical diameter-t region; equivalently, since Hn has diameter t, each residue class contains a coordinate representative at graph distance at most t from the origin. Therefore, we may write A = x + yω (92) with D(x, y) ≤ t.
(93)
It is sufficient to prove that every point in Ht can be written as the difference of two points on the boundary Bt . The hexagonal ball Ht is divided into six sectors corresponding to the six EJ directions 1, ω, ω 2 , −1, −ω, −ω 2 .
(94)
We first prove the construction explicitly for the first sector, and then extend it to the remaining five sectors by rotational symmetry. 17
Assume first that A lies in the first sector. Then A = r + sω,
(95)
where r ≥ 0,
s ≥ 0,
r + s ≤ t.
(96)
Define two nodes U = (r − t) + tω
(97)
V = −t + (t − s)ω.
(98)
U − V = (r − t) + tω − −t + (t − s)ω = (r − t + t) + t − (t − s) ω = r + sω = A.
(99)
and Then
(100) (101) (102)
Thus, A is the difference of U and V . It remains to show that both U and V are boundary nodes. For U , the coordinate pair is (r − t, t). (103) Using (86), we obtain D(U ) = max{|r − t|, |t|, |(r − t) + t|} = max{t − r, t, r} = t,
(104) (105) (106)
U ∈ Bt .
(107)
(−t, t − s).
(108)
D(V ) = max{| − t|, |t − s|, | − t + (t − s)|} = max{t, t − s, s} = t,
(109) (110) (111)
because 0 ≤ r ≤ t. Hence, For V , the coordinate pair is Again using (86), we obtain
because 0 ≤ s ≤ t. Hence, V ∈ Bt .
(112)
Therefore, every node A in the first sector can be expressed as A=U −V 18
(113)
for some U, V ∈ Bt . Now consider a node A in any other sector. The remaining sectors are obtained from the first sector by multiplication by one of the six EJ units 1, ω, ω 2 , −1, −ω, −ω 2 .
(114)
Multiplication by any EJ unit is a graph automorphism of Hn . It preserves adjacency, graph distance, and the distance-t boundary. Therefore, if a rotated version of A, denoted by A′ , lies in the first sector and has a decomposition A′ = U ′ − V ′
(115)
U ′ , V ′ ∈ Bt ,
(116)
A=U −V
(117)
U, V ∈ Bt .
(118)
with then rotating back gives with Thus, every node of Hn can be represented as the difference of two graph-distance-t boundary nodes. Hence, Bt − Bt = Hn . (119)
6.2
Two-Fault Re-Rooting Theorem
By Lemma 1, every relative displacement in Hn can be written as the difference of two boundary nodes. Theorem 1 (Existence of a Common Distance-t New Source). Let F1 and F2 be any two faulty nodes in the dense EJ network Hn with diameter t = n − 1. Then there exists a node N S ∈ Hn such that d(F1 , N S) = t (120) and d(F2 , N S) = t.
(121)
Proof. Let A = F2 − F1
(mod α).
(122)
A=U −V
(mod α).
(123)
N S = F1 + U
(mod α).
(124)
By Lemma 1, there exist U, V ∈ Bt such that
Choose
19
Since U ∈ Bt , translation invariance gives d(F1 , N S) = d(0, U ) = t.
(125)
N S − F2 = F1 + U − F2 (mod α) = U − (F2 − F1 ) (mod α) = U − A (mod α) = V (mod α).
(126) (127) (128) (129)
d(F2 , N S) = d(0, V ) = t.
(130)
Also,
Since V ∈ Bt , we obtain Therefore, N S is a common graph-distance-t node for F1 and F2 . Corollary 1. For any one-node or two-node static fault configuration in Hn , the proposed re-rooting method can select a new source node such that all faulty nodes are leaf-level nodes in the subsequent one-to-all broadcast.
6.3
Three-Fault Limitation
The previous theorem gives a deterministic guarantee for any pair of faulty nodes. However, the same guarantee does not hold for arbitrary triples of faulty nodes. Proposition 1 (Three-Fault Counterexample). The two-fault re-rooting guarantee does not generally extend to arbitrary three-node fault configurations in dense EJ networks. Proof. Consider H4 , for which t=n−1=3
(131)
N = 3n2 − 3n + 1 = 37.
(132)
and Using the circulant representation with jumps 3,
4,
7,
(133)
the graph-distance-3 boundary of node 0 is B3 (0) = {2, 5, 9, 12, 13, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 28, 32, 35}.
(134)
Now choose three faulty nodes with integer labels F1 = 0,
F2 = 5,
20
F3 = 14.
(135)
By vertex transitivity, the graph-distance-3 boundary of node F is obtained by shifting B3 (0) by F modulo 37. Thus, B3 (F1 ) = {2, 5, 9, 12, 13, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 28, 32, 35},
(136)
B3 (F2 ) = {0, 3, 7, 10, 14, 17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 29, 30, 33},
(137)
B3 (F3 ) = {1, 2, 5, 9, 12, 16, 19, 23, 26, 27, 29, 30, 31, 32, 33, 34, 35, 36}.
(138)
and
A valid re-rooted source for all three faulty nodes would need to lie in B3 (F1 ) ∩ B3 (F2 ) ∩ B3 (F3 ).
(139)
However, direct intersection gives B3 (F1 ) ∩ B3 (F2 ) ∩ B3 (F3 ) = ∅.
(140)
Therefore, no node N S satisfies d(N S, F1 ) = d(N S, F2 ) = d(N S, F3 ) = 3.
(141)
This proves that the deterministic guarantee for two faulty nodes cannot be extended to arbitrary triples.
7
Complexity and Communication Cost
The proposed method consists of two phases: source selection and message dissemination.
7.1
Source-Selection Cost
For one faulty node, the algorithm scans at most 6t boundary candidates. Therefore, T1 (t) = O(t).
(142)
For two faulty nodes, the algorithm also scans at most 6t candidates and tests whether the translated candidate is on the boundary. Using the distance formula in (14), each membership test is constant time. Hence, T2 (t) = O(t).
(143)
Since N = 3t2 + 3t + 1, the source-selection √ cost is linear in the diameter and sublinear in the network size; equivalently, O(t) = O( N ). 21
7.2
Communication Cost
The standard one-to-all broadcast in Hn completes in Bbaseline (t) = t
(144)
parallel communication steps. The proposed method first routes the message from the original source S to the selected new source N S. Since the network diameter is t, the relocation distance satisfies R(t) = d(S, N S) ≤ t.
(145)
After the message reaches N S, the standard one-to-all broadcast is executed from N S in t steps. Therefore, the total worst-case communication time is Btotal (t) = R(t) + Bbaseline (t) ≤t+t = 2t.
(146) (147) (148)
Thus, the proposed method provides deterministic one- and two-node fault tolerance while increasing the worst-case broadcast time by at most one additional diameter.
7.3
Why the Relocation Path Is Safe
If a faulty node F is placed at distance t from N S, then it cannot be an internal node on a shortest path from the original source S to N S. If it were an internal node on such a path, then the remaining distance from F to N S along that path would be strictly less than t. This would contradict the construction condition d(F, N S) = t. Therefore, the one-to-one relocation phase is not blocked by the faulty nodes selected by the re-rooting condition.
8
Experimental Evaluation
In this section, we evaluate the proposed re-rooting-based fault-tolerant broadcasting method in dense Eisenstein–Jacobi networks. The goal of the evaluation is to compare the reliability and overhead of the proposed method with the original one-to-all broadcasting algorithm under static node-failure scenarios.
8.1
Experimental Setup
We conducted simulations on dense Eisenstein–Jacobi networks generated by α = n + (n − 1)ω.
(149)
t = 10, 25, 50, 100, 200,
(150)
The tested diameter values were
22
corresponding to n = 11, 26, 51, 101, 201.
(151)
Thus, the tested network sizes were N = 331, 1951, 7651, 30301, 120601.
(152)
For each network size, two node-failure scenarios were considered: • Single-node failure: one faulty node is present in the network. • Two-node failures: two distinct faulty nodes are present in the network. For each value of t and each fault scenario, four fault-placement modes were tested: • Random: faulty nodes are selected uniformly at random. • Near-source: faulty nodes are selected close to the original source. • Critical-position: faulty nodes are selected from positions likely to interrupt the broadcast forwarding process. • Close-pair: faulty nodes are selected from locally clustered regions. For each exact configuration of diameter, fault count, and fault-placement mode, 1000 independent trials were performed. The full experiment contains 5 × 2 × 4 × 1000 = 40000
(153)
trials.
8.2
Simulation Procedure
For each tested value of n, the simulator first constructs the dense EJ network Hn = Z[ω]/(n + (n − 1)ω).
(154)
Each node is represented by an EJ coordinate x + yω, and adjacency is defined using the six EJ directions ±1, ±ω, ±ω 2 . (155) For each trial, the faulty node set is generated according to the selected fault-placement mode. The original source node is fixed as node 0, and the same faulty set is used to evaluate both the baseline and proposed methods. A trial is considered successful if every non-faulty node receives the broadcast message. Formally, if F is the set of faulty nodes and R is the set of nodes reached by the broadcast, then the trial is successful when Hn \ F ⊆ R. (156)
23
8.3
Boundary-Difference Validation
Before evaluating broadcast performance, we validate the main theoretical condition used by the proposed method. For each tested network size, the simulator constructs the distance-t boundary and verifies that Bt − Bt = Hn . Table 2: Validation of the boundary-difference property in dense EJ networks. n 11 26 51 101 201
t 10 25 50 100 200
N 331 1951 7651 30301 120601
|Bt | |Bt − Bt | 60 331 150 1951 300 7651 600 30301 1200 120601
The results in Table 2 support the theoretical result that the distance-t boundary difference set covers the entire dense EJ network.
8.4
Broadcast Success and Reachability
Table 3 summarizes the broadcast success rate and average reachability of the baseline and proposed methods across all tested fault-placement modes. Table 3: Broadcast performance under one- and two-node failures across all fault-placement modes. n 11 26 51 101 201 11 26 51 101 201
t Faults N 10 1 331 25 1 1951 50 1 7651 100 1 30301 200 1 120601 10 2 331 25 2 1951 50 2 7651 100 2 30301 200 2 120601
Trials Baseline (%) 4000 9.125 4000 3.875 4000 2.300 4000 1.025 4000 0.500 4000 3.925 4000 0.975 4000 0.650 4000 0.300 4000 0.225
Proposed (%) 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0
Avg. Base Reach 318.952 1920.667 7589.553 30188.283 120378.393 307.554 1891.973 7528.753 30075.920 120198.111
Avg. Prop. Reach 330 1950 7650 30300 120600 329 1949 7649 30299 120599
The proposed method achieves complete delivery in all one- and two-node failure configurations because the selected new source places every faulty node on the distance-t boundary.
24
Figure 5: Broadcast success rate versus network diameter t. The proposed re-rooting method achieves complete delivery in all tested one- and two-node failure scenarios, while the baseline broadcast success rate decreases as the network size increases. Figure 5 shows the broadcast success rate as the network size increases.
8.5
Reachability Variation
Table 4 reports the standard deviation of the number of reached nodes across trials. Table 4: Reachability variation under fault-placement experiments. n 11 26 51 101 201 11 26 51 101 201
t Faults Base SD Prop. SD 10 1 15.777 0.000 25 1 64.026 0.000 50 1 183.218 0.000 100 1 482.064 0.000 200 1 1386.801 0.000 10 2 24.487 0.000 25 2 93.407 0.000 50 2 270.004 0.000 100 2 694.483 0.000 200 2 1806.523 0.000
The proposed method has zero reachability variation when it reaches exactly N − |F | non-faulty nodes in every successful trial. In contrast, the baseline method may show larger variation because its performance depends strongly on the locations of the faulty nodes relative to the original broadcast tree.
8.6
Communication and Computational Overhead
Table 5 reports the communication-step and computational overhead of the proposed method. 25
Table 5: Communication-step and computational overhead of the proposed re-rooting method. The checked-candidate count is bounded by 6t, confirming the O(t) source-selection behavior. n 11 26 51 101 201 11 26 51 101 201
t Faults N 10 1 331 25 1 1951 50 1 7651 100 1 30301 200 1 120601 10 2 331 25 2 1951 50 2 7651 100 2 30301 200 2 120601
Avg. Reloc. Hops 7.633 18.369 36.735 72.856 145.151 7.649 18.656 36.507 72.978 146.006
Avg. Total Steps 17.633 43.369 86.735 172.856 345.151 17.649 43.656 86.507 172.978 346.006
Min–Max Steps 10–20 26–50 51–100 103–200 204–400 10–20 25–50 51–100 101–200 201–400
Avg. Runtime (ms) 0.002129 0.002267 0.002395 0.003168 0.005129 0.003954 0.005808 0.009112 0.019914 0.036946
Avg. Checked 1.000 1.000 1.000 1.000 1.000 7.278 19.065 39.500 78.585 151.961
The fault-free EJ broadcast completes in t = n − 1 parallel steps. The proposed method adds one preliminary relocation phase from the original source S to the selected new source N S. Since the diameter of Hn is t, the relocation distance satisfies d(S, N S) ≤ t.
(157)
Therefore, the total broadcast time satisfies Btotal (t) ≤ 2t.
(158)
The maximum total-step values in Table 5 confirm this bound. The computational overhead comes from selecting N S. Since the proposed source-selection algorithm scans a linear-size boundary of size 6t, the source-selection cost is O(t).
(a) Checked candidates
(b) Runtime
Figure 6: Source-selection overhead versus network diameter t. (a) The number of checked candidates remains bounded by the graph-distance-t boundary size 6t, confirming the O(t) source-selection behavior. (b) The measured runtime remains small across all tested network sizes. Figure 6 (a) shows that the number of checked candidates is bounded by 6t, while Figure 6 (b) shows the measured source-selection runtime. 26
8.7
Comparative Discussion
Although the experimental comparison in this work focuses on the original non-fault-tolerant one-to-all broadcasting algorithm, it is useful to position the proposed re-rooting method relative to common fault-tolerant communication approaches. Table 6 summarizes the qualitative differences between these approaches and the proposed re-rooting method. Table 6: Qualitative comparison with common fault-tolerant broadcasting strategies. Method Redundant trees Multiple paths Adaptive rerouting Local recovery Proposed re-rooting
Extra Runtime structures adaptation Yes Low/Med. Yes Medium No/Partial High Partial Medium No Low
Changed broadcast Yes Yes Yes Yes No
The main advantage of the proposed method is its simplicity. It is designed specifically for dense EJ networks, whose algebraic and geometric structure allows the source to be relocated so that one or two faulty nodes lie on the graph-distance-t boundary. Since boundary nodes are leaves in the one-to-all broadcast tree, they do not need to forward the message. Therefore, the original broadcast procedure can be preserved.
8.8
Failure Model and Limitations
The proposed method is designed for static node-failure scenarios. In this model, the set of faulty nodes is known before the broadcast begins and does not change during message propagation. This work focuses on one- and two-node failures. For any pair of faulty nodes in a dense EJ network, the boundary-difference theorem guarantees the existence of a node N S whose graph distance from both faulty nodes is exactly t. Therefore, the proposed method provides a deterministic guarantee for all one- and two-node fault configurations. The present model does not directly address link failures. A failed link may interrupt communication even when both endpoint nodes remain operational. Extending the re-rooting idea to link failures would require a different condition, possibly based on avoiding failed edges along the six directional broadcast sectors rather than selecting a source that makes faulty nodes leaves. The model also assumes that failures are static during the broadcast. If a new node fails after the message has already been relocated to N S, the selected source may no longer satisfy the required distance condition. Handling dynamic or transient failures would require repeated re-rooting, online failure detection, or adaptive recovery during message propagation. These extensions are outside the scope of the present work.
27
8.9
Practical Implications
The proposed method is particularly suitable for systems in which the underlying communication topology is regular and the broadcast algorithm is already optimized for parallel propagation. Dense EJ networks have degree six, small diameter, regular structure, and efficient one-to-all communication. In such systems, adding redundant spanning trees or maintaining several backup routes may increase routing-table storage, control overhead, and implementation complexity. By contrast, the proposed method preserves the original EJ one-to-all broadcast algorithm and adds only a lightweight source-selection and relocation phase. This property is attractive for NoC-based chip multiprocessors, many-core accelerators, distributed edgecomputing systems, and embedded parallel systems where predictable communication behavior and low implementation overhead are important.
9
Conclusion
This paper presented a re-rooting-based fault-tolerant broadcasting method for dense Eisenstein– Jacobi networks. The method relocates the effective broadcast source so that faulty nodes are placed at graph distance equal to the network diameter from the new source. Under the standard one-to-all broadcasting algorithm, these nodes become leaf-level nodes and are not required to forward packets. For the single-fault case, a valid new source can be selected directly from the graphdistance-t boundary of the faulty node. For the two-fault case, we proved that for any pair of faulty nodes in a dense EJ network, there exists a node whose graph distance from both faulty nodes is exactly t. The proof is based on a boundary-difference coverage property showing that every network node can be written as the difference of two distance-t boundary nodes. The proposed source-selection algorithm runs in linear time with respect to the network diameter t. The communication cost consists of one relocation phase of at most t steps followed by the standard t-step broadcast. Hence, the total worst-case broadcast time is bounded by 2t. The paper also identified the theoretical limitation of the approach. An explicit counterexample in H4 shows that a common graph-distance-t source does not necessarily exist for arbitrary three-node fault configurations. Therefore, the proposed method is positioned as a deterministic lightweight solution for static one- and two-node failures in dense degree-six EJ networks. Future work will investigate whether additional structure in the dense EJ boundary can be used to further reduce the source-selection cost for special fault configurations. Additional directions include extensions to link failures, dynamic failures, and partial three-fault classes that admit common boundary re-rooting, as well as implementation-level comparisons with specific redundant-tree and adaptive-routing methods under a unified EJ network simulation framework.
28
Acknowledgment The authors would like to acknowledge the support of Kuwait University and its Department of Computer Science.
References [1] M. Flahive and B. Bose, “The topology of Gaussian and Eisenstein–Jacobi interconnection networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 21, no. 8, pp. 1132–1142, Aug. 2010. [2] B. Albader, B. Bose, and M. Flahive, “Efficient communication algorithms in hexagonal mesh interconnection networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 1, pp. 69–77, Jan. 2012, doi: 10.1109/TPDS.2011.112. [3] M.-S. Chen, K. G. Shin, and D. D. Kandlur, “Addressing, routing, and broadcasting in hexagonal mesh multiprocessors,” IEEE Transactions on Computers, vol. 39, no. 1, pp. 10–18, Jan. 1990. [4] D. D. Kandlur and K. G. Shin, “Reliable broadcast algorithms for HARTS,” ACM Transactions on Computer Systems, vol. 9, no. 4, pp. 374–398, Nov. 1991. [5] J. W. Dolter, P. Ramanathan, and K. G. Shin, “Performance analysis of virtual cutthrough switching in HARTS: A hexagonal mesh multicomputer,” IEEE Transactions on Computers, vol. 40, no. 6, pp. 669–680, Jun. 1991. [6] K. Huber, “Codes over Eisenstein–Jacobi integers,” in Finite Fields: Theory, Applications, and Algorithms. Providence, RI, USA: American Mathematical Society, 1994, pp. 165–179. [7] C. Martı́nez, E. Stafford, R. Beivide, and E. M. Gabidulin, “Modeling hexagonal networks with the Eisenstein–Jacobi graphs,” Problems of Information Transmission, vol. 44, no. 1, pp. 1–11, 2008. [8] F. Garcia, I. Stojmenovic, and J. Zhang, “Addressing and routing in hexagonal networks with applications in location update and connection rerouting in mobile phone networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 13, no. 9, pp. 963–971, Sept. 2002. [9] C. Martı́nez, E. Vallejo, R. Beivide, C. Izu, and M. Moretó, “Dense Gaussian networks: Suitable topologies for on-chip multiprocessors,” International Journal of Parallel Programming, vol. 34, no. 3, pp. 193–211, 2006. [10] R. Beivide, C. Martı́nez, and E. Vallejo, “Gaussian interconnection networks,” in Proc. Spanish Parallelism Conference, 2005. [11] A. Grama, A. Gupta, G. Karypis, and V. Kumar, Introduction to Parallel Computing, 2nd ed. Pearson, 2003. 29
[12] V. Kumar, A. Grama, A. Gupta, and G. Karypis, Introduction to Parallel Computing: Design and Analysis of Algorithms. Redwood City, CA, USA: Benjamin-Cummings, 1994. [13] J. Duato, S. Yalamanchili, and L. Ni, Interconnection Networks: An Engineering Approach. San Francisco, CA, USA: Morgan Kaufmann, 2002. [14] W. J. Dally and B. Towles, Principles and Practices of Interconnection Networks. San Francisco, CA, USA: Morgan Kaufmann, 2004. [15] S. Pasricha and N. Dutt, On-Chip Communication Architectures: System-on-Chip Interconnect. San Francisco, CA, USA: Morgan Kaufmann, 2008. [16] J. Flich and D. Bertozzi, Designing Network-on-Chip Architectures in the Nanoscale Era. Boca Raton, FL, USA: CRC Press, 2010. [17] B. Cheng, D. Wang, and J. Fan, “Independent spanning trees in networks: A survey,” ACM Computing Surveys, vol. 55, no. 14s, Article 335, pp. 1–29, 2023, doi: 10.1145/3591110. [18] S.-S. Kao, R. Klasing, L.-J. Hung, C.-W. Lee, and S.-Y. Hsieh, “A parallel algorithm for constructing multiple independent spanning trees in bubble-sort networks,” Journal of Parallel and Distributed Computing, vol. 181, Article 104731, 2023, doi: 10.1016/j.jpdc.2023.104731. [19] H. Zhang, Y. Wang, J. Fan, and C. Shu, “Edge-independent spanning trees in folded crossed cubes,” Theoretical Computer Science, vol. 970, Article 114053, 2023, doi: 10.1016/j.tcs.2023.114053. [20] K.-J. Pai, J.-S. Yang, G.-Y. Chen, and J.-M. Chang, “Configuring protection routing via completely independent spanning trees in dense Gaussian on-chip networks,” IEEE Transactions on Network Science and Engineering, vol. 9, no. 2, pp. 932–946, 2022, doi: 10.1109/TNSE.2022.3140329. [21] X. Yu, J. Zhang, and Y. Liu, “Fault tolerant and quality of service aware routing algorithm based on priority technique for scalable network-on-chip architectures,” Scientific Reports, vol. 15, Article 39590, 2025, doi: 10.1038/s41598-025-20381-3. [22] Y. Kurokawa, “Adaptive and passage-based fault-tolerant routing methods for 3D mesh network-on-chip,” Technologies, vol. 13, no. 5, Article 176, 2025, doi: 10.3390/technologies13050176. [23] X. Zhang, H. Zhang, R. Shen, and S. Pasricha, “A survey of machine learning for network-on-chips,” Journal of Parallel and Distributed Computing, vol. 182, Article 104778, 2024, doi: 10.1016/j.jpdc.2023.104778. [24] J. Samala, “Enhancing fault-tolerant application mapping in network-on-chip using transformer-based reinforcement learning,” The Journal of Supercomputing, 2025, doi: 10.1007/s10791-025-09704-0.
30