Multi-Orientation Edge-Minimum Repair for Non-Redundant Fault-Tolerant Broadcasting in Dense Eisenstein–Jacobi Networks arXiv:2606.19834v1 [cs.DC] 18 Jun 2026
Bader A. Albader Department of Computer Science, Faculty of Science, Kuwait University, Kuwait [email protected]
Abstract Dense Eisenstein–Jacobi (EJ) networks are degree-six algebraic interconnection networks whose finite quotient geometry is naturally represented by a hexagonal axialcoordinate ball. This paper studies non-redundant one-to-all broadcast repair in the dense EJ network generated by α = (t + 1) + tω, where t is the network diameter. We propose EJ-MOEM, a multi-orientation edge-minimum repair method that evaluates a constant-size family of hexagonal broadcast-tree orientations, selects a fault-aware candidate, contracts the fault-pruned tree into healthy components, and reconnects these components using external component-crossing repair edges. The resulting structure is a rooted spanning tree of the healthy subgraph: every healthy node receives the message exactly once, no faulty node is used, and the original healthy tree components are preserved. We prove that, for a chosen orientation whose fault-pruned component graph is connected, exactly c − 1 external repair edges are necessary and sufficient, where c is the number of healthy components. We also prove a depth-certificate theorem for EJ coordinate-reduction trees: every one-fault placement admits a repair of depth at most t + 1, and every two-fault placement admits a repair of depth at most t + 2. The proof uses the three-strip representation of EJ hexagons, a sector-suffix attachment lemma, a non-adjacent-sector separation lemma, and a six-direction shielding classification for paired cuts. Extended validation includes exhaustive one- and twofault enumeration for t = 2, . . . , 12, 14, 16, 18 (up to N = 1027 and 525,825 two-fault placements at t = 18), structured theorem-critical tests through t = 30, and large random tests through t = 200, all with 100% success and no violation of the theorem.
Keywords: Eisenstein–Jacobi networks, hexagonal networks, Cayley graphs, fault-tolerant broadcasting, non-redundant communication, local repair, component repair, interconnection networks, edge-minimum repair, parallel communication.
1
Introduction
One-to-all broadcasting is a basic collective communication operation in parallel and distributed systems. In a non-redundant broadcast, each healthy processor receives the message 1
exactly once. This avoids duplicate traffic, avoids unnecessary contention, and gives a clean correctness condition: the communication structure must be a rooted spanning tree of the healthy subgraph. The challenge is that a fault-free broadcast tree can be fragmented by a small number of faulty processors. Algebraic interconnection networks provide compact symmetric graph models for such problems. Dense Eisenstein–Jacobi (EJ) networks are especially attractive because their degree is six, their distance balls are discrete hexagons, and their coordinate model is compatible with simple modular addressing. The dense EJ family considered in this paper has diameter t and order N = 3t2 + 3t + 1. (1) The natural fault-free source-centered broadcast tree reaches every node in at most t steps. After faults occur, however, a fixed broadcast tree can split into multiple healthy components. A global breadth-first rebuild can restore reachability, but it may replace a large number of parent edges. The objective here is different: preserve the healthy portions of the damaged broadcast tree and add only the minimum number of external component-crossing repair edges needed to reconnect them. This paper introduces EJ-MOEM : multi-orientation edge-minimum repair for dense EJ broadcast trees. The method constructs a small family of deterministic EJ coordinatereduction broadcast trees. For each orientation, the faulty nodes are deleted, the remaining forest is contracted into components, and a component-level repair is performed. The selected candidate is the valid repaired tree with best lexicographic score, primarily minimizing repaired depth and then repair count. The contributions are as follows. • We formulate non-redundant local broadcast repair for dense EJ networks under one and two processor faults. • We define a 15-orientation EJ broadcast-tree family based on six-direction coordinate reduction in the hexagonal axial ball. • We prove the component-minimum repair theorem: for a selected orientation with c healthy components and connected component graph, exactly c−1 external componentcrossing repair edges are necessary and sufficient. • We prove an EJ depth-certificate theorem: one fault is repaired within depth t + 1, and two faults are repaired within depth t + 2. • We give worked examples illustrating the coordinate model, orientation rules, one-fault repair, two-fault repair, and the component-contraction view. • We validate the proof-derived behavior by extended exhaustive, structured, and large random tests, including exhaustive two-fault enumeration up to N = 1027 and random tests up to N = 120601.
2
2
Related Work
Akers and Krishnamurthy introduced a group-theoretic model for symmetric interconnection networks [1]. Standard references on parallel algorithms and interconnection networks discuss meshes, tori, hypercubes, collective communication, and routing primitives [2, 3]. Faulttolerant communication algorithms in toroidal networks were studied in [4]. Gaussian and Eisenstein–Jacobi networks were developed as algebraic low-degree interconnection topologies with compact routing descriptions. Martinez and coauthors modeled toroidal and hexagonal networks using Gaussian and EJ algebraic structures [9, 10, 11]. Flahive and Bose studied the topology of Gaussian and EJ interconnection networks [12], and later classified resource placements in Gaussian and EJ networks [14]. Communication algorithms in hexagonal mesh networks and Hamiltonian structures in Gaussian networks were studied in [13, 15]. Independent spanning trees in EJ networks provide multiple prebuilt broadcast structures for fault-tolerant delivery [8]. EJ-MOEM instead takes a single selected tree after the fault set is known and minimizes the number of new componentcrossing edges needed to repair it. Post-fault reconfiguration in structured networks has been studied in other topologies. Faulty hypercube broadcasting and routing algorithms use local connectivity or local safety information [5, 6]. Fault-tolerant adaptive routing in dragonfly networks preserves communication under link or router failures [7].
3
Dense EJ Network Model
Let
√ −1 + i 3 . (2) ω= 2 We represent an Eisenstein integer x + yω by the axial coordinate pair (x, y) ∈ Z2 . The six unit EJ directions are D = {(1, 0), (0, 1), (1, −1), (−1, 0), (0, −1), (−1, 1)}.
(3)
For readability, these directions are denoted by E, N, SE, W, S, N W,
(4)
respectively. The EJ distance from the origin is ρ(x, y) = dEJ ((0, 0), (x, y)) = max{|x|, |y|, |x + y|}.
(5)
The radius-t EJ ball centered at the origin is the discrete hexagon Ht = {(x, y) : |x| ≤ t, |y| ≤ t, |x + y| ≤ t}.
3
(6)
Figure 1: EJ hexagonal ball H3 with six sectors, strip axes, unit rays, and example layer values. Yellow squares mark boundary strip-intersection vertices where two strip coordinates are simultaneously tight. It contains |Ht | = 3t2 + 3t + 1
(7)
vertices. The dense EJ network considered here is generated by α = (t + 1) + tω,
(8)
N = 3t2 + 3t + 1.
(9)
so its order is The integer label associated with an axial coordinate is ϕ(x + yω) ≡ tx + (2t + 1)y
(mod N ).
(10)
Example 1 (Dense EJ coordinates for t = 3). For t = 3, the network has N = 37 nodes. The vertex (1, 0) has label ϕ(1, 0) = 3, while (0, 1) has label ϕ(0, 1) = 7 under the convention in (10).
3.1
Fault-Free Coordinate-Reduction Broadcast Trees
Let the source be s = (0, 0). A coordinate-reduction orientation chooses, for every non-source vertex v ∈ Ht , one neighbor p(v) satisfying ρ(p(v)) = ρ(v) − 1.
(11)
Lemma 1 (Fault-free EJ orientation tree). For any parent rule that assigns to every nonsource vertex v ∈ Ht a neighbor p(v) with ρ(p(v)) = ρ(v) − 1, the induced parent relation is a spanning tree rooted at s with depth at most t. 4
Proof. Every non-source vertex has exactly one parent. Along each parent edge, the layer ρ decreases by one. Therefore directed cycles are impossible and repeated parent application reaches the unique layer-zero vertex. Since every vertex of Ht has layer at most t, the resulting tree has depth at most t. Example 2 (Priority-based parent choice). Let t = 4 and consider v = (2, 1). Then ρ(v) = max{2, 1, 3} = 3. The neighbors (1, 1) and (2, 0) have layer 2, so both are valid parents. An orientation priority list decides which inward neighbor is selected.
3.2
Orientation Family
The six directions are indexed in cyclic order as δ0 = E, δ3 = W,
δ1 = SE, δ4 = N W,
δ2 = S, δ5 = N.
(12)
with all indices taken modulo six. EJ-MOEM uses a constant-size family Θ of 15 priority orientations: Ci = (δi , δi+1 , δi+2 , δi+3 , δi+4 , δi+5 ), Ri = (δi , δi−1 , δi−2 , δi−3 , δi−4 , δi−5 ), Ai = (δi , δi+3 , δi+1 , δi+4 , δi+2 , δi+5 ),
0 ≤ i < 6, 0 ≤ i < 6, 0 ≤ i < 3.
(13)
Table 1: Explicit EJ-MOEM orientation family. Directions are indexed cyclically by δ0 = E, δ1 = SE, δ2 = S, δ3 = W, δ4 = N W, δ5 = N .
4
Orientation
Priority rule
C0 C1 C2 C3 C4 C5 R0 R1 R2 R3 R4 R5 A0 A1 A2
δ0 , δ 1 , δ 2 , δ 3 , δ 4 , δ 5 δ1 , δ 2 , δ 3 , δ 4 , δ 5 , δ 0 δ2 , δ 3 , δ 4 , δ 5 , δ 0 , δ 1 δ3 , δ 4 , δ 5 , δ 0 , δ 1 , δ 2 δ4 , δ 5 , δ 0 , δ 1 , δ 2 , δ 3 δ5 , δ 0 , δ 1 , δ 2 , δ 3 , δ 4 δ0 , δ 5 , δ 4 , δ 3 , δ 2 , δ 1 δ1 , δ 0 , δ 5 , δ 4 , δ 3 , δ 2 δ2 , δ 1 , δ 0 , δ 5 , δ 4 , δ 3 δ3 , δ 2 , δ 1 , δ 0 , δ 5 , δ 4 δ4 , δ 3 , δ 2 , δ 1 , δ 0 , δ 5 δ5 , δ 4 , δ 3 , δ 2 , δ 1 , δ 0 δ0 , δ 3 , δ 1 , δ 4 , δ 2 , δ 5 δ1 , δ 4 , δ 2 , δ 5 , δ 3 , δ 0 δ2 , δ 5 , δ 3 , δ 0 , δ 4 , δ 1
EJ-MOEM: Multi-Orientation Edge-Minimum Repair
Let Tθ be the broadcast tree induced by orientation θ ∈ Θ. Let F be a set of faulty vertices with s ∈ / F . Removing the faulty vertices and their incident tree edges gives a forest Tθ − F = C1 ∪ C2 ∪ · · · ∪ Cc . 5
(14)
Let Cs denote the component containing the source. Definition 1 (Component graph). The component graph Cθ has one vertex for each component Cj of Tθ − F . Two component vertices are adjacent in Cθ if there exists a healthy EJ graph edge joining the corresponding tree components.
4.1
Certified Edge-Minimum Repair for One Orientation
For a crossing edge (a, b) from the already repaired side to an unrepaired component C, define the predicted attachment value D(a, b, C) = dT cur (s, a) + 1 + eccC (b),
(15)
where dT cur (s, a) is the depth of a in the current partial repaired tree and eccC (b) is the maximum distance from b to any vertex of C using only the original fault-pruned tree edges inside C. Algorithm 1: Certified edge-minimum repair for one EJ orientation Input: dense EJ network Ht , source s, fault set F , orientation tree Tθ . 1. Delete F and incident tree edges from Tθ . 2. Compute components C1 , . . . , Cc and identify source component Cs . 3. Build the component graph Cθ and record all healthy EJ crossing edges between components. 4. Enumerate the rooted component-level spanning choices of Cθ ; for each ordered component attachment, use the stored crossing edge with minimum attachment value. 5. Root the resulting candidate at s, compute its maximum depth, and validate fault exclusion, source reachability, acyclicity, and parent uniqueness. 6. Return the valid candidate of minimum depth; ties prefer fewer repair edges, then lower maximum out-degree, then deterministic edge order.
4.2
Multi-Orientation Selection
The full algorithm evaluates every orientation in Θ. The best valid candidate is selected lexicographically by (success, depth, repair edges, maximum out-degree, orientation rank). (16) Algorithm 2: EJ-MOEM broadcast repair Input: dense EJ network Ht , source s, fault set F , orientation family Θ. 1. Initialize candidate set B = ∅. 2. For every θ ∈ Θ, construct Tθ . 3. Apply Algorithm 1 to Tθ − F . 4. Insert every validated candidate into B. 5. Return the best valid candidate under the lexicographic score. 6
5
Correctness and Edge-Minimum Repair
Lemma 2 (Component lower bound). Let T be a spanning tree of a graph G, and let F be a fault set not containing the source. If T − F has c healthy components, then any repaired broadcast tree that preserves the healthy vertices and reconnects these components must use at least c − 1 component-crossing edges. Proof. Contract each connected component of T − F into a supernode. A broadcast tree spanning all healthy vertices must connect these c supernodes. Any connected graph on c vertices has at least c−1 edges. Each such edge corresponds to a healthy graph edge crossing between two distinct components. Theorem 1 (External repair-edge optimality). Suppose the component graph Cθ of Tθ − F is connected. Then Algorithm 1 returns a non-redundant broadcast tree over Ht − F and uses exactly c − 1 external component-repair edges. Proof. Since Cθ is connected, a component-level spanning tree rooted at Cs exists. Algorithm 1 adds one crossing edge whenever it attaches one new component, so it adds exactly c − 1 external edges. Inside each component, the fault-pruned structure is a tree. The resulting graph is connected, acyclic, includes every healthy vertex, and excludes every faulty vertex. The lower bound proves that c − 1 is minimum. Corollary 1. EJ-MOEM returns a correct non-redundant repaired broadcast tree whenever at least one tested orientation has a connected healthy component graph. Remark 1 (Orientation dominance). Since the repaired candidate for any fixed orientation θ ∈ Θ is one of the candidates considered by EJ-MOEM, the selected candidate cannot have a worse score than any single fixed-orientation candidate under the declared lexicographic score. Example 3 (Component contraction and repair). Suppose a two-fault deletion splits an orientation tree into four healthy components: the source component and three detached suffix components. The component lower bound says that at least three external repair edges are necessary. If the component graph is connected, Algorithm 1 attaches the three detached components one at a time and uses exactly three repair edges.
6
Depth Certificates in EJ Geometry
Definition 2 (EJ repair certificate). Fix an orientation θ and let Tθ − F have components C1 , . . . , Cc , with source component Cs . A K-depth repair certificate consists of an ordering of the non-source components and crossing edges (aj , bj ),
j = 1, . . . , c − 1,
(17)
where bj ∈ Cj and aj lies in the partial repaired tree T (j−1) . The certificate condition is dT (j−1) (s, aj ) + 1 + eccCj (bj ) ≤ K. 7
(18)
Lemma 3 (Certificate implies bounded depth). If an orientation θ admits a K-depth repair certificate, then there exists a non-redundant repaired broadcast tree of depth at most K. Proof. Attach components in the certificate order. When Cj is attached through (aj , bj ), every vertex v ∈ Cj obtains a path from s through aj , then across (aj , bj ), and then inside Cj from bj to v. Thus dist(s, v) ≤ dT (j−1) (s, aj ) + 1 + distCj (bj , v) ≤ K.
(19)
The final structure is connected, acyclic, includes every healthy vertex, and has maximum depth at most K. Lemma 4 (Certified repair selection). If some component-level repair of Tθ − F admits a Kdepth repair certificate, then Algorithm 1 returns, for the same orientation, a valid candidate of depth at most K. Proof. Algorithm 1 enumerates the rooted component-level spanning choices of the connected component graph. The certified repair is one of these choices. Therefore the minimum-depth candidate returned by Algorithm 1 has depth no larger than K.
6.1
Hexagonal Suffixes and Sector Entries
For a vertex v = (x, y), write the three strip coordinates as X(v) = x,
Y (v) = y,
Z(v) = x + y.
(20)
The layer is ρ(v) = max{|X(v)|, |Y (v)|, |Z(v)|}. Definition 3 (Sector suffix). Let f be a fault of layer r = ρ(f ). A component C of Tθ − {f } is an r-sector suffix if every vertex of C has layer at least r + 1, the parent path from every vertex in C decreases the layer by one until it reaches a child of f , and there is an entry vertex b ∈ C of layer r + 1 with eccC (b) ≤ t − r − 1.
(21)
Lemma 5 (Sector side-entry lemma). Let C be an r-sector suffix with entry b. Suppose b lies in the sector bounded by two adjacent rays δi and δi+1 . If the chosen priority is either Ci or Ri+1 , then C has a side-entry crossing from outside the descendant interval. More precisely, there is a healthy neighbor a of b such that a ∈ / C and either ρ(a) = r + 1 or ρ(a) = r. If a is not the second fault, then a lies in the source component of the fault-pruned tree. Proof. Inside the sector bounded by δi and δi+1 , write every point in sector coordinates as uδi + vδi+1 with u, v ≥ 0. A cyclic priority Ci or the reversed priority Ri+1 chooses one of the two inward gates before the other whenever both lower the layer. The descendants of a fixed child of f form a monotone interval in the first layer beyond the cut, and the two endpoints cannot both be internal descendants of the same child of f . Hence at least one endpoint neighbor across a sector boundary is outside C. At strip-intersection vertices where two coordinates among |X|, |Y |, |Z| are tight, there are two inward directions. The priority selects one as the parent direction; the alternative gate has layer r and is not a descendant of f . The six signed strip-side cases are: 8
Tight strip of b
Interior range
Two layer-r gates
X =r+1 Y =r+1 Z =r+1 X = −(r + 1) Y = −(r + 1) Z = −(r + 1)
y<0 x<0 x, y > 0 y>0 x>0 x, y < 0
W, NW S, SE W, S E, SE N, NW E, N
In each case the alternative gate is not a descendant of f , since every descendant of f has layer strictly greater than r. The quotient identification does not change this conclusion: parent paths keep strictly decreasing canonical layer sequences and cannot pass through f. Lemma 6 (Sector suffix attachment). Let C be an r-sector suffix with entry b. If there is a healthy crossing edge (a, b) with a in the current partial repaired tree T (j−1) and dT (j−1) (s, a) ≤ r+1, then attaching C through (a, b) has certificate value at most t+1. If dT (j−1) (s, a) ≤ r+2, the value is at most t + 2. Proof. By the suffix definition, eccC (b) ≤ t − r − 1. Therefore dT (j−1) (s, a) + 1 + eccC (b) ≤ (r + 1) + 1 + (t − r − 1) = t + 1.
(22)
The same substitution with dT (j−1) (s, a) ≤ r + 2 gives t + 2. Theorem 2 (One-fault EJ depth theorem). For every t ≥ 1 and every one-fault placement F = {f } ⊆ Ht \ {s}, the EJ-MOEM orientation family contains a repaired tree of depth at most t + 1. Proof. Let r = ρ(f ). Choose a cyclic or reversed cyclic orientation whose first two priorities match the sector containing the outward children of f . Each detached component is an r-sector suffix. By the sector side-entry lemma, each suffix has a healthy lateral entry from the source component. The repaired-side endpoint has depth at most r + 1 in the original tree. The sector suffix attachment lemma gives value at most t + 1 for every detached component. Remark 2 (Explicit one-fault witness). If the failed vertex f lies at layer r in sector Si , take the cyclic or reverse orientation whose first priorities expose the two boundary directions of Si . Let b be the first layer-(r + 1) vertex of the descendant suffix cut off by f . The repair edge is the lateral edge (a, b) where a is the side-entry neighbor supplied by the sector side-entry lemma. Figure 2 shows the concrete witness used in Example 4.
9
Figure 2: One-fault side-entry witness for t = 4. The fault f = (2, 1) cuts off a local sector suffix; the dashed repair edge ((3, 0), (3, 1)) reconnects the suffix from the source component.
6.2
Two-Fault Certificate Classification
Lemma 7 (Non-adjacent sector separation). Let f and g be two faults in non-adjacent sectors of Ht , and suppose that they are not on opposite rays. Then the side-entry endpoint a supplied for a suffix detached by f is neither g nor a vertex blocked solely by g. Proof. Each side-entry edge changes one of the three strip coordinates X, Y, Z by ±1. A fault in a non-adjacent, non-opposite sector is separated from both side-entry boundaries by at least one full sector, so it cannot be the side-entry endpoint and cannot occupy the crossing edge used for that suffix. The descendant cones are disjoint except at opposite-ray boundary cases. Lemma 8 (Non-adjacent paired cuts). For two non-adjacent, non-opposite-ray faults, a side-entry endpoint for one suffix that is not in the source component can only lie in the component detached by the other cut. Proof. The outward cone of the second fault’s descendants is separated from the first suffix’s boundary lines by at least one full sector. Therefore deleting the other fault can block the parent path from the side-entry endpoint only if that endpoint lies on the boundary of the other fault’s own detached cone. If it were in a third component, the unique parent path would have to cross two distinct sector boundaries without passing through either deleted vertex, contradicting the coordinate-reduction parent rule. 10
Lemma 9 (Same-ray and opposite-ray faults). If two faults lie on the same EJ ray or on two opposite EJ rays, then some orientation in Θ admits a (t + 2)-depth repair certificate. Proof. By symmetry take the ray to be δ0 = E. For same-ray faults at layers 1 ≤ a < b ≤ t, use the alternating orientation A0 = (E, W, SE, N W, S, N ). The bounded interval between the cuts is entered from a transverse neighbor at depth at most a + 1 and has internal eccentricity at most b − a − 1, giving value at most b + 1 ≤ t + 1. The outer suffix is entered at depth at most b + 1 and has eccentricity at most t − b, giving value at most t + 2. For opposite-ray faults, the same opposite-pair priority separates the two tails. Each tail has a transverse entry with value at most t + 2. Lemma 10 (Separated-sector faults). If two faults lie in non-adjacent sectors and are not on opposite rays, then some orientation in Θ admits a (t + 2)-depth repair certificate. Proof. Choose the cyclic or reverse orientation exposing the boundary farther from the second fault. By Lemma 7, the side-entry neighbor for the first suffix cannot be the second fault. For the second suffix, by Lemma 8, the only possible obstruction is the other cut’s component, which is attached first. The first attachment has value at most t + 1; after it is attached, the second has value at most t + 2. Lemma 11 (Adjacent-sector faults). If two faults lie in adjacent sectors sharing a boundary ray, then some orientation in Θ admits a (t + 2)-depth repair certificate. Proof. Normalize the common boundary to be δ0 = E. Use orientation A0 = (E, W, SE, N W, S, N ). If both side entries are healthy, the sector suffix attachment lemma gives value at most t + 1 for both. If one entry is the other fault, attach the component with the unblocked outer side first with value at most t + 1; after it is attached, the second component has value at most t + 2. Lemma 12 (Boundary microcomponents). If a detached component is represented only through a quotient wraparound edge at the boundary of Ht , then it still has a (t + 2) attachment. Proof. A boundary microcomponent has one or two consecutive boundary vertices, so eccC (b) ≤ 1. The repaired-side endpoint a is a vertex of the original source component with depth at most t. If C is a single boundary vertex, the certificate value is at most t + 1. If C has two consecutive boundary vertices, the value is at most t + 2. Theorem 3 (EJ-MOEM t + 2 depth theorem). For every dense EJ network Ht with t ≥ 2 and every fault set F ⊆ Ht \ {s} with |F | ≤ 2, the EJ-MOEM orientation family contains a valid repair of depth at most t + 2. If |F | = 1, depth at most t + 1 is sufficient. Proof. The case |F | = 0 is the fault-free tree of depth at most t. The case |F | = 1 is the one-fault depth theorem. For |F | = 2: ray-resident fault pairs are assigned to Lemma 9; nonadjacent, non-opposite-ray sector pairs are assigned to Lemma 10; adjacent-sector pairs are assigned to Lemma 11; boundary quotient representatives are covered by Lemma 12. These cases are mutually exclusive under the stated priority order and exhaustive after dihedral normalization. Hence some orientation in Θ admits a (t+2) certificate, the component graph is connected, and Algorithm 1 returns a candidate of depth at most t + 2. 11
Corollary 2 (Minimum repair count under the depth bound). For every one- or two-fault placement covered by the preceding theorem, the returned EJ-MOEM tree satisfies the stated depth bound and uses exactly c − 1 external component-repair edges for its selected faultpruned orientation. Table 2: EJ depth-certificate templates used in the t + 2 proof. Fault signature Orientation strategy Detached component Certificate shape bound One interior-sector Choose Ci or Ri exposfault ing a side entry One boundary fault Use transverse priority Two faults on same ray Two faults on opposite rays Two faults in separated sectors Two faults in adjacent sectors Boundary wraparound pair
Class
Use Ai to expose transverse directions Use Ai to separate the tails Use cyclic or reverse priority Use Ai around shared boundary ray Use quotient representative
One monotone hexago- t + 1 nal suffix One boundary arc or t + 1 small cap One or two nested axial t + 2 tails Two independent tails t + 2 Two sector suffixes
t+2
Two sector suffixes
t+2
One- or two-node mi- t + 2 crocomponent
Table 3: Normalized two-fault sector-case audit. Normalized condition Covering result
Ray-resident pair Separated sectors Adjacent sectors Boundary representative
Both faults on same ray or opposite rays Sector indices differ by two, three, or four modulo six Sectors share one boundary ray Side-entry edge via quotient boundary
Lemma 9 Lemmas 8 and 10 Lemma 11 Lemma 12
Example 4 (One-fault depth certificate). For t = 4, let f = (2, 1) with ρ(f ) = 3. Choose orientation C0 = (E, SE, S, W, N W, N ). The first layer-4 entry in the descendant suffix is b = (3, 1); its side-entry neighbor is a = (3, 0), which has layer 3 and lies in the source component. The repair edge is ((3, 0), (3, 1)) with certificate value 3 + 1 + 0 = 4 = t. Example 5 (Two-fault depth certificate). For t = 4, suppose two faults lie in adjacent sectors: f1 = (1, 0) and f2 = (0, 1). The alternating opposite-pair orientation attaches the component with the unblocked outer side first with value at most t + 1. After it is attached, the second component attaches with value at most t + 2. 12
Figure 3: Schematic adjacent-sector two-fault repair for t = 4. After the unblocked suffix is attached, the shared-boundary entry for the second suffix becomes available. Example 6 (Complete two-fault repair for t = 3). Let t = 3, N = 37, s = (0, 0), and fault set F = {(1, 0), (2, 0)}. Use the alternating orientation A0 = (E, W, SE, N W, S, N ). After deleting the two faults, the only outer suffix beyond (2, 0) is C2 = {(3, 0)}. The neighbors of (3, 0) include the healthy boundary vertex (2, 1) ∈ Cs . Choose crossing edge ((2, 1), (3, 0)). Since eccC2 ((3, 0)) = 0 and dCs (s, (2, 1)) = 3, the certificate value is 3 + 1 + 0 = 4 = t + 1. The repaired tree uses exactly one repair edge.
7
Experimental Validation
The validation suite checks the implementation against the proved invariants. Every reported case verifies fault exclusion, source reachability, parent uniqueness, acyclicity, number of external repair edges, number of components, final depth, and the selected orientation.
13
7.1
Extended Exhaustive Validation
Table 4: Extended exhaustive EJ-MOEM validation. Every one- and two-fault placement was tested for the listed diameters. t
N
|F |
Cases
Success
Max depth
Max over.
Max repair
Max comp.
Min good
2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 14 14 16 16 18 18
19 19 37 37 61 61 91 91 127 127 169 169 217 217 271 271 331 331 397 397 469 469 631 631 817 817 1027 1027
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
18 153 36 630 60 1,770 90 4,005 126 7,875 168 14,028 216 23,220 270 36,315 330 54,285 396 78,210 468 109,278 630 198,135 816 332,520 1,026 525,825
100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100%
3 3 4 5 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 15 15 17 17 19 19
1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 3 1 3 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4
2 4 2 4 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5
15 15 15 15 12 7 12 7 12 7 12 7 12 7 12 7 12 7 12 7 12 7 12 7 12 7 12 7
14
7.2
Structured and Large-Scale Validation
Table 5: Structured theorem-critical and sampled stress tests. All rows use two faults. t
N
15 15 15 15 15 15 15 20 20 20 20 20 20 20 25 25 25 25 25 25 25 30 30 30 30 30 30 30
721 721 721 721 721 721 721 1261 1261 1261 1261 1261 1261 1261 1951 1951 1951 1951 1951 1951 1951 2791 2791 2791 2791 2791 2791 2791
Mode same-ray opposite-ray adjacent near-source adjacent sector grid boundary micro non-adjacent sector uniform random same-ray opposite-ray adjacent near-source adjacent sector grid boundary micro non-adjacent sector uniform random same-ray opposite-ray adjacent near-source adjacent sector grid boundary micro non-adjacent sector uniform random same-ray opposite-ray adjacent near-source adjacent sector grid boundary micro non-adjacent sector uniform random
Cases/trials
Success
Avg over.
Max over.
Avg repair
Max repair
630 675 42 216 702 324 5,000 1,140 1,200 42 216 942 324 5,000 1,800 1,875 42 216 1,182 324 5,000 2,610 2,700 42 216 1,422 324 5,000
100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100%
0.867 0.996 1.000 0.000 0.171 0.000 0.227 0.900 0.998 1.000 0.000 0.159 0.000 0.164 0.920 0.998 1.000 0.000 0.152 0.000 0.141 0.933 0.999 1.000 0.000 0.148 0.000 0.127
1 1 1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1
1.733 1.867 2.143 1.667 0.752 1.667 1.767 1.800 1.900 2.143 1.667 0.752 1.667 1.807 1.840 1.920 2.143 1.667 0.751 1.667 1.839 1.867 1.933 2.143 1.667 0.751 1.667 1.869
2 2 3 2 2 2 3 2 2 3 2 2 2 3 2 2 3 2 2 2 3 2 2 3 2 2 2 3
Table 6: Large random validation. Time is wall-clock seconds for the complete row. t
N
|F |
Trials
Success
Avg depth
Max depth
Avg over.
Max over.
Avg repair
Max repair
Time (s)
50 50 100 100 200 200
7651 7651 30301 30301 120601 120601
1 2 1 2 1 2
1,000 1,000 1,000 1,000 1,000 1,000
100% 100% 100% 100% 100% 100%
50.033 50.084 100.020 100.036 200.014 200.019
51 51 101 101 201 201
0.033 0.084 0.020 0.036 0.014 0.019
1 1 1 1 1 1
0.952 1.910 0.982 1.961 0.986 1.980
1 2 1 2 1 2
87.2 122.1 355.4 487.5 1477.7 1981.8
15
Figure 4: Depth-overhead summary for the validation run. Panel (a) gives percentage distributions of exact two-fault overheads from exhaustive enumeration; panels (b) and (c) summarize average and maximum overhead for structured stress tests and large random tests, respectively.
7.3
Interpretation
The validation results support three points. First, the implementation realizes the proved depth guarantees on exhaustive and stress-tested finite instances. Second, the certified component-repair procedure realizes the predicted c − 1 edge count. Third, although the proof guarantees depth t + 2 for all two-fault placements, overhead two appears only in the small t = 3 exhaustive case, while all larger exhaustive, structured, and random tests observed maximum overhead at most one.
7.4
Baseline Interpretation
Table 7: Objective-level and numerical comparison with natural baselines. Numerical rows: t = 10, N = 331, F = {(5, 0), (10, 0)}, s = (0, 0). Method
Optimizes
New parent edges
Depth
Limitation
Global BFS rebuild
Reachability
Up to Θ(N ) = 330
t = 10
Fixed orientation C0 Fixed orientation A0
Component repair Component repair
c−1=2 c−1=1
11 = t + 1 10 = t
Independent-tree redundancy EJ-MOEM
Path/tree diversity
Not applicable
Not comparable
c−1=1
10 = t
May replace the damaged tree entirely Preselected; may not be optimal Not known before faults observed Precomputes trees; does not minimize repair edges Depth proof covers |F | ≤ 2
Best validated orientation
16
8
Complexity
For one orientation, constructing the coordinate-reduction tree takes O(N ) time. Deleting faults and computing connected components takes O(N ) time. Crossing edges are found by scanning the six neighbors of each healthy vertex, also O(N ). Component eccentricities are computed by two tree sweeps inside each component in linear time. EJ-MOEM evaluates a constant number of orientations, so the total running time is O(N ) for the one- and two-fault setting.
9
Discussion
The EJ case is not merely the Gaussian case with six directions. Gaussian coordinate balls are diamonds under the Manhattan metric, while EJ coordinate balls are hexagons described by three axial strips. At strip-intersection vertices, an EJ boundary or sector-corner cut may have two simultaneous tight strip coordinates, so one side entry is a layer-(r+1) lateral vertex while the other is a layer-r inward gate. The adjacent-sector pair case also has no direct degree-four Gaussian analogue. The t + 2 bound is a worst-case theorem. The validation run shows that the bound is attained in the smallest nontrivial two-fault case t = 3, but no overhead-two case was observed for t ≥ 4 in the extended exhaustive run. A natural open question is whether depth t + 1 is universally sufficient for all t ≥ 4.
10
Conclusion
This paper introduced EJ-MOEM, a multi-orientation edge-minimum repair method for nonredundant one-to-all broadcasting in dense Eisenstein–Jacobi networks. EJ-MOEM evaluates a constant-size family of six-direction coordinate-reduction broadcast trees, deletes faulty vertices, contracts the fault-pruned forest into healthy components, and reconnects those components using an externally edge-minimum set of repair edges. For any selected orientation with c healthy components and connected component graph, exactly c − 1 external component-crossing repair edges are necessary and sufficient. The depth theorem proves repairs of depth at most t + 1 for one fault and t + 2 for two faults. Extended validation confirms the proof-derived behavior with 100% success across all tested cases.
Data and Code Availability The data and code that support the findings of this study are available from the corresponding author upon reasonable request.
Acknowledgment The author thanks the Department of Computer Science, Faculty of Science, Kuwait University, for its support and research environment. This work did not receive a specific grant 17
from any funding agency in the public, commercial, or not-for-profit sectors.
References [1] S. B. Akers and B. Krishnamurthy, “A group-theoretic model for symmetric interconnection networks,” IEEE Transactions on Computers, vol. 38, no. 4, pp. 555–566, Apr. 1989. [2] F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. San Mateo, CA, USA: Morgan Kaufmann, 1992. [3] W. J. Dally and B. Towles, Principles and Practices of Interconnection Networks. San Francisco, CA, USA: Morgan Kaufmann, 2004. [4] B. F. A. AlMohammad and B. Bose, “Fault-tolerant communication algorithms in toroidal networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 10, no. 10, pp. 976–983, Oct. 1999. [5] T. C. Lee and J. P. Hayes, “Routing and broadcasting in faulty hypercube computers,” in Proc. Third Conference on Hypercube Concurrent Computers and Applications, vol. 1, 1988, pp. 346–354. [6] F. Liu and Y. Song, “Broadcast in the locally k-subcube-connected hypercube networks with faulty tolerance,” in Networking and Mobile Computing, Lecture Notes in Computer Science, vol. 3619. Berlin, Germany: Springer, 2005, pp. 305–313. [7] D. Xiang, B. Li, and Y. Fu, “Fault-tolerant adaptive routing in dragonfly networks,” IEEE Transactions on Dependable and Secure Computing, vol. 16, no. 2, pp. 259–271, Mar./Apr. 2019. [8] Z. Hussain, H. AboElFotoh, and B. AlBdaiwi, “Independent spanning trees in Eisenstein–Jacobi networks,” arXiv:2101.09797 [cs.DC], Jan. 2021. [9] C. Martinez, R. Beivide, E. Stafford, M. Moreto, and E. M. Gabidulin, “Modeling toroidal networks with the Gaussian integers,” IEEE Transactions on Computers, vol. 57, no. 8, pp. 1046–1056, Aug. 2008. [10] C. Martinez, E. Vallejo, R. Beivide, C. Izu, and M. Moreto, “Dense Gaussian networks: Suitable topologies for on-chip multiprocessors,” International Journal of Parallel Programming, vol. 34, no. 3, pp. 193–211, 2006. [11] C. Martinez, E. Stafford, R. Beivide, and E. M. Gabidulin, “Modeling hexagonal constellations with Eisenstein–Jacobi graphs,” Problems of Information Transmission, vol. 44, no. 1, pp. 1–11, 2008. [12] 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. 18
[13] B. A. 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. [14] M. Flahive and B. Bose, “On resource placements in Gaussian and EJ networks,” IEEE Transactions on Computers, vol. 62, no. 3, pp. 623–626, Mar. 2013. [15] B. A. Albader and B. Bose, “Edge-disjoint Hamiltonian cycles in Gaussian networks,” IEEE Transactions on Computers, vol. 65, no. 1, pp. 315–321, Jan. 2016. [16] C. Camarero, C. Martinez, and R. Beivide, “Symmetric interconnection networks from cubic crystal lattices,” arXiv:1311.2019, 2013. [17] C. Camarero, C. Martinez, E. Vallejo, and R. Beivide, “Projective networks: Topologies for large parallel computer systems,” arXiv:1512.07574, 2015. [18] D. Kliazovich, F. Granelli, and D. Miorandi, “A survey of fault-tolerant network-onchip architectures,” IEEE Communications Surveys and Tutorials, vol. 15, no. 4, pp. 1676–1690, 2013. [19] S. Pasricha and N. Dutt, On-Chip Communication Architectures: System on Chip Interconnect. San Francisco, CA, USA: Morgan Kaufmann, 2008.
19