Re-Rooting-Assisted Edge-Minimum Runtime Repair for Node and Link Failures in Dense Eisenstein–Jacobi Broadcast Networks arXiv:2606.21133v1 [cs.DC] 19 Jun 2026
Bader A. Albader Department of Computer Science, Faculty of Science, Kuwait University, Kuwait [email protected]
Abstract One-to-all broadcasting in dense Eisenstein–Jacobi (EJ) networks relies on diameterlevel spanning trees that fragment when nodes or links fail. This paper introduces the selected triple (r, θ, Kr,θ )–a chosen root, a chosen EJ coordinate-reduction orientation, and the healthy component graph induced by that choice–as the fundamental unit of analysis for joint node/link fault recovery. The central result is a necessary and sufficient condition: hybrid repair succeeds if and only if the healthy EJ graph G′ = Ht − FV − FE is connected. When G′ is connected, a spanning tree of Kr,θ maps to exactly c − 1 component-crossing repair edges, which is minimum for the selected pruned tree. Deterministic guarantees include: one/two faulty nodes are always placed on the distance-t boundary by re-rooting; a single failed link is either avoided or repaired by exactly one crossing edge; and the repaired depth satisfies Dr,θ ≤ 2t + 1 under shallowest-layer entry selection. A 260,000-trial validation campaign confirms 100% recovery and substantial repair-edge reduction over fixed-source repair across five network scales up to N = 120601 nodes, while global-BFS, near-miss, and capsensitivity audits clarify the tradeoff between reachability, forwarding-state changes, and ranked root selection.
Keywords: Eisenstein–Jacobi networks, hexagonal networks, fault-tolerant broadcasting, re-rooting, link failures, component repair, edge-minimum repair, interconnection networks, Network-on-Chip, runtime recovery.
1
Introduction
One-to-all broadcasting is a core collective operation in parallel computers, many-core systems, Network-on-Chip fabrics, and distributed accelerators. Dense Eisenstein–Jacobi (EJ) networks are attractive for such communication because they have degree six, small diameter, vertex symmetry, and a regular hexagonal coordinate geometry. The fault-free EJ broadcast reaches all nodes in one network diameter by expanding through six directional sectors. However, if a faulty node or failed link appears at an internal forwarding position, the fault-free tree can fragment and downstream nodes may fail to receive the broadcast. 1
Two existing EJ mechanisms motivate the present work. First, source re-rooting can relocate the effective source so that one or two faulty nodes lie on the graph-distance-t boundary of the new source; in the standard EJ broadcast, boundary nodes are leaves and do not forward. Second, component repair can reconnect a fault-pruned EJ broadcast tree by contracting its healthy components and adding component-crossing edges. These mechanisms solve different problems. Re-rooting alone does not handle failed links or residual component cuts. Component repair alone repairs a chosen tree, but does not explain how to choose a source and orientation that reduce the damage before repair. This paper studies the combined object (r, θ, Kr,θ ),
(1)
where r is the selected effective source, θ is a selected EJ coordinate-reduction orientation, and Kr,θ is the healthy component graph induced after node and link pruning. The optimization is therefore not only to find a valid re-rooted source or to repair a fixed tree. It is to choose a root–orientation pair that reduces the residual component structure and then repair that structure with the minimum possible number of external component-crossing edges.
1.1
Novelty Separation
Table 1 separates this paper from the two direct EJ ingredients. This separation is important because the present paper should not be read as merely repeating the one/two-node boundary theorem or the c − 1 component theorem. Those are foundations. The new problem is joint node/link/runtime recovery by selecting the coupled unit (r, θ, Kr,θ ). Table 1: Novelty separation from the two EJ foundation mechanisms. Ingredient Solves Not solved by that ingredient alone EJ re-rooting
Places one/two faulty nodes on the distance-t boundary so they become leaves in the standard broadcast.
EJ-MOEM compo- For a chosen EJ tree whose nent repair healthy component graph is connected, repairs c components using exactly c − 1 external crossing edges. This paper Selects a damage-reducing root–orientation pair, filters failed EJ links, repairs residual components with the c − 1 optimum, and characterizes recovery by healthy-graph connectivity. 2
Failed links, runtimediscovered links, mixed node/link cuts, residual component fragmentation, and repair-edge minimization. How to choose a source and orientation that reduce the damage before component repair; link-safety filtering and runtime discovery. Global optimization over all possible roots when the ranked/capped selector is used; tighter high-probability connectivity bounds for G′ under non-uniform or adversarial fault distributions.
1.2
Contributions
The contributions are as follows. C1. We introduce the selected triple (r, θ, Kr,θ ) and prove that hybrid recovery succeeds if and only if the healthy EJ graph G′ is connected—a necessary and sufficient characterization that subsumes node, link, mixed, and runtime faults. C2. We prove the EJ link-exclusion test: whether a selected broadcast tree uses a given failed link reduces to two coordinate parent comparisons, costing O(|FE |) per candidate without constructing the full tree. C3. We prove edge-minimum component repair: when Kr,θ is connected, exactly c − 1 crossing edges are necessary and sufficient, and deterministic single-link repair follows because no EJ link is a bridge. C4. We prove a repaired-depth bound Dr,θ ≤ 2t + 1 under shallowest-layer entry selection, converting the near-diameter depth observed in deterministic regimes into a theorem. C5. We validate the framework over 260,000 trials at five network scales with a globalBFS rebuild audit, a cap-sensitivity audit, and a near-miss audit, demonstrating 100% recovery and quantifying the structural repair-edge advantage over fixed-source repair.
1.3
Scope
The deterministic guarantees in this paper are deliberately limited but explicit. One/twonode boundary re-rooting is guaranteed. Single-link repair is guaranteed after a root– orientation pair is selected. The c − 1 repair theorem is exact whenever the selected component graph is connected. For higher-order node/link faults, success is governed by healthygraph connectivity: if the healthy EJ graph remains connected, the component graph of every selected pruned tree is connected and the hybrid repair succeeds; if the healthy graph is disconnected, no broadcast tree over all healthy vertices can exist. The ranked/capped part of the implementation affects which successful root–orientation pair is chosen and therefore the observed repair-edge count and depth, not the existence of a successful repair under healthygraph connectivity, because the original healthy source and its orientations are pinned as fallback candidates.
2
Related Work
Algebraic interconnection networks use group, ring, or Cayley-graph structure to obtain symmetry, compact routing descriptions, and low-degree regularity. General treatments of interconnection networks, collective communication, and routing appear in standard texts on parallel algorithms and network design [2, 3, 4, 5]. Dense EJ networks belong to this family: their degree-six adjacency comes from the six unit directions of the triangular/EJ lattice, and the finite quotient gives a compact hexagonal topology with small diameter [8, 9]. Hexagonal mesh and HARTS-style systems motivated early addressing, routing, and reliable 3
broadcast algorithms in six-neighbor networks [6, 7], while later EJ formulations supplied the algebraic model used here [10]. Dense EJ networks belong to the broader family of algebraic quotient and circulant interconnection networks, where vertex transitivity and compact generator sets support concise routing and broadcasting rules [1, 8, 9]. The present paper does not rely on results from other quotient-lattice families; it is self-contained for the degree-six EJ topology. The key recovery mechanisms–the distance-t boundary re-rooting lemma, the two-comparison link-exclusion test, and the six-neighbor local obstruction model–all use the triangular EJ coordinate system and are proved directly in this manuscript. Fault-tolerant broadcasting has also been studied in broader distributed and parallelcomputer settings. Classical work considered time bounds and impossibility tradeoffs for fault-tolerant broadcast in distributed networks [11, 12]. Hypercube fault-tolerant routing and broadcasting developed another line of results in which a structured topology is preserved while faulty nodes or links are bypassed [13]. Independent or completely independent spanning trees provide tree diversity by precomputing multiple delivery structures, and surveys summarize this protection-oriented approach [14]. Network-on-Chip fault tolerance similarly includes adaptive routing, region avoidance, spare-path use, virtual-channel based rerouting, and topology-agnostic deadlock-free schemes [15, 16, 17, 18]. The present work occupies a different point in this design space. It does not precompute several complete trees, duplicate every broadcast along multiple paths, or optimize arbitrary packet traffic under background load. Instead, it starts from a deterministic EJ diameterlevel broadcast tree after a small fault set is known, selects a root–orientation pair to reduce the damaged component structure, and adds the minimum number of external componentcrossing edges for the selected pruned tree. The external global-BFS rebuild baseline is intentionally included to make this distinction clear: BFS rebuild can restore reachability with small depth, but it may replace many parent pointers and therefore does not optimize local component-preserving repair state. To our knowledge, no prior published method addresses joint root–orientation selection for component-minimizing repair of EJ broadcast trees under mixed node and link faults. The closest EJ-specific foundations are node-only boundary re-rooting and multi-orientation component repair. Those works solve disjoint subproblems; the present manuscript is selfcontained and restates the results it needs, using them as ingredients in the coupled triple (r, θ, Kr,θ ). The irreducible contribution of this paper is therefore not a new componentrepair certificate alone nor a new re-rooting guarantee alone, but the proof that selecting the coupled triple (r, θ, Kr,θ ) gives an exact recovery condition, together with the link-exclusion test that makes this selection computationally tractable. Boundary re-rooting by itself does not address link faults or characterize when repair fails; fixed-source component repair by itself does not prove that the component graph of every selected candidate is connected whenever the healthy graph is connected. The healthy-graph connectivity theorem closes both gaps simultaneously. The global-BFS rebuild baseline included in the experiments is therefore not a competing EJ broadcast-repair method in the same objective class. It is an intentionally strong external reachability baseline that shows the cost of discarding healthy tree structure entirely, making the repair-edge reduction advantage of the hybrid method interpretable. Reliable broadcast algorithms for HARTS-style hexagonal meshes address faulty proces4
sors by storing alternate paths and recovery rules in the network [7]. Such protection-oriented methods improve robustness but maintain redundancy before faults are known. In contrast, the hybrid method stores a constant family of EJ orientation rules and inserts only O(c − 1) exceptional forwarding rules after the fault set is observed. For the single-fault case, boundary re-rooting or single-link repair requires zero or one exceptional rule, whereas redundant path methods reserve alternate state regardless of whether it is needed. Independent spanning tree methods precompute multiple complete spanning trees of the fault-free graph, providing tree diversity before faults occur [14]. They are complementary but solve a different optimization problem: an IST is fixed before the fault set is known, whereas the hybrid method chooses a root–orientation pair after faults are observed. A fault placement that creates many components in one precomputed tree may create fewer components in a differently rooted EJ orientation. The hybrid method exploits this post-fault selection freedom and then proves c − 1 repair optimality for the selected pruned tree.
3
Dense EJ Network Model
Let
√ −1 + i 3 . (2) ω= 2 An EJ integer is written as x + yω and represented by the axial coordinate pair (x, y) ∈ Z2 . The six unit directions are D = {(1, 0), (0, 1), (1, −1), (−1, 0), (0, −1), (−1, 1)}.
(3)
The EJ distance from the origin is ρ(x, y) = max{|x|, |y|, |x + y|}.
(4)
Ht = {(x, y) : |x| ≤ t, |y| ≤ t, |x + y| ≤ t}.
(5)
N = 3t2 + 3t + 1
(6)
The radius-t hexagonal ball is
It contains vertices. The dense EJ network considered in this paper is generated by α = (t + 1) + tω,
(7)
and is the quotient of the EJ lattice modulo α. The integer label associated with (x, y) is ϕ(x + yω) ≡ tx − (t + 1)y
(mod N ).
(8)
Thus unit axial moves correspond to the six degree-six circulant jumps ±t,
±(t + 1),
under the chosen convention. 5
±(2t + 1)
(9)
For a node a and offset z ∈ Ht , the translated node is denoted by a + z in the quotient. The relative coordinate of node v with respect to root r is ∆r (v) = can(v − r) ∈ Ht ,
(10)
where can returns the canonical axial representative in the radius-t hexagon.
Figure 1: Dense EJ network for t = 3 (n = 4, N = 37) represented as an axial hexagon. Boundary nodes satisfy ρ(x, y) = 3 and are highlighted. Integer labels use ϕ(x+yω) = 3x−4y (mod 37), and the six annotated directions correspond to the six unit EJ moves.
4
Rooted EJ Broadcast Orientations
A coordinate-reduction orientation chooses one parent for every non-root vertex by selecting an inward neighbor whose EJ layer is one smaller. Definition 1 (EJ coordinate-reduction parent rule). Let θ = (d1 , d2 , . . . , d6 ) be an ordered list of the six EJ unit directions. For a nonzero coordinate z ∈ Ht , define pθ (z) = z + dj ,
(11)
where dj is the first direction in θ satisfying ρ(z + dj ) = ρ(z) − 1.
6
(12)
For a selected root r, the tree Tr,θ contains the directed parent edge r + pθ (∆r (v)) −→ v
(13)
for every non-root node v before faults are applied. Lemma 1 (Fault-free EJ orientation tree). For any root r and any orientation θ that assigns to every non-root coordinate an inward parent, Tr,θ is a spanning tree of the dense EJ network rooted at r with depth at most t. Proof. Every non-root vertex has exactly one parent. Along each parent edge, the layer ρ(∆r (v)) decreases by one. Hence directed cycles are impossible and repeated parent application reaches the unique layer-zero coordinate, namely the root. Since every canonical coordinate has layer at most t, the maximum root-to-node depth is at most t.
4.1
Orientation Family
The hybrid framework can use either one fixed EJ broadcast orientation or a constant-size family. For compatibility with EJ-MOEM, we use the 15-orientation family. Let the six directions be indexed cyclically by δ0 , . . . , δ5 . Define 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,
(14) (15) (16)
with indices modulo six. The selected family affects repair quality and depth, not the graphtheoretic optimality theorem for a chosen tree.
5
Fault Model and Recovery Objective
Let FV ⊆ V be the faulty-node set and FE ⊆ E the failed-link set. The original source is assumed healthy. A recovered broadcast must reach every node in V \ FV without using failed nodes or failed links. For a selected root–orientation pair (r, θ), pruning removes faulty nodes, tree edges incident to faulty nodes, and failed tree links: − Tr,θ = Tr,θ − FV − FE .
(17)
Cr,θ = {C1 , C2 , . . . , Cc }
(18)
Let − be the connected components of Tr,θ on healthy vertices.
Definition 2 (Healthy component graph). The healthy component graph Kr,θ has one vertex for each component Ci . Two component vertices Ci and Cj are adjacent if there exists a healthy EJ graph edge uv ∈ E \ FE with u ∈ Ci , v ∈ Cj , and u, v ∈ / FV . 7
For a successful candidate, let ρr,θ be the number of external component-crossing repair edges, Dr,θ the repaired depth, and Mr,θ the number of inspected root/orientation candidates. The hybrid selector used in this paper orders valid candidates lexicographically as min(ρr,θ , Dr,θ , Mr,θ ).
(19)
Thus the primary metric is exceptional forwarding state, while repaired depth is reported separately as a latency-related metric. This paper does not evaluate a separate weighted latency objective; avoiding an unevaluated objective prevents confusion between the proven edge-minimum repair certificate and possible future latency-dominant engineering choices. An avoid-only candidate is one for which λ(r, θ, FE ) = 0 and every node in FV that can be neutralized by re-rooting satisfies dist(r, f ) = t. Equivalently, the selected tree neither uses any failed link nor has a neutralized faulty node at an internal forwarding position. In that case zero component-crossing repair edges are needed, and the candidate succeeds without invoking the component-repair phase.
6
EJ Re-Rooting Preliminaries
The graph-distance-t boundary of the origin is Bt = {z ∈ Ht : ρ(z) = t}.
(20)
The distance-t boundary of a node a is a + Bt . Lemma 2 (EJ boundary-difference coverage). For the dense EJ network of diameter t, Bt − Bt = V.
(21)
Equivalently, for every displacement A ∈ V , there exist U, V ∈ Bt such that A = U − V in the EJ quotient. Proof. Every node has a canonical representative A = (x, y) ∈ Ht . It is enough to show that every point of Ht is a difference of two boundary points. In the sector x ≥ 0, y ≥ 0, and x + y ≤ t, write A = r + sω with r, s ≥ 0 and r + s ≤ t. Define U = (r − t) + tω,
V = −t + (t − s)ω.
(22)
Then U − V = r + sω = A. Moreover, ρ(r − t, t) = max{t − r, t, r} = t, ρ(−t, t − s) = max{t, t − s, s} = t,
(23) (24)
so U, V ∈ Bt . The remaining five sectors follow by multiplication by EJ units, which preserve adjacency, distance, and the boundary. Therefore every displacement in V is in Bt − Bt . Theorem 1 (One/two-node EJ re-rooting). Let FV be a node-fault set with |FV | ≤ 2. There exists a root r such that dist(r, f ) = t for every f ∈ FV . (25) 8
Proof. For one fault f , choose any r ∈ f + Bt . For two faults f1 , f2 , set A = f2 − f1 . By boundary-difference coverage, choose U, V ∈ Bt with A = U − V . Let r = f1 + U . Then r − f1 = U , so dist(r, f1 ) = t. Also r − f2 = f1 + U − f2 = U − A = V , so dist(r, f2 ) = t. Corollary 1 (Zero-repair node-only cases). If |FV | ≤ 2, FE = ∅, and the selected EJ broadcast tree treats every distance-t node as a leaf, then a root satisfying the preceding theorem makes every faulty node a leaf. Removing those faulty leaves does not disconnect the healthy tree, so zero external repair edges are required.
Figure 2: Two-fault re-rooting on H4 . Under the original source, the two faults can lie on internal forwarding branches. After re-rooting to r = 28, both faulty nodes lie on the distance-3 boundary of the selected root and become leaves, so no component repair is needed in the node-only case. Remark 1 (Three-fault limitation). The one/two-node guarantee does not extend to arbitrary triples. A zero-repair three-node re-rooting exists precisely when \ {r : dist(r, f ) = t} ̸= ∅. (26) f ∈FV
There are triples in H4 with empty triple boundary intersection. Thus all higher-order nodefault claims in this hybrid framework must be stated as conditional or empirical unless an additional fault-class restriction is imposed. Example 1 (Concrete H4 three-fault obstruction). Let t = 3 and N = 37. In the integerlabel representation with jumps 3, 4, 7, take F1 = 0,
F2 = 5,
F3 = 14.
(27)
The distance-three boundary of label 0 is B3 (0) = {2, 5, 9, 12, 13, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 28, 32, 35}. (28) 9
By vertex transitivity, B3 (Fi ) = Fi + B3 (0) modulo 37. Direct intersection gives B3 (F1 ) ∩ B3 (F2 ) ∩ B3 (F3 ) = ∅.
(29)
Therefore no re-rooted source is at distance t from all three faults. This example is used only to mark the deterministic boundary of the node-only re-rooting theorem; the hybrid method may still recover many three-fault instances after component repair.
7
EJ Link-Failure Exclusion
Node re-rooting uses distance-to-boundary constraints. Link failures require a different condition: a failed link matters only if the selected broadcast tree uses that link as a parent–child edge. Definition 3 (Failed-tree-link count). For a root–orientation pair (r, θ) and failed-link set FE , define λ(r, θ, FE ) = |E(Tr,θ ) ∩ FE |. (30) A candidate is link-safe if λ(r, θ, FE ) = 0. Proposition 1 (EJ link-exclusion test). Let e = {u, v} be a failed EJ link. For a selected root r and orientation θ, write ∆r (w) for the canonical coordinate of w relative to r. Then Tr,θ uses e if and only if ∆r (u) = pθ (∆r (v))
or
∆r (v) = pθ (∆r (u)).
(31)
Thus testing whether a candidate uses one failed link requires only constant-size coordinate comparisons after canonical reduction. Proof. By definition of the rooted orientation tree, the parent of a non-root node w is the quotient node with relative coordinate pθ (∆r (w)). Therefore u is the parent of v if and only if ∆r (u) = pθ (∆r (v)). Similarly, v is the parent of u if and only if ∆r (v) = pθ (∆r (u)). Since an undirected failed link is used by the directed broadcast tree exactly in one of these two parent–child cases, the equivalence follows. Corollary 2 (Link-safe roots and orientations). For a failed-link set FE , a candidate (r, θ) is link-safe if and only if the two parent equalities in the link-exclusion test are false for every e ∈ FE . Testing one candidate costs O(|FE |) coordinate comparisons and does not require constructing the full tree. Example 2 (Link-exclusion test on H4 ). Let t = 3, r = 0, and use the first cyclic orientation. The node with label 3 has coordinate (1, 0) and parent label 0, so the failed link {0, 3} satisfies the endpoint-parent test and is a failed tree link. By contrast, labels 28 and 35 correspond to adjacent boundary coordinates (−3, 0) and (−2, −1), but neither endpoint is the selected parent of the other under this orientation; the link is an EJ graph edge but not a tree edge. Thus the candidate using r = 0 is unsafe for {0, 3} but safe for {28, 35}. The test uses only the two parent comparisons in Proposition 1 and therefore costs O(|FE |) for a fixed candidate. 10
8
Edge-Minimum Component Repair
The following theorem is independent of the special EJ geometry once the tree and component graph are fixed. It is included here because it is the central repair certificate of the hybrid framework. − Lemma 3 (Component lower bound). If Tr,θ has c healthy components, any non-redundant repaired broadcast tree that preserves those internal components must use at least c − 1 external component-crossing repair edges.
Proof. Contract each healthy component into one supernode. A repaired broadcast tree spanning all healthy nodes must connect the c supernodes. Any connected graph on c vertices has at least c − 1 edges. Each such edge corresponds to a component-crossing repair edge in the original network. Theorem 2 (Edge-minimum repair for a selected EJ tree). If the healthy component graph − Kr,θ is connected, then Tr,θ can be repaired into a non-redundant broadcast tree over all healthy nodes using exactly c − 1 external component-crossing repair edges. This number is minimum. Proof. Since Kr,θ is connected, choose any spanning tree of Kr,θ rooted at the component containing r. For each component-level spanning-tree edge, add one corresponding healthy EJ crossing edge between the two original components. Inside each component, the original structure is a tree because it is a subgraph of Tr,θ . Contracting each component maps the repaired structure to the selected component-level spanning tree, so no cycle is introduced. The final graph is connected, acyclic, spans all healthy vertices, excludes faulty nodes and failed links, and can be rooted at r. It uses exactly c − 1 crossing edges, which is minimum by the component lower bound.
Figure 3: Component contraction and edge-minimum repair. After pruning, the healthy forest has three components. The connected component graph admits a component-level spanning tree. Mapping that spanning tree back to EJ crossing edges reconnects the original components using exactly c − 1 = 2 external repair edges.
11
Remark 2 (Repair count versus repaired depth). The repair-edge count c − 1 counts exceptional component-crossing forwarding rules. The repaired depth is a separate metric because a repair edge may attach to a component at a vertex far from that component’s farthest descendant. Therefore the hybrid framework reports both repair-edge count and repaired depth. − Lemma 4 (Repaired-depth accounting bound). Let Tr,θ have healthy components C1 , . . . , Cc , with C1 containing the selected root r. For a non-root component Ci , define
ℓ(Ci ) = min dTr,θ (r, v), v∈Ci
span(Ci ) = max dTr,θ (r, v) − ℓ(Ci ). v∈Ci
(32)
If the component-level repair attaches Ci through a crossing edge whose already-repaired endpoint has repaired depth dattach and enters Ci at a vertex bi , then every vertex of Ci is reached at repaired depth at most dattach + 1 + eccCi (bi ). (33) If bi is a shallowest-layer entry of Ci , then eccCi (bi ) ≤ span(Ci ); in general eccCi (bi ) ≤ 2 span(Ci ). Since every component is a subtree of an EJ coordinate-reduction tree of depth at most t, span(Ci ) ≤ t. Consequently, whenever the selected component repair attaches every non-root component from an endpoint of repaired depth at most t, the repaired depth satisfies Dr,θ ≤ 3t + 1, (34) and it improves to Dr,θ ≤ 2t + 1 when each component is entered through a shallowest-layer entry. If the entering crossing edge is counted as the first edge of the component suffix, this is reported as the cleaner 2t accounting bound used in the deterministic suffix cases. Proof. After a crossing edge is added from an already-repaired endpoint to an entry vertex bi of Ci , every vertex of Ci is reached by following the repaired path to the crossing endpoint, traversing the crossing edge, and then following tree edges inside Ci . The maximum additional distance inside the component is eccCi (bi ). If bi is a shallowest-layer entry, the farthest descendant lies at most the layer span away along the coordinate-reduction suffix. The shallowest-layer entry assumption is enforceable in Algorithm 1 at the component-edge selection step by selecting, among all healthy crossing edges between a parent component and Ci , an edge whose endpoint in Ci has minimum layer index. This choice is computable during the component-edge scan, does not increase the repair-edge count, and is therefore compatible with the c − 1 optimality of the edge-minimum repair theorem. Every component Ci is a connected subtree of Tr,θ , which is a rooted tree whose vertices are stratified by the EJ layer ρ(∆r (v)). Within Ci , let ℓmin and ℓmax be the minimum and maximum layer indices, so span(Ci ) = ℓmax − ℓmin . Because Ci is a connected component of a pruned rooted tree, a minimum-layer vertex v ∗ is the local root of Ci and an ancestor of every other vertex in Ci ; otherwise the parent path from a vertex of Ci to the global root would leave and re-enter Ci , contradicting component maximality after pruning. For an arbitrary entry vertex bi ∈ Ci and any vertex w ∈ Ci , the unique tree path inside Ci is contained in the union of the two ancestor paths through v ∗ , so dCi (bi , w) ≤ dCi (bi , v ∗ ) + dCi (v ∗ , w).
12
(35)
The path from bi to v ∗ follows parent edges through layers between ℓmin and ℓmax , so its length is at most ρ(∆r (bi )) − ℓmin ≤ span(Ci ). Similarly, the ancestor path from v ∗ to w has length at most ℓmax − ℓmin = span(Ci ). Hence eccCi (bi ) ≤ 2 span(Ci ). Since every layer lies between 0 and t, span(Ci ) ≤ t. Substitution proves the bounds. Remark 3 (Why deterministic rows have depth t). In the deterministic one/two-node rows, the selected re-rooted source places each faulty node on the distance-t boundary. Boundary nodes are leaves of the EJ broadcast tree, so deleting them does not create internal detached components. In the single-link rows, either the failed link is avoided or the bypass reconnects the detached suffix at the same layer where the cut occurred. Thus the deepest reachable healthy boundary layer remains t, and the repaired depth is exactly t in the deterministic rows of Table 3. Higher-order rows can have larger delivery tails because several faults may detach internal components whose best entry is not at the original shallowest layer. Corollary 3 (Deterministic-regime exact depth). In the one/two-node boundary re-rooting regime (|FV | ≤ 2, FE = ∅), the selected re-rooted tree has repaired depth Dr,θ = t whenever at least one healthy boundary vertex remains. In the single-link regime (FV = ∅, |FE | = 1) with a link-safe candidate, Dr,θ = t. Proof. In the one/two-node case, the selected root places every faulty node at layer t. These nodes are leaves and their removal does not detach any internal component, so the pruned tree keeps the same layer structure as Tr,θ on the healthy vertices. The boundary Bt has |Bt | = 6t vertices, and at most two of them are faulty. For every t ≥ 1, at least 6t − 2 ≥ 4 boundary vertices remain healthy. Hence a healthy layer-t vertex remains in the pruned tree, so the maximum repaired depth is exactly t. In the link-safe single-link case, λ = 0 and the pruned tree is identical to Tr,θ restricted to healthy nodes; the depth is again t. Example 3 (Repaired-depth accounting). Suppose a higher-order placement in H5 (t = 4) detaches a component Ci whose shallowest layer is 2 and whose deepest layer is 4, so span(Ci ) = 2. If the component is attached from a repaired endpoint at depth 3, an arbitrary entry may reach the farthest vertex at depth up to 3 + 1 + 2 = 6, giving overhead 2 above the diameter. If a shallower crossing edge enters Ci at its minimum-layer entry, the same component is reached with a smaller internal suffix, e.g., depth 3 + 1 + 1 = 5. This is why Algorithm 1 records the shallowest entry among crossing edges when a depth-bounded certificate is requested: it does not change the c − 1 repair count, but it reduces delivery-tail depth.
9
Deterministic Single-Link Repair
A single failed link has a deterministic repair guarantee in dense EJ networks. Lemma 5 (No EJ link is a bridge). Every EJ graph edge lies on a triangle in the dense EJ quotient. Therefore deleting one link cannot disconnect the dense EJ network. Proof. Let e = (u, u + d) where d is one of the six EJ unit directions. Choose a unit direction h adjacent to d in the triangular lattice, so that h − d is also a unit direction. Then u −→ u + d −→ u + h −→ u 13
(36)
uses the unit directions d, h − d, and −h, respectively. Thus e lies on a 3-cycle, possibly represented through quotient wraparound at the boundary. Hence no EJ link is a bridge. Lemma 6 (Healthy graph implies component graph). If the healthy EJ graph Ht − FV − FE − is connected, then the component graph Kr,θ is connected for every pruned tree Tr,θ over the healthy vertices. Proof. Take any two tree components. Since the healthy graph is connected, there is a healthy graph path between them. Whenever this path moves from one tree component to another, it uses a healthy crossing edge. Hence the path induces a path in the component graph. Theorem 3 (Healthy-graph connectivity is necessary and sufficient). Let FV and FE be arbitrary fault sets with the original source healthy, and let G′ = Ht − FV − FE
(37)
be the healthy EJ graph. With the mandatory healthy-source fallback used by Algorithm 1, a repaired broadcast tree over V \ FV exists if and only if G′ is connected. In particular, when G′ is connected, the component graph Kr,θ is connected for every retained root–orientation pair (r, θ), and the repair phase succeeds with exactly c − 1 external component-crossing edges for that selected pruned tree. Proof. For sufficiency, suppose G′ is connected. By the preceding lemma, for every retained root–orientation pair (r, θ), the component graph Kr,θ of the pruned tree is connected. The edge-minimum repair theorem then adds exactly c − 1 healthy crossing edges and returns a valid non-redundant broadcast tree over all healthy vertices. Algorithm 1 pins the original healthy source with all orientations in its mandatory fallback set, so at least one healthy retained candidate is evaluated even when the ranked top-K list is capped; hence it succeeds. For necessity, suppose G′ is disconnected. Then two healthy vertices lie in different connected components of the healthy graph. No tree using only healthy vertices and healthy links can span both vertices, so no broadcast repair method can succeed. Remark 4 (Candidate retention). The ranked/capped selector never removes the original source fallback. Algorithm 1 evaluates the union of the top-K ranked root–orientation pairs and the mandatory fallback set containing the original healthy source with all 15 orientations. Thus the cap can affect which high-ranked candidate wins the lexicographic score, but it cannot eliminate the existence of a successful retained candidate whenever G′ is connected. Corollary 4 (High-order recovery condition). The hybrid method fails to produce a repaired broadcast tree exactly when the healthy graph G′ = Ht − FV − FE is disconnected, or when an implementation deliberately evaluates no healthy candidate. Under adversarial fault placement, recovery is governed solely by healthy-graph connectivity: if the adversary’s fault set leaves G′ connected, the hybrid repair succeeds for that placement; if the adversary disconnects G′ , no broadcast method can succeed by the necessity direction of the healthy-graph connectivity theorem. The probability bound below therefore quantifies only the likelihood of random-placement local obstructions, not the existence of adversarial ones. 14
Figure 4: Healthy-graph connectivity is the exact recovery condition. If the healthy graph G′ = Ht −FV −FE remains connected, every selected pruned tree has a connected component graph and hybrid repair succeeds. If a healthy node is isolated by six faulty neighbours, G′ is disconnected and no broadcast tree can reach all healthy nodes. Theorem 4 (Deterministic single-link repair). Let FV = ∅ and let FE = {e} contain one failed EJ link. For any selected healthy root r and orientation θ, the hybrid repair phase succeeds. If e ∈ / E(Tr,θ ), zero repair edges are needed. If e ∈ E(Tr,θ ), exactly one repair edge is necessary and sufficient. Proof. If e is not a tree edge, pruning does not change the tree and no repair is needed. If e is a tree edge, deleting it splits Tr,θ into exactly two healthy components. By the nobridge lemma, deleting one EJ link does not disconnect the underlying healthy EJ graph. Therefore the two-component graph is connected. The edge-minimum repair theorem repairs it with c − 1 = 1 crossing edge. The component lower bound shows that one crossing edge is necessary. Corollary 5 (One-node/one-link bounded mixed case). If one node fault is placed on the boundary by re-rooting and one failed link is present, then the selected tree either avoids the failed link or the failed link creates a two-component residual cut that is repaired by one edge, provided the healthy graph remains connected. In particular, the node fault itself does not create an internal forwarding cut under the boundary-leaf condition.
10
Hybrid Re-Rooting and Repair Algorithm
The hybrid algorithm evaluates a bounded candidate set of root–orientation pairs. For node faults, the re-rooting theorem provides exact candidates for |FV | ≤ 2. For link-only or mixed cases, link-safety testing filters candidates; if no link-safe candidate is found, the algorithm selects the candidate that minimizes residual component repair.
15
Algorithm 1 EJ Hybrid Re-Rooting-Assisted Edge-Minimum Repair Require: Dense EJ network Ht , original source s, node faults FV , link faults FE , orientation family Θ. Ensure: Repaired non-redundant broadcast tree over V \ FV , or failure certificate. 1: Generate candidate roots R: exact boundary roots for |FV | ≤ 2; otherwise leaf-scoreranked roots; if the original source s is healthy, mark (s, θ) for every θ ∈ Θ as mandatory fallback pairs. 2: Rank candidate root–orientation pairs cheaply by leaf score L(r) and failed-tree-link count λ(r, θ, FE ). 3: Set best ← null. 4: for each pair in the union of the top-K ranked pairs and the mandatory fallback pairs do 5: Compute λ(r, θ, FE ) using the EJ link-exclusion test. 6: Prune Tr,θ by deleting FV and failed tree links in FE . 7: Compute components C1 , . . . , Cc and the component graph Kr,θ . 8: if Kr,θ is connected then 9: Add a component-level spanning tree and map it to c − 1 healthy EJ crossing edges, selecting for each newly attached component the crossing edge whose entry vertex in that component has minimum layer index. 10: Validate reachability, acyclicity, parent uniqueness, fault exclusion, and failed-link exclusion. 11: Score the candidate by (c − 1, Dr,θ , Mr,θ ) and update best if improved. 12: end if 13: end for 14: return best valid candidate, or a root-cause label if best is null. Example 4 (End-to-end hybrid execution, t = 3). Let s = 0, FV = {3}, and FE = {{12, 16}} in H4 (t = 3, N = 37). Avoid-only case. Root r = 28 gives ρ(∆28 (3)) = 3 = t, so node 3 is a boundary leaf. Under orientation C0 , Proposition 1 gives λ(28, C0 , FE ) = 0: neither endpoint of {12, 16} is the C0 -parent of the other relative to root 28. The pruned tree has c = 1 component and score (0, 3, 1). Residual-repair case. Keep root r = 0 and orientation C0 , but let the failed link be e′ = {12, 8}. Under the label convention above, labels 12 and 8 have coordinates (0, −3) and (0, −2), and pC0 (0, −3) = (0, −2), so e′ is a tree link and λ(0, C0 , {e′ }) = 1. Pruning detaches one component; the two-component graph is connected because no EJ link is a bridge. Algorithm 1 adds one shallowest-entry crossing edge and returns score (1, D0,C0 , 1) with D0,C0 ≤ 2t + 1 = 7 by Lemma 4. Remark 5 (Exact repair versus capped selection). For every fully repaired candidate (r, θ), the component theorem gives an exact c − 1 repair certificate if Kr,θ is connected. The implementation used in the validation run ranks many candidates cheaply and fully repairs the best 64 ranked root–orientation candidates plus the mandatory healthy-source fallback pairs. Therefore the reported hybrid selector is a ranked/capped engineering selector, not a proof that no untested root could have a better score. The fixed-source comparator in the validation run evaluates all 15 orientations exactly.
16
Theorem 5 (Hybrid correctness certificate). If Algorithm 1 returns a candidate for a selected pair (r, θ) whose component graph Kr,θ is connected, then the returned structure is a nonredundant broadcast tree over all healthy vertices, excludes every faulty node and failed link, uses exactly c − 1 external component-crossing repair edges for that selected pruned tree, and uses the minimum possible number of external crossing edges among all repairs that preserve the selected healthy components. Proof. The algorithm first deletes faulty nodes and failed tree links, so every retained internal component contains only healthy vertices and healthy tree edges. The connected component graph supplies a component-level spanning tree. Mapping each component-level edge to a healthy EJ crossing edge connects all healthy components without adding a failed edge. Since each original component is a tree and the component-level structure is also a tree, the expanded repaired structure is connected and acyclic. Rooting it at r gives one parent for every healthy non-root vertex and no parent for the root, so the result is a non-redundant broadcast tree. The number of added crossing edges is exactly the number of edges in the component-level spanning tree, namely c − 1, and the component lower bound proves that no repair preserving the same selected components can use fewer.
11
Runtime Micro-Re-Rooting Protocol
The transient model considered in this framework is a single link discovered during propagation. Suppose a node u attempts to forward to child v and detects that the link e = {u, v} is unavailable. Phase 1: observation. The detector records the failed link, the detection layer, and the current reached set. A conservative global recovery restarts the selection and repair process over the whole broadcast instance and therefore inherits all guarantees of Algorithm 1. A regional implementation can restrict the component scan to the subtree rooted at the detection point: only the descendants of the forwarding node u are re-scanned, the already delivered portion is treated as fixed, and the link-exclusion test and component repair are applied only to the affected subtree. The regional variant preserves the c − 1 repair optimality guarantee for the affected subtree because the component-repair theorem applies to any selected tree or subtree after its healthy components are contracted. The regional variant does not restart delivery to already reached nodes, so it is strictly less invasive than global recovery. Its correctness requires that no cycle be introduced at the junction between the delivered prefix and the re-routed suffix; this is enforced by keeping u as the unique attachment point of the re-routed descendants. Phase 2: candidate selection and link test. The candidate generator selects root– orientation pairs. For every candidate, the link-exclusion test determines whether e is used by the candidate tree. Candidates with λ = 0 are preferred; otherwise the algorithm keeps candidates with small component count and connected component graph. Phase 3: component repair. The selected tree is pruned, the healthy components are contracted, and a component-level spanning tree is mapped back to EJ repair edges. The recovered tree is then used to complete delivery. The graph-theoretic guarantee is identical to the static case once the failed link is included in FE . 17
12
Higher-Order Heuristic Regimes
For |FV | ≥ 3, a common distance-t root is not guaranteed. The hybrid method therefore uses a best-effort leaf score L(r) = |{f ∈ FV : dist(r, f ) = t}|.
(38)
Candidate roots are ranked by high L(r) and low failed-tree-link count λ(r, θ, FE ). By the healthy-graph connectivity theorem, success in the higher-order regime is governed by the connectivity of the healthy graph G′ = Ht − FV − FE . The heuristic component of Algorithm 1—leaf-score ranking, link-safety filtering, and the full-repair cap—controls which successful root–orientation pair is selected and therefore the repair-edge count and repaired depth. It does not create a new graph-theoretic recovery condition: a successful repaired tree exists for every fault set that leaves G′ connected, and no method can succeed when G′ is disconnected. Proposition 2 (Local obstruction). A set of six failed neighbors of a healthy EJ node isolates that node from the healthy graph. Likewise, the six incident links of a healthy EJ node isolate it as a singleton component. Hence no method can guarantee recovery for arbitrary high-order node or link faults without excluding such local cuts. Proof. Every EJ node has exactly six incident unit-direction links. If all six neighboring nodes fail, the central healthy node has no healthy neighbor. If all six incident links fail, the same node has no remaining incident healthy link. In either case, the healthy graph is disconnected, so no broadcast tree over all healthy nodes can exist. Proposition 3 (Local-obstruction probability scale). Let q node faults be sampled uniformly without replacement, and let Pt be any translated local obstruction family with at most CN patterns, each consisting of s specified vertices, where C and s are independent of t. Then q s . (39) Pr[∃P ∈ Pt : P ⊆ FV ] ≤ CN N For the six-neighbor isolating obstruction, s = 6, and since N = Θ(t2 ), the bound is O(q 6 /t10 ) for fixed q. Proof. For one fixed pattern P of size s, the probability that all its vertices are sampled is at most (q/N )s . A union bound over at most CN translated patterns gives the first inequality. Substituting N = 3t2 + 3t + 1 = Θ(t2 ) and s = 6 gives O(q 6 /t10 ). By the healthy-graph connectivity theorem, the theoretical success condition is connectivity of G′ , not a special property of the selected component graph. Proposition 3 applies to uniform random sampling and quantifies one important class of local obstructions. For nonuniform or clustered distributions, the bound degrades in proportion to how strongly faults concentrate around a single node neighborhood. For adversarial distributions, no probabilistic argument is needed for correctness: if the adversarial fault set leaves G′ connected, the hybrid repair succeeds for that placement; if it disconnects G′ , no broadcast method can succeed. 18
13
Experimental Evaluation
This section reports the validation campaign for the EJ hybrid framework. The experiment is graph-level and proof-auditing oriented: it tests reachability, component repair, failed-link exclusion, repair-edge count, repaired depth, selector settings, and root-cause labels across the regimes used in the paper. The theorem statements above do not depend on random sampling; the experiment validates the implementation and quantifies the structural benefit of re-rooting-assisted repair.
13.1
Experimental Settings
The validation used script for Python 3, NumPy, macOS, 10 workers, t ∈ {10, 25, 50, 100, 200}, 13 scenarios, four placement modes, and 1000 trials per exact setting. This gives 260,000 raw trials. The run used root cap 20000, full-repair-candidate cap 64, hybrid orientation cap 15, and fixed-source orientation cap 15. The elapsed time was 94.42 hours, with an average rate of 0.765 trials/s. The fixed-source comparator therefore remains the exact 15-orientation comparator, while the hybrid root search is a ranked/capped engineering selector. To address comparator and selector-breadth concerns, the artifact also includes a full postprocessed global-BFS rebuild audit over the same 260,000 trials and a targeted cap-sensitivity audit over the hardest higher-order stress settings.
13.2
Formal Fault-Placement Modes
The four placement modes are defined as follows. Let s = 0 be the original source, let ρs (v) = d(s, v), and let Ts,C0 denote the original source tree under orientation C0 . • Random: sample faulty nodes uniformly without replacement from V \ {s} and failed links uniformly from healthy EJ edges. • Near-source: sample faulty nodes from the inner ball {v : 1 ≤ ρs (v) ≤ max(1, ⌊t/5⌋)} when possible; failed links are sampled preferentially from original tree edges whose child layer is at most max(2, ⌊t/5⌋). • Critical: sample faulty nodes from internal ray/axis positions with 1 ≤ ρs (v) ≤ max(2, ⌊t/2⌋), where x = 0, y = 0, or x + y = 0. Failed links are sampled preferentially from original tree edges in the same internal layer range. These positions are not worst-case adversarial cuts; they are high-impact positions for the fixed source tree. • Close: choose a random healthy seed and then sample the remaining faults from its constant-radius EJ neighborhood by local breadth-first expansion. For two-fault instances this produces close-pair placements; for higher-order rows it produces clustered local stress tests. These definitions are distributional. They do not claim to cover every adversarial high-order cut; the high-order rows are explicitly empirical best-effort regimes.
19
13.3
Compared Methods
The main tables compare four implemented methods. Baseline no repair runs the original source tree and stops at faulty nodes or failed tree links. Avoid-only re-rooting succeeds only when the selected root–orientation tree already avoids all failed tree links and places node faults as non-forwarding boundary leaves, so no component repair edge is used. Fixed-source component repair keeps the source fixed at 0 and evaluates the 15 EJ orientations exactly. Hybrid repair ranks root–orientation candidates, fully repairs the best ranked candidates plus the mandatory healthy-source fallback, and returns the best successful repaired tree under the lexicographic score. A fifth external/general baseline is also reported: global BFS rebuild. This baseline deletes faulty nodes and failed links, runs BFS from the original source in the healthy EJ graph, and constructs a new shortest-path broadcast tree. It is not a local repair method and it does not preserve the damaged tree components. Its purpose is to show the tradeoff between global reachability/depth and the number of parent-pointer changes relative to the original broadcast tree. In the audit, BFS rebuild is applied to every validation row as an external graph-reconfiguration baseline.
13.4
Cap Sensitivity and Near-Miss Audits
The hybrid selector in the validation fully repairs the best 64 ranked pairs plus the mandatory healthy-source fallback pairs. This cap controls source-search breadth only; for every selected candidate, the component repair is still exact and uses c − 1 edges when the component graph is connected. To avoid making cap 64 look arbitrary, a targeted cap-sensitivity audit compares caps 16, 64, and 128 on the most stressful higher-order regimes: t ∈ {25, 50}, scenarios 3 nodes plus 2 links and 5 nodes, and critical/close placements. A near-miss audit also records cap pressure, maximum component count, maximum repair edges, maximum repaired-depth overhead, and the number of avoid-only failures recovered by component repair. Table 2: Recovery by claim regime. The run used 1000 trials per exact (t, scenario, mode) setting, 10 workers, exact 15-orientation fixed-source comparison, and a ranked hybrid repair cap of 64 fully repaired pairs plus mandatory source fallback pairs. Regime
Trials Baseline (%) Avoid-only (%) Fixed repair (%) Hybrid (%)
1–2 nodes 40,000 1 link 20,000 1 node + 1 link 20,000 1 node + multi-link 20,000 2-node mixed 40,000 multi-link 60,000 higher-order heuristic 40,000 transient 1 link 20,000
2.415 33.105 2.150 1.555 0.718 14.250 0.215 33.310
100.000 100.000 100.000 100.000 99.922 100.000 44.557 100.000
100.000 100.000 100.000 100.000 100.000 100.000 100.000 100.000
100.000 100.000 100.000 100.000 100.000 100.000 100.000 100.000
Hybrid failures 0 0 0 0 0 0 0 0
Table 2 gives the main claim-regime summary. The proposed hybrid method recovered every one of the 260,000 validation trials. The fixed-source component-repair comparator also recovered every trial in this run, but it used more external repair edges and produced 20
larger repaired depth. Avoid-only re-rooting was perfect in the deterministic one/two-node, single-link, one-node/link, and multi-link rows, but dropped in the higher-order heuristic row because a common boundary root is not guaranteed for five-node clustered placements. Table 3: Average external repair-edge reduction. Depth values are averaged over t ∈ {10, 25, 50, 100, 200} and the four placement modes. Rows with zero hybrid edges are theorem-backed deterministic regimes; the two higher-order rows are empirical stress regimes governed by healthy-graph connectivity. Scenario
Fixed edges
Hybrid edges
0.9651 2.0618 0.1096 0.2734 0.4485 0.8391 1.1279 1.3544 2.2365 2.4846 3.6117 5.3740 0.1052
0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0016 0.3838 1.3259 0.0000
1 node 2 nodes 1 link 2 links 3 links 5 links 1 node + 1 link 1 node + 2 links 2 nodes + 1 link 2 nodes + 2 links 3 nodes + 2 links 5 nodes transient 1 link
Reduction (%) Fixed depth 100.00 100.00 100.00 100.00 100.00 100.00 100.00 100.00 100.00 99.94 89.37 75.33 100.00
Hybrid depth
95.867 110.319 78.063 80.048 82.420 88.153 97.261 99.656 113.229 116.210 128.375 140.511 78.027
77.000 77.000 77.000 77.000 77.000 77.000 77.000 77.000 77.000 77.002 77.131 80.559 77.000
Rows 1–10 and the transient single-link row are theorem-backed by boundary re-rooting, link exclusion, and deterministic single-link repair; zero hybrid repair edges and depth 77.000 reflect the uniform diameter average t̄ = (10 + 25 + 50 + 100 + 200)/5 = 77 together with the deterministic-depth corollary. Rows 11–12 are higher-order empirical regimes; recovery is governed by the healthy-graph connectivity theorem and repair-edge count depends on the selected ranked/capped candidate.
Table 3 shows the main structural advantage of the hybrid method. In all deterministic one/two-node and link-only regimes, the hybrid selected a root/orientation with zero average external repair edges. In mixed two-node/two-link cases, the average repair count was only 0.0016, a 99.94% reduction from the exact fixed-source comparator. In higher-order regimes, the method remained effective but no longer zero-repair: three nodes plus two links required 0.3838 repair edges on average, and five-node cases required 1.3259 repair edges on average. These are the regimes where the paper states best-effort empirical recovery rather than a deterministic universal theorem. Table 4: Aggregate scaling by EJ diameter t across all tested scenarios and placement modes. t
Trials Baseline (%)
10 52,000 25 52,000 50 52,000 100 52,000 200 52,000
10.844 9.146 8.938 8.527 8.531
Avoid-only (%) Hybrid (%) 93.696 91.423 90.848 90.806 90.519
100.000 100.000 100.000 100.000 100.000
Fixed edges
Hybrid edges
Fixed depth
Hybrid depth
1.8134 1.6348 1.5692 1.5349 1.5213
0.0839 0.1272 0.1431 0.1489 0.1550
14.260 33.671 65.910 130.330 258.960
10.050 25.114 50.196 100.344 200.715
Table 4 aggregates by diameter. Across all tested scenarios, the hybrid success rate stayed 21
at 100% from t = 10 to t = 200. Average hybrid depth stayed close to the network diameter, whereas fixed-source repaired depth was much larger because a fixed source leaves faults on internal forwarding trunks. The average hybrid repair count remained below 0.16 even at t = 200 in this validation campaign. Table 5 compares the hybrid method with a global BFS rebuild baseline aggregated by claim regime. BFS rebuild is an intentionally strong external reachability/depth baseline: it succeeds whenever the healthy graph is connected and builds a shortest-path tree from the original source. Its cost is that it replaces the broadcast structure globally. The changedparent column is an upper-bound proxy for the number of parent rules that may differ from the original tree. Hybrid repair instead keeps healthy tree components and adds only a small number of component-crossing rules. Table 5: External global-BFS rebuild comparison on the same 260,000 validation rows. BFS rebuild restores reachability but may replace essentially the whole broadcast tree; hybrid repair preserves selected healthy components and adds few external crossing rules. Claim regime
Trials
One/two node Single link One node + one link One node + multi-link Multi-link Two-node mixed Higher-order heuristic Transient single link
40,000 20,000 20,000 20,000 60,000 40,000 40,000 20,000
BFS succ. (%) BFS depth 100.000 100.000 100.000 100.000 100.000 100.000 100.000 100.000
BFS parent-change proxy Hybrid edges
77.439 77.110 77.437 77.462 77.241 77.517 77.594 77.105
32,164.5 32,166.0 32,165.0 32,165.0 32,166.0 32,164.0 32,162.0 32,166.0
Hybrid depth
Fixed edges
77.000 77.000 77.000 77.000 77.000 77.001 78.845 77.000
1.513 0.110 1.128 1.354 0.520 2.361 4.493 0.105
0.000 0.000 0.000 0.000 0.000 0.001 0.855 0.000
Table 6: Reproducibility and selector settings. Item
Value
Raw trials Diameters Placement modes Workers used Root cap Hybrid full-repair cap Hybrid orientation cap Fixed-source orientation cap Hybrid failures Worker errors Elapsed time Rate
22
260,000 10, 25, 50, 100, 200 random, near, critical, close 10 20,000 64 15 15 0 0 94.42 h 0.765 trials/s
Table 7: Targeted cap-sensitivity audit on higher-order stress cases; 160 trial-units per cap. Cap Success (%) Avg. edges Depth ovh. Hits 16 64 128
100.000 100.000 100.000
0.5938 0.5938 0.5938
0.8375 0.7500 0.7500
2 0 0
Table 8: Near-miss audit aggregated by claim regime. Cap pressure means the selected run touched the full-repair cap proxy; it is not a hybrid failure. Claim regime
Trials Hybrid failures
One/two node Single link One node + one link One node + multi-link Multi-link Two-node mixed Higher-order heuristic Transient single link
40,000 20,000 20,000 20,000 60,000 40,000 40,000 20,000
Avoid-only fail, hybrid recovered
0 0 0 0 0 0 0 0
0 0 0 0 0 31 22,177 0
Max comp. Max repair 1 1 1 1 1 2 4 1
0 0 0 0 0 1 3 0
Max depth over t Cap pressure 0 0 0 0 0 25 174 0
0 0 0 0 0 0 19 0
The root-cause output file contained no hybrid failures. Thus no disconnected-component or relocation-failure breakdown appears in this validation campaign. The manuscript nevertheless keeps the theorem statements conditional for high-order regimes, because local six-neighbor or six-link isolating cuts make universal recovery impossible. The near-miss audit shows that the only meaningful cap-pressure events occur in the higher-order heuristic regime, while theorem-backed regimes remain zero-repair and zero-pressure in this dataset. The connectivity-threshold audit in Table 9 then tests the exact boundary condition of Theorem 3.
13.5
Connectivity-Threshold Audit
Table 9 tests the boundary condition of Theorem 3 directly. For each tested diameter t ∈ {10, 25, 50} and fault loading k, the healthy graph G′ = Ht − FV is checked by breadthfirst search after uniform random node faults are sampled. The two right columns record the fraction of trials where G′ is connected and the fraction of trials whose success is implied by Theorem 3. By Theorem 3, these two quantities are equal for every fault level and network size. The table validates the exact transition from high success at low fault loading to zero success when G′ becomes fully disconnected, with no exceptions in either direction across 3,000 trials. This audit checks G′ -connectivity directly and uses Theorem 3 to classify predicted recovery, so it does not require rerunning the full capped selector.
23
Table 9: Connectivity-threshold audit for uniform random node faults. The audit deliberately increases fault loading until the remaining healthy graph begins to disconnect. The two right columns are identical because Theorem 3 gives the exact recovery condition: predicted hybrid success is exactly the event that G′ is connected. t 10 10 10 10 10 25 25 25 25 25 50 50 50 50 50
13.6
N Node faults k Trials G′ connected (%) Theorem 3 predicted success (%) 331 331 331 331 331 1951 1951 1951 1951 1951 7651 7651 7651 7651 7651
40 80 100 120 140 200 400 500 600 800 500 1000 1500 2000 2500
200 200 200 200 200 200 200 200 200 200 200 200 200 200 200
100.0 94.5 86.0 53.0 13.5 100.0 84.5 62.0 24.5 0.0 100.0 96.0 62.5 7.5 0.0
100.0 94.5 86.0 53.0 13.5 100.0 84.5 62.0 24.5 0.0 100.0 96.0 62.5 7.5 0.0
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; in the exact validation, some two-fault cases select orientations with five components and therefore four repair edges. Third, although the proof guarantees depth t + 2 for all two-fault placements, the selected 15-orientation EJ-MOEM candidate is often stronger: 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.
14
Discussion
14.1
Why the Hybrid Objective Matters
The validation data show that fixed-source component repair can often recover the same trials, but it leaves substantially more fragmentation and larger depth. The hybrid method changes the tree before repair. A fault that is internal for the original source can become a boundary leaf for a re-rooted source, and a failed link used by one orientation can be avoided by another root–orientation pair. Thus the main structural benefit is not merely higher success, but lower exceptional repair state and shallower repaired trees.
24
14.2
Comparator Fairness
The fixed-source comparator evaluates all 15 EJ orientations, so it is an exact fixed-source 15orientation comparator. This is a strong internal ablation because it gives the fixed source the same orientation family and exact component-repair engine. The paper also includes global BFS rebuild as a general external graph-reconfiguration baseline. BFS rebuild has 100% success in the validation rows and near-diameter depth, but the parent-change proxy is on the order of N because the tree is rebuilt globally. The proposed method should therefore be judged on a different axis: it preserves healthy components of a selected diameter-level tree and minimizes the number of new component-crossing repair rules for that selected tree. For a NoC implementation, each component-crossing repair edge corresponds to one exceptional forwarding rule inserted at a component boundary node. The median hybrid repair-edge count is zero in all theorem-backed deterministic regimes, so the common case requires no additional routing-table entries beyond activating the selected root–orientation tree. In higher-order regimes, the five-node row averages 1.3259 repair edges in the current 260,000-trial dataset, meaning fewer than two additional component-boundary forwarding entries per broadcast instance on average. This contrasts with global BFS rebuild, whose parent-change proxy is O(N ) and would require changing a large fraction of the broadcast parent map. From a latency perspective, each component-crossing repair edge represents one additional forwarding hop at a component boundary. In the median case, the theorem-backed deterministic regimes have zero repair edges, so the repaired broadcast latency equals the original diameter-t broadcast. In the higher-order five-node row, the average repair count is 1.3259; even if each repair edge is charged as one additional hop, this is less than two extra hops on average and below 1% of the t = 200 diameter scale. This is a structural latency metric, not a substitute for a full cycle-accurate NoC throughput evaluation. Deadlock freedom follows from the repaired structure being a tree. The fault-free broadcast tree has no cyclic channel dependency because every packet follows an acyclic parent– child structure. Each component-crossing repair edge is directed from a parent-side component to a child-side component and is used once per broadcast event. Since the componentlevel repair is also a tree, adding these directed crossings cannot create a cycle in the broadcast dependency graph. Thus the repaired broadcast inherits deadlock freedom from acyclicity, independent of the underlying unicast routing protocol used outside this scheduled broadcast. The hybrid selector uses a ranked/capped root search: it cheaply ranks many root– orientation pairs and fully repairs the best 64 ranked pairs together with the mandatory healthy-source fallback pairs in the main validation table. In theorem-backed one/two-node regimes, the root cap is non-binding: exact boundary generation returns at most 6t roots per fault, and 6t · 15 = 90t ≤ 18000 orientation candidates at t = 200, below the root cap of 20000. At least one boundary-root candidate exists by the re-rooting theorem, and it is lexicographically optimal when it produces zero repair edges. For higher-order regimes, the cap is an engineering selector. The cap is reported explicitly in Table 6, and the capsensitivity audit in Table 7 shows that cap 64 matches cap 128 in success and average repair-edge count on the audited stress cases, with zero cap hits for both settings. The paper therefore claims exact repair optimality for every fully repaired selected candidate, 25
not global optimality over all possible roots.
14.3
Limits and Reviewer-Safe Claims
The deterministic claims are: one/two-node boundary re-rooting exists; one failed link is always avoided or repaired by at most one crossing edge for any selected tree; and connected component graphs are repaired with exactly c − 1 edges. The empirical claim is: under the tested distributions and cap settings, the hybrid method recovered all 260,000 trials and reduced repair edges substantially compared with fixed-source repair. The paper does not claim universal high-order recovery.
14.4
Threats to Validity
The validation is graph-level rather than a full router microarchitectural study. It measures broadcast reachability, component repair, repair-edge count, and repaired depth, but it does not claim saturation throughput, calibrated power, virtual-channel behavior, or backgroundtraffic performance. A cycle-accurate EJ NoC implementation and background-traffic evaluation are outside the scope of this paper; the present validation targets graph-level correctness, repair-edge optimality, and forwarding-state reduction. The hybrid root search is capped, so the reported hybrid candidate is the best among the fully repaired ranked candidates rather than a global optimum over all roots. These limitations do not affect the deterministic theorems: they affect only the interpretation of empirical high-order and performance-oriented claims.
15
Complexity
Let N = 3t2 + 3t + 1, let m = |E| = 3N because the EJ graph has degree six, let qV = |FV |, and let qE = |FE |. For a fixed root–orientation pair (r, θ), failed-link exclusion costs O(qE ) by Proposition 1. If full repair is invoked, pruning, component identification, componentgraph construction, shallowest-entry crossing selection, and repaired-depth validation cost O(N + m) = O(N ) because the degree is constant. The cheap-ranking phase evaluates R ≤ 20000 candidate roots with Q ≤ 15 orientations. The leaf score L(r) costs O(qV ) through the EJ distance formula, and the failed-tree-link count costs O(qE ) per orientation. Thus the cheap-ranking cost is O R qV + QqE . (40) The full-repair phase evaluates K ≤ 64 root candidates and Qf ≤ 15 orientations at cost O(N ) per orientation, giving O(KQf N ). (41) At t = 200 and qV = qE = 5, cheap ranking costs on the order of 20000(5 + 15 · 5) ≈ 1.6 × 106 primitive coordinate checks, while full repair costs up to 64 · 15 · 120601 ≈ 1.16 × 108 vertexlevel operations. Full repair is therefore the dominant validation cost. The exact fixed-source comparator costs O(15N ) per trial; the global-BFS rebuild baseline costs O(N ) but replaces 26
O(N ) parent pointers, whereas the hybrid repair changes only O(c − 1) component-crossing entries for the selected tree. For |FV | ≥ 3, candidate roots are ranked over at most N − 1 healthy nodes. A full sort costs O(N log N ) time and O(N ) space, but only the top R = 20000 candidates are retained; a heap-select implementation costs O(N + R log N ) time and O(R) space. At t = 200, R log2 N ≈ 20000 · 17 = 340000 comparisons, dominated by the full-repair phase. The retained candidate list requires R⌈log2 N ⌉ ≈ 340000 bits, about 42 KB. For an online implementation with precomputed tables, the common bounded-fault case is much smaller than the offline audit. For |FV | ≤ 2 and |FE | ≤ 2 at t = 200, exact boundary generation produces at most 6t = 1200 root offsets per fault, and the link-exclusion check costs O(|FE |) parent comparisons per candidate. A selected candidate needs one O(N ) component pass only when a residual cut remains. A conservative operation count is therefore about 1200 · 4 + 120601 ≈ 1.25 × 105 primitive operations, or roughly 125 µs at a 1 ns operation budget. This is an order-of-magnitude software-defined reconfiguration estimate, not a cycle-accurate router claim. The 94.42-hour runtime reported in Table 6 is an offline validation/proof-auditing cost over 260,000 trials with exact fixed-source comparison; it is not a per-broadcast NoC latency [3, 15]. The dominant precomputed storage is the orientation parent table. Absolute parent labels require 15N ⌈log2 N ⌉ bits. At t = 200, N = 120601 and ⌈log2 N ⌉ = 17, giving about 30.75 Mbits, or 3.84 MB. Direction-offset encoding stores each parent as one of six directions and requires 15N ⌈log2 6⌉ bits, about 0.68 MB at t = 200. Centralized in a dedicated faultmanagement unit, this is a modest global table. If distributed, each router tile need only store its own parent direction for each of the 15 orientations, requiring 15⌈log2 6⌉ ≈ 45 bits per tile, not the full table. Boundary candidate tables are O(t) and link-exclusion uses no large table.
16
Data and Reproducibility
The validation drivers emit 260,000 raw trials, repair-edge summaries, timing data, rootcause logs, full-BFS rebuild audits over all raw rows, near-miss audits, cap-sensitivity summaries, and connectivity-threshold tables as CSV/JSON files and package them into ZIP archives. The archive records all reproduction settings, including root cap, full-repair cap, orientation caps, worker count, placement modes, and random seed.
17
Conclusion
This paper introduced a re-rooting-assisted edge-minimum runtime repair framework for dense EJ broadcast networks under node faults, link faults, mixed faults, and runtimediscovered single-link faults. The central object is the selected triple (r, θ, Kr,θ ). EJ boundary re-rooting supplies deterministic one/two-node source relocation, EJ link exclusion gives a constant-time failed-link test, and component repair gives the exact c − 1 edge-minimum certificate whenever the component graph is connected. Theorem 3 establishes the necessary and sufficient recovery condition across all fault orders: the method
27
succeeds exactly when the healthy EJ graph G′ = Ht − FV − FE is connected. Lemma 4 gives Dr,θ ≤ 2t + 1 under the shallowest-layer entry rule enforced in Algorithm 1. The 260,000-trial validation campaign shows 100% hybrid recovery and strong repair-edge reduction compared with exact fixed-source 15-orientation repair. The BFS rebuild, nearmiss, cap-sensitivity, and connectivity-threshold audits clarify the tradeoff between reachability, forwarding-state changes, selector pressure, and the exact boundary condition of Theorem 3. The artifact workflow regenerates all tables from raw CSV outputs without changing the theory or manuscript structure.
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, 1989. [2] F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann, 1992. [3] W. J. Dally and B. Towles, Principles and Practices of Interconnection Networks. Morgan Kaufmann, 2004. [4] J. Duato, S. Yalamanchili, and L. Ni, Interconnection Networks: An Engineering Approach. Morgan Kaufmann, 2003. [5] A. Grama, A. Gupta, G. Karypis, and V. Kumar, Introduction to Parallel Computing, 2nd ed. Addison-Wesley, 2003. [6] 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, 1990. [7] D. D. Kandlur and K. G. Shin, “Reliable broadcast algorithms for HARTS,” ACM Transactions on Computer Systems, vol. 9, no. 4, pp. 374–398, 1991. [8] 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, 2010. [9] C. Martinez, 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. [10] 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, 2012. [11] D. Peleg and A. A. Schäffer, “Time bounds on fault-tolerant broadcasting,” Networks, vol. 19, no. 7, pp. 803–822, 1989. 28
[12] V. Hadzilacos and S. Toueg, “A modular approach to fault-tolerant broadcasts and related problems,” Technical Report TR94-1425, Cornell University, 1994. [13] T. C. Lee and J. P. Hayes, “Routing and broadcasting in faulty hypercube computers,” in Proc. Third Conference on Hypercube Concurrent Computers and Applications, 1988, pp. 346–354. [14] B. Cheng, D. Wang, and J. Fan, “Independent spanning trees in networks: A survey,” ACM Computing Surveys, vol. 55, no. 14s, Article 335, 2023. [15] 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. [16] S. Pasricha and N. Dutt, On-Chip Communication Architectures: System on Chip Interconnect. Morgan Kaufmann, 2008. [17] J. Flich and D. Bertozzi, Designing Network-on-Chip Architectures in the Nanoscale Era. CRC Press, 2010. [18] P. Stroobant, S. Abadal, W. Tavernier, E. Alarcón, D. Colle, and M. Pickavet, “A general, fault tolerant, adaptive, deadlock-free routing protocol for Network-on-Chip,” arXiv:1811.11262, 2018. [19] B. A. Albader, “Re-rooting-based fault-tolerant one-to-all broadcasting in dense Eisenstein–Jacobi networks,” preprint available from the author upon request, 2026. [20] B. A. Albader, “Multi-orientation edge-minimum repair for non-redundant fault-tolerant broadcasting in dense Eisenstein–Jacobi networks,” preprint available from the author upon request, 2026.
29