Keywords: Dense Gaussian networks, fault-tolerant broadcasting, link failures, node failures, re-rooting, component repair, Network-on-Chip, interconnection networks, edge-minimum repair, transient recovery.

1 Introduction↩︎

One-to-all broadcast is a core collective operation in parallel processors, many-core systems, NoC fabrics, and distributed accelerators. It is used for synchronization, coherence messages, configuration updates, and control dissemination. A broadcast primitive in a low-degree topology should have small depth, avoid duplicate traffic, use simple forwarding state, and tolerate faults without global rebuilding after every small failure.

Dense Gaussian networks provide an algebraic topology in which this problem can be studied with explicit coordinate structure. For parameter \(k\), the dense Gaussian network generated by \(k+(k+1)i\) has \[N=k^2+(k+1)^2=2k^2+2k+1\] nodes, degree four, and diameter \(k\). Its canonical coordinate model identifies the vertices with the Manhattan ball \[B_k=\{(x,y)\in\mathbb{Z}^2: |x|+|y|\le k\}\] through the integer label \[\phi(x+yi)\equiv kx+(k+1)y \pmod N.\] This model supports deterministic source-centered broadcast trees of depth at most \(k\).

Prior static re-rooting work shows that one and two failed nodes can be neutralized by relocating the source to a node at distance \(k\) from each failed node. Such faults become leaves of the broadcast tree and do not forward packets. Prior component-repair work shows that if a fault-pruned tree breaks into \(c\) healthy components and the component graph is connected, then \(c-1\) component-crossing repair edges are both necessary and sufficient. These results are useful, but neither alone solves runtime node/link failures. Re-rooting by itself does not repair residual failed tree links or high-order fault cuts. Component repair by itself can succeed from a fixed source but may require many repair edges if the fixed source leaves faults on major trunks.

This paper addresses the missing problem: runtime node/link broadcast recovery by re-rooting first and repairing only the residual damage. The intellectual point is not a mechanical juxtaposition of two earlier techniques. The paper develops a new link-failure exclusion condition, a runtime micro-re-rooting protocol, a candidate-generation/selection interface, a root-cause analysis for non-perfect high-order recovery, and a quantitative repair-edge reduction study against fixed-source component repair. The combination changes the optimization objective: the selected root is not merely a valid source, but a damage-minimizing source that reduces the number of healthy components before the edge-minimum repair phase is invoked.

1.1 Contributions↩︎

The contributions are as follows.

• We formulate joint node/link fault-tolerant broadcasting in dense Gaussian networks as re-rooting-assisted component repair, covering static node/link faults, mixed faults, and runtime-discovered single-link faults.

• We give a self-contained re-rooting primitive with the one/two node guarantee and a constant-size \(9\times16\) shifted sign-case candidate generator for two-node source selection.

• We introduce a link-failure exclusion test and prove an edge-minimum component-repair theorem: if the healthy component graph is connected after pruning, exactly \(c-1\) component-crossing repair edges are necessary and sufficient.

• We prove deterministic single-link repair and a high-order threshold result: one failed link is always avoided or repaired by one crossing edge, while three-node zero-repair re-rooting is governed by a triple boundary-intersection condition.

• We add deterministic component-count and repair-edge bounds, distinguish repair state from repaired hop depth, and provide a local-obstruction probability bound explaining why fixed-size high-order cuts become rare as \(k\) increases.

• We evaluate 280,000 static trials and 15,000 transient trials up to 80,401 nodes, reporting success rates, candidate overhead, repair-edge reduction, transient discovery layer, and a complete root-cause breakdown of all non-recovered cases.

• We validate the NoC interpretation using documented patched native Gaussian-link Noxim scheduled replays, a \(k=25\) completion-cycle audit with zero-setup and latency-objective ablations, and a \(k=50\) full-root-scan sanity check.

1.2 Scope and Relationship to Related Manuscripts↩︎

The present paper is self-contained: every theorem, selection rule, and repair procedure used in the experiments is stated here. Static node-failure re-rooting and multi-orientation component repair are discussed as related foundations, but the present contribution is the link/runtime hybrid framework and its analysis. In particular, the present paper studies failed links, runtime discovery, link-safety filtering, repair-edge reduction after re-rooting, and root-cause analysis of high-order failures; these are not consequences of either static re-rooting alone or fixed-source component repair alone. The companion-style references are therefore contextual rather than logical prerequisites for the correctness claims made here.

Table ¿tbl:tab:novelty95separation? makes this separation explicit. The present paper’s new unit of analysis is the pair \[(r,\mathcal{H}_r),\] namely the selected root together with the component graph induced after node and link pruning. The optimization is therefore not only to find a valid root or to repair a fixed tree, but to choose a root that makes the residual component graph small and repairable.

max width=

2 Related Work↩︎

Algebraic interconnection networks use group or ring structure to obtain symmetry, small routing tables, and concise path descriptions. Akers and Krishnamurthy introduced a group-theoretic view of symmetric interconnection networks [1]. Classical texts describe meshes, tori, hypercubes, Cayley graphs, collective communication, deadlock-free routing, and fault tolerance in interconnection networks [2]–[5]. Dense Gaussian networks belong to this tradition: they are degree-four quotient networks over Gaussian integers with small diameter and coordinate-based routing.

Gaussian and circulant-based topologies have been studied for routing, resource placement, Hamiltonicity, and NoC suitability. Martinez et al. studied dense Gaussian networks as low-degree on-chip multiprocessor topologies [6] and modeled toroidal networks using Gaussian integers [7]. Flahive and Bose studied Gaussian and Eisenstein–Jacobi interconnection networks [8]. Additional work considered routing and path structures in dense Gaussian and optimal degree-four circulant networks [9]–[11]. Edge-disjoint Hamiltonian cycles in Gaussian networks provide another form of path diversity [12].

Fault-tolerant broadcasting and reliable communication have often been addressed using independent spanning trees, completely independent spanning trees, redundant paths, or adaptive routing. Independent spanning trees provide internally disjoint delivery structures and are widely used as a protection mechanism in vertex- or edge-fault settings [13]–[15]. Related tree-diversity approaches are attractive when steady-state redundancy is acceptable: the system maintains multiple delivery structures and switches traffic after a fault. The present paper targets a different point in the design space. It keeps one deterministic delivery tree in the fault-free case and pays only for the exceptional component-crossing rules needed after faults are observed. In NoC systems, fault tolerance has been studied using adaptive routing, spare links, region avoidance, reconfiguration, and application mapping [16]–[19]. Such methods typically optimize packet routing, traffic distribution, or application placement. The present method differs by preserving a non-redundant broadcast objective: every healthy node receives the message once, and the recovery cost is measured by the number of external component-crossing repair edges.

The nearest same-objective line is local repair of a pruned broadcast tree. Rather than maintaining multiple complete trees in advance, the method studied here starts from one deterministic Gaussian broadcast tree, relocates the root to reduce fault damage, and then repairs the remaining components using the minimum possible number of external repair edges under the selected root. This gives a different tradeoff from independent spanning-tree protection: lower steady-state redundancy and very small repair-edge counts in common bounded-fault regimes, but no universal deterministic guarantee for arbitrary high-order clustered faults.

3 Dense Gaussian Model and Broadcast Tree↩︎

Let \(G_k=(V,E)\) be the dense Gaussian network with \[V=\mathbb{Z}_N,\qquad N=k^2+(k+1)^2.\] Two vertices \(u,v\in V\) are adjacent if \[v-u\equiv \pm k \quad\text{or}\quad v-u\equiv \pm(k+1) \pmod N.\] The coordinate map \(\phi(x+yi)\equiv kx+(k+1)y\pmod N\) maps the Manhattan ball \(B_k\) bijectively onto \(V\). Unit moves in the \(x\) and \(y\) directions correspond to the two generators \(k\) and \(k+1\).

For a root \(r\), define \(\Delta_r(v)=\operatorname{mod}_{G_k}(v-r)\) as the canonical coordinate difference from \(r\) to \(v\). A deterministic broadcast tree \(T_r\) is formed by assigning each non-root node a parent that decreases \(|x|+|y|\) by one in the coordinate difference. In the implementation used for the experiments, ties reduce the larger absolute coordinate first: \[p(x,y)= \begin{cases} (x-\operatorname{sgn}(x),y), & |x|\ge |y|,~x\ne0,\\ (x,y-\operatorname{sgn}(y)), & \text{otherwise.} \end{cases}\] The parent of \(v\) is \(r+\phi(p(x,y))\) modulo \(N\).

Lemma 1 (Fault-free tree). Every parent rule that decreases \(|x|+|y|\) by one at each non-root node induces a spanning tree of \(G_k\) rooted at \(r\) with depth at most \(k\).

Proof. Every non-root node has one parent adjacent in \(G_k\), and the layer \(|x|+|y|\) decreases by one. Repeated parent application reaches the root; hence directed cycles are impossible and every node is connected to the root. Since all canonical coordinates satisfy \(|x|+|y|\le k\), the maximum depth is at most \(k\).\(\square\)

Figure 1 shows \(B_3\) explicitly. Each node \((x,y)\) has exactly four Gaussian neighbors obtained by unit moves in the \(x\) and \(y\) directions, corresponding to adding or subtracting generator \(k\) or \(k+1\) modulo \(N\). The tree assigns each non-root node the parent that reduces \(|x|+|y|\) by one using the rule above. Boundary nodes at layer \(k\) are leaves; this is the geometric basis for re-rooting.

3.1 Recovery Objective↩︎

Given a source \(s\), node-fault set \(F_V\), and link-fault set \(F_E\), the recovery algorithm may select a root \(r\) and a repaired tree \(\widehat{T}_r\). The primary correctness objective is \[V(\widehat{T}_r)=V\setminus F_V,\qquad E(\widehat{T}_r)\cap F_E=\emptyset,\] with exactly one parent for each healthy non-root vertex. The recovery objective has two forms. The experiments use the lexicographic score \[\min (\rho_r, D_r, M_r),\] where \(\rho_r\) is the number of external component-crossing repair edges, \(D_r\) is the repaired depth, and \(M_r\) is the number of candidate roots inspected. This ordering is appropriate for the control-state-sensitive setting studied here, because each repair edge creates an exceptional forwarding rule while small depth changes are already reported separately. It is a design choice, not a universal NoC objective: the paper prioritizes minimizing exceptional forwarding state and then reports depth separately. A latency-dominant implementation can instead use the weighted score \[J_{\alpha,\beta,\gamma}(r)=\alpha \rho_r+\beta(D_r-k)+\gamma M_r,\] with \(\beta>\alpha\) when hop latency dominates routing-state cost. Thus the lexicographic rule is one operating point in a family of state/latency tradeoffs. All tables therefore report both repair-edge count and depth so that another weighting can be applied without rerunning the correctness test.

3.2 Fault Model↩︎

Node faults are denoted by \(F_V\subseteq V\) and link faults by \(F_E\subseteq E\). The original source is assumed healthy. A valid recovered broadcast must reach every vertex in \(V\setminus F_V\) without using failed nodes or failed links. A link fault may be static, known before broadcast begins, or transient, discovered when a router attempts to forward across a failed neighbor. The evaluated transient model is deliberately limited to one runtime-discovered link fault followed by one recovery episode; transient node failures, cascading faults, and sequential multi-link discoveries are outside the evaluated scope and are listed as future work. Throughout the paper, re-rooting denotes selecting a new effective broadcast source, while relocation denotes the control movement or notification cost needed to activate that source.

Given a root \(r\), pruning removes all faulty nodes, all tree edges incident to faulty nodes, and all failed tree links: \[T_r^- = T_r - F_V- F_E.\] Let \(\mathcal{C}_r=\{C_1,\ldots,C_c\}\) be the connected components of \(T_r^-\). The healthy component graph \(\mathcal{H}_r\) has one vertex for each \(C_i\) and an edge \(C_iC_j\) if there exists a healthy Gaussian edge in \(G_k-F_V-F_E\) with endpoints in \(C_i\) and \(C_j\).

4 Re-Rooting Preliminaries↩︎

For node failures, the re-rooting goal is to choose a source \(r\) satisfying \[\operatorname{dist}(r,f)=k\qquad \forall f\in F_V.\] Distance-\(k\) vertices are leaves of a diameter-level broadcast tree, so they do not forward.

Theorem 1 (Boundary intersection non-emptiness). For any two distinct nodes \(a,b\in V(G_k)\), the set \[I(a,b)=\{r\in V:\operatorname{dist}(r,a)=k \text{ and } \operatorname{dist}(r,b)=k\}\] is nonempty. Moreover, \(I(a,b)\) has at least two candidates for all non-degenerate fault pairs; in the finitely many degenerate tangent configurations it has exactly one candidate, which remains sufficient for Corollary 1.

Proof. By vertex transitivity it is enough to translate \(a\) to the origin and write \(C=b-a\) in canonical coordinates. A root \(r\) is valid exactly when its offset \(P=r-a\) satisfies \[P\in \partial B_k,\qquad P-C\in \partial B_k\] in one of the quotient copies of the coordinate ball. Equivalently, \(C\) must be expressible as a difference of two boundary points of the quotient ball. The dense Gaussian quotient has lattice generators \((k,k+1)\) and \((-(k+1),k)\). Hence it is sufficient to inspect the central copy and the eight adjacent copies, i.e., shifts \(m(k,k+1)+n(-(k+1),k)\) for \(m,n\in\{-1,0,1\}\). On each shifted copy, the equations \[|p|+|q|=k, \qquad |p-c'|+|q-d'|=k\] are the intersection equations for two Manhattan diamonds. Removing absolute values gives the sixteen signed systems in Section 5. The side-pair cases are exhaustive because every boundary point lies on one of four sides and every shifted copy contributes four translated sides. If the two sides are nonparallel, the signed linear system has one candidate; if they are parallel, the intersection is either empty or an interval endpoint is obtained by the same side inequalities. The dense quotient identity \(\partial B_k-\partial B_k=B_k\) follows from this finite side-pair enumeration: every canonical difference \(C\in B_k\) appears in at least one of the nine shifted side pairs, guaranteeing that \(I(a,b)\) is nonempty.

For the “at least two candidates” claim, three intersection cases arise for a given shifted side pair. Case 1 is nonparallel sides with transverse crossing. The two signed linear systems have determinant nonzero and the solution \((p,q)\) lies in the interior of both boundary sides. The opposite sign choice \((-s_1,-s_2,s_3,s_4)\) or \((s_1,s_2,-s_3,-s_4)\) yields a second solution symmetric about the side midpoint. These two solutions are distinct because \(C\ne0\) prevents the symmetric point from coinciding with the original.

Case 2 is parallel sides with interval intersection. The two boundary sides are parallel and their overlap is a line segment. The two endpoints of this segment are distinct candidates whenever the overlap has positive length. Zero-length overlap means that the sides are tangent at one point; this is the degenerate case.

Case 3 is tangent intersection. Tangency occurs when \(C\) lies exactly on a boundary side of a shifted copy with the same slope as that side, so the two diamonds meet at exactly one point. In this case both sign orientations yield the same candidate. There is therefore one valid candidate, not two.

Cases 1 and 2 with positive-length overlap yield at least two candidates. Case 3 yields exactly one. Since Case 3 occurs only on a finite set of boundary configurations defined by the nine shifted boundary sides, it is a degenerate condition. Thus \(I(a,b)\) is nonempty for all nonzero canonical differences, and it has at least two candidates except in the finitely many degenerate tangent configurations.\(\square\)

Corollary 1 (One/two node re-rooting primitive). For every one- or two-node fault set \(F_V\) in \(G_k\), there exists a root \(r\) such that \(\operatorname{dist}(r,f)=k\) for all \(f\in F_V\).

Proof. For one fault, choose any boundary vertex of the failed node. For two faults \(a,b\), apply Theorem 1 and select any \(r\in I(a,b)\).\(\square\)

Corollary 2 (Zero-repair node cases). If \(|F_V|\le2\), \(F_E=\emptyset\), and \(r\) satisfies \(\operatorname{dist}(r,f)=k\) for every failed node, then \(T_r^-\) has one healthy component and requires zero repair edges.

Proof. The failed nodes are leaves in \(T_r\). Removing leaves cannot disconnect healthy internal forwarding nodes from \(r\). Thus \(c=1\).\(\square\)

Example 1 (zero-repair re-rooting). Consider \(k=3\) with failed nodes at \((2,1)\) and \((-1,2)\). With the original source at \((0,0)\), both faults may appear on forwarding branches. Re-rooting to the illustrated source moves those faults to the boundary of the new broadcast tree, where they act as leaves. The pruned tree remains connected, so zero external repair edges are required. Figure 3 gives the core intuition in a small worked example.

5 Constant-Size Candidate Generation↩︎

This section gives the compact candidate-generation primitive used as the hardware-oriented selector. It is included so the present paper is not dependent on a separate constant-time selector manuscript.

Let \(C=(c,d)=\operatorname{mod}_{G_k}(b-a)\) be the reduced difference of two failed nodes. A valid offset \(P=(p,q)\) satisfies \[|p|+|q|=k, \qquad |p-c'|+|q-d'|=k, \label{eq:shiftedabs}\tag{1}\] for some quotient-lattice shift \[(c',d')=(c,d)+m(k,k+1)+n(-(k+1),k),\] where \(m,n\in\{-1,0,1\}\). The nine shifts cover the central copy and the eight adjacent quotient copies that can intersect the canonical boundary.

For each shift, remove the absolute values in 1 by choosing signs \[(s_1,s_2,s_3,s_4)\in\{\pm1\}^4.\] The signed system is \[s_1p+s_2q=k, \qquad s_3p+s_4q=k+s_3c'+s_4d'. \label{eq:signsystem}\tag{2}\] When the determinant is nonzero, Cramer’s rule gives one candidate. When the equations are parallel, the valid candidates form an interval on a boundary side, and an endpoint can be selected. Hence at most \(9\times16=144\) signed systems are checked.

Lemma 2 (Constant-size two-node generator). Under the standard word-RAM model for coordinate arithmetic, the shifted sign-case procedure returns a valid two-node re-rooting candidate in \(O(1)\) arithmetic cases.

Proof. The number of quotient shifts is nine and the number of sign tuples per shift is sixteen. Each nonparallel case requires constant arithmetic; each parallel case requires constant interval endpoint checks. Existence follows from the boundary-intersection theorem in Section 4.\(\square\)

5.1 Selector Used in the Experiments↩︎

The validation code intentionally separates the mathematical selector from implementation choices. For one and two node faults, the experiments used exact boundary-intersection enumeration of the \(4k\) boundary candidates rather than the compressed \(144\)-case selector. This makes the reported recovery independent of any possible implementation bias in the constant-size selector; the constant-size selector is included as the deployable primitive, while enumeration is used as a conservative validator. This gives \(O(k)\) candidate generation for the node-guaranteed cases. For three or more node faults, candidates are ranked by the number of failed nodes placed at distance \(k\). For link-only cases, candidate roots are tried in a deterministic pseudo-random order with a cap of 20,000 roots in the full run; this cap is used only for the avoid-only selector. The hybrid repair still prunes and repairs the selected tree even when no perfectly link-avoiding root is found. Link-safety testing for a candidate \(r\) costs \(O(|F_E|)\) because each failed link \(e=(u,v)\) is checked by testing whether the parent of \(u\) is \(v\) or the parent of \(v\) is \(u\) in \(T_r\).

Thus the experimental source-selection cost is explicitly \[O(M(|F_V|+|F_E|)),\] where \(M\) is the number of candidate roots checked. For one/two node faults, \(M\le4k\); for full-run link-only avoidance, \(M\le20{,}000\); for the constant-size selector, \(M\le144\). The component-repair phase scans the \(N\) nodes and their four Gaussian neighbors, giving \(O(N)\) time for a fixed selected root. No experimental setting uses an \(O(N^2)\) repair step.

5.2 Constant-Size Selector Cross-Validation↩︎

The constant-size selector and the \(O(k)\) boundary enumeration are allowed to return different roots; the correctness requirement is that the returned root satisfy the same distance-\(k\) predicate. To close the implementation gap between the hardware-oriented primitive and the conservative validator, the selector was cross-checked against exact boundary enumeration on the same one- and two-node instances used in the full run. Table 2 reports zero misses and zero invalid roots. Thus the experimental use of enumeration does not hide a correctness problem in the constant-size primitive; enumeration was used to make the validation independent of sign-case implementation details.

5.3 Link-Safety Candidate Structure↩︎

For node faults, the boundary-intersection structure reduces candidate search to a constant number of shifted side cases. An analogous reduction for link faults would require characterizing all roots \(r\) for which \(\lambda(r,F_E)=0\), that is, roots whose broadcast tree avoids every failed link. A failed link \(e=(u,v)\) is avoided by \(T_r\) if and only if neither \(u\) is the parent of \(v\) nor \(v\) is the parent of \(u\) under the coordinate rule rooted at \(r\). The parent relation depends on the two relative coordinates \(\Delta_r(u)\) and \(\Delta_r(v)\) simultaneously, so the resulting constraint is a region in root-coordinate space rather than a single boundary-distance equation. It does not decompose as cleanly as the distance-\(k\) node-fault condition.

Proposition 3 (Link-avoidance exclusion condition). Let \(e=\{u,v\}\) be a failed Gaussian link and let \(r\) be a candidate root. Write \[\Delta_r(w)=\operatorname{mod}_{G_k}(w-r)\] for the canonical coordinate of node \(w\) relative to root \(r\), and let \(p(\cdot)\) be the coordinate parent rule in (7). Then \(T_r\) uses the failed link \(e\) if and only if \[\Delta_r(u)=p(\Delta_r(v)) \quad\text{or}\quad \Delta_r(v)=p(\Delta_r(u)). \label{eq:link95exclusion}\tag{3}\] Equivalently, if \(\Delta_r(v)=(x,y)\), the first equality in (3 ) holds exactly when one of the following parent-reduction cases holds: \[\begin{align} \Delta_r(u)&=(x-\operatorname{sgn}(x),y), && |x|\ge |y|,~x\ne0,\tag{4}\\ \Delta_r(u)&=(x,y-\operatorname{sgn}(y)), && \text{otherwise and }y\ne0.\tag{5} \end{align}\] The two symmetric cases are obtained by exchanging \(u\) and \(v\).

Proof. By definition, the broadcast tree rooted at \(r\) assigns each non-root vertex \(w\) the parent whose coordinate is \(p(\Delta_r(w))\). Since \(\phi\) is a bijection from the coordinate ball to the vertex set, the parent of \(v\) is \(u\) if and only if \(\Delta_r(u)=p(\Delta_r(v))\). Similarly, the parent of \(u\) is \(v\) if and only if \(\Delta_r(v)=p(\Delta_r(u))\). Expanding the two branches of the parent rule gives (4 ) and (5 ). Therefore the undirected failed link is used by \(T_r\) exactly in the two cases stated in (3 ).\(\square\)

Corollary 4 (Link-avoidance root characterization). For a fixed failed link \(e=\{u,v\}\), define \[A(e)=\{r\in V: \Delta_r(u)=p(\Delta_r(v))\text{ or }\Delta_r(v)=p(\Delta_r(u))\}.\] Then a candidate root \(r\) avoids \(e\) if and only if \(r\notin A(e)\). For a failed-link set \(F_E\), a root is link-safe if and only if \[r\notin \bigcup_{e\in F_E} A(e).\]

Proposition 3 gives a necessary and sufficient \(O(1)\) coordinate test for whether a candidate root uses a specific failed link; it does not require constructing the full tree. For multiple failed links, candidate testing costs \(O(|F_E|)\) coordinate comparisons. The set \(A(e)\) is a structured exclusion set in root-coordinate space. This suggests that a closed-form link selector may be possible by intersecting the node-boundary candidate system with these link-exclusion sets, but a complete constant-size construction for arbitrary link-fault sets remains open.

A complete constant-size link-avoidance selector remains open. The present experiments therefore use a deterministic cap-bounded root order for the avoid-only comparator. This is sufficient for the hybrid method because perfect link avoidance is not required for correctness: residual failed tree links are converted into component cuts and repaired by Theorem 2 whenever the component graph is connected. Table 8 shows that the average candidates checked remain far below the cap for one to three failed links; cap hits occur only in the five-link stress regime already labeled empirical.

6 Link-Failure Exclusion and Component Repair↩︎

For a candidate root \(r\), define the failed-tree-link count \[\lambda(r,F_E)=|E(T_r)\cap F_E|.\] If \(\lambda(r,F_E)=0\), the selected tree avoids all failed links. If \(\lambda(r,F_E)>0\), the failed links split the tree into components that may still be reconnectable by healthy Gaussian edges.

Lemma 3 (Repair lower bound). If \(T_r^-\) has \(c\) healthy components, then any non-redundant repaired broadcast tree preserving these internal components must use at least \(c-1\) external component-crossing repair edges.

Proof. Contract each healthy tree component to a supernode. Any connected repaired broadcast must connect the \(c\) supernodes, and any connected graph on \(c\) vertices has at least \(c-1\) edges.\(\square\)

Theorem 2 (Edge-minimum component repair). If the healthy component graph \(\mathcal{H}_r\) is connected, then \(T_r^-\) can be repaired into a non-redundant broadcast tree over all healthy nodes using exactly \(c-1\) external component-crossing repair edges. This is minimum.

Proof. Since \(\mathcal{H}_r\) is connected, choose a spanning tree of \(\mathcal{H}_r\) rooted at the component containing \(r\). For every non-root component, add one corresponding healthy Gaussian crossing edge. The internal components are trees because they are subgraphs of \(T_r\). Contracting every component maps the repaired structure to the selected component-level spanning tree; hence no cycle is introduced. The final graph is connected, acyclic, spans all healthy vertices, and can be rooted at \(r\). It uses \(c-1\) repair edges, which is optimal by Lemma 3.\(\square\)

Lemma 4 (Component-count bound and depth accounting). Let \(q_E^T=|E(T_r)\cap F_E|\) be the number of failed links used by the selected tree, and let \(\ell_T\) be the number of failed nodes that are leaves of \(T_r\). Then pruning creates at most \[c \le 1+q_E^T+3(|F_V|-\ell_T) \label{eq:component95bound}\tag{6}\] healthy components. Consequently, if the component graph is connected, the edge-minimum repaired tree uses \[R=c-1\le q_E^T+3(|F_V|-\ell_T) \label{eq:repair95bound}\tag{7}\] external component-crossing repair edges. The hop depth of the repaired tree is a separate measured quantity: it depends on the endpoints selected for the component-crossing edges and on the rooted orientation of the repaired tree, and is therefore not bounded in general by \(k+R\).

Proof. Deleting a tree link increases the number of components by at most one, giving the \(q_E^T\) term. A failed leaf contributes no new healthy component because it has no child subtree. A non-leaf failed node in the coordinate-reduction tree has at most one parent and at most two child subtrees under the binary coordinate-priority rule used here; deleting it can therefore increase the number of healthy components by at most three. Summing these contributions gives 6 . If the component graph is connected, Theorem 2 selects exactly \(c-1\) external component-crossing edges, which gives 7 . The depth statement is an accounting clarification rather than an additional bound: after components are reconnected, a root-to-destination path may enter a component through a repair endpoint that is not the original parent-side gate of that component, and the path may then traverse a nontrivial internal subtree segment. Thus a single repair edge can add more than one hop to the longest rooted path, even though it contributes only one exceptional forwarding rule. This is why the experiments report repaired depth separately from \(R\).\(\square\)

Proposition 5 (Hybrid repaired-depth accounting). If the selected hybrid root yields \(R=0\), the repaired structure is the pruned re-rooted Gaussian broadcast tree, so its depth is at most \(k\) by Lemma 1 and is exactly \(k\) whenever a healthy boundary vertex remains. If \(R>0\) and the repair reconnects components \(C_1,\ldots,C_c\), then a coarse accounting bound is \(D_r\le k+\sum_i \operatorname{diam}(C_i)\), with \(\operatorname{diam}(C_i)\le 2k\) because each component is a subtree of a depth-\(k\) Gaussian tree. This bound is loose but resolves the interpretation: \(R\) counts exceptional component-crossing forwarding rules, whereas depth also depends on the internal distance from a repair-entry gate to the farthest descendant inside each reconnected component. The near-\(k\) hybrid depths in the experiments therefore reflect the observed small residual component diameters after re-rooting, not a universal \(k+R\) bound.\(\square\)

Proposition 1 (Component-count bound tightness). The bound in 6 is worst-case tight when every non-leaf failed node has one parent edge and two child subtrees in \(T_r\), and when all failed tree links lie on distinct tree paths.

Proof. In such a placement, each failed tree link separates one previously connected child subtree, increasing \(c\) by exactly one. Each non-leaf failed node with one parent and two child subtrees separates the parent-side component and two child-side components, increasing the count by exactly three relative to the intact tree. If the affected paths are distinct, none of these increases merge or overlap. The upper bound is therefore attained.\(\square\)

The bound is deliberately a worst-case tool. Boundary faults have fewer children, and multiple faults often lie on the same subtree path. Hence practical component counts are much lower than the bound for node faults; Table 6 quantifies this gap.

Example 3 (multi-component repair). Figure 5 provides a worked example with \(c=3\) components. The healthy component graph \(H\) has three vertices and a highlighted spanning tree. Mapping those two highlighted component-graph edges back to the Gaussian network gives exactly the two dashed repair edges in panel (d), making the statement of Theorem 2 visually immediate.

Lemma 5 (Healthy graph implies component graph). If the healthy graph \(G_k-F_V-F_E\) is connected, then \(\mathcal{H}_r\) is connected for every pruned tree \(T_r^-\) over the healthy vertices.

Proof. For any two tree components, a path in the connected healthy graph joins them. Whenever this path moves from one tree component to another, it uses a healthy crossing edge; therefore the path induces a path in \(\mathcal{H}_r\).\(\square\)

Lemma 6 (No Gaussian edge is a bridge). Every edge of \(G_k\) lies on a 4-cycle. Therefore deleting one link does not disconnect \(G_k\).

Proof. For an edge \((u,u+k)\), the vertices \[u, \quad u+k, \quad u+k+(k+1), \quad u+(k+1)\] form a 4-cycle using generator differences \(k,k+1,-k,-(k+1)\). The generator \(k+1\) case is symmetric.\(\square\)

Theorem 3 (Deterministic single-link repair). For any one failed link \(e\in E(G_k)\) and any healthy selected root \(r\), the hybrid repair phase succeeds. If \(e\notin E(T_r)\), zero repair edges are needed. If \(e\in E(T_r)\), exactly one repair edge is necessary and sufficient.

Proof. If \(e\) is not in \(T_r\), pruning does not change the tree. If \(e\) is in \(T_r\), deleting it splits the tree into exactly two components. By Lemma 6, \(G_k-e\) is connected; by Lemma 5, the two-component graph is connected. Theorem 2 repairs it with \(c-1=1\) edge, and Lemma 3 proves that one edge is necessary.\(\square\)

Proposition 2 (Minimum isolating cut). For any healthy node \(v\) in \(G_k\), the minimum node-fault set that isolates \(v\) from all other healthy nodes has size four, consisting of the four Gaussian neighbors of \(v\). The minimum link-fault set that isolates \(v\) has size four, consisting of the four incident edges of \(v\).

Proof. Every vertex of \(G_k\) has exactly four incident Gaussian channels, corresponding to the generators \(\pm k\) and \(\pm(k+1)\). To isolate a fixed healthy node \(v\) as a singleton component, every incident channel from \(v\) to a healthy neighbor must be removed. With node faults this requires faulting all four Gaussian neighbors of \(v\); any set of at most three faulty neighbors leaves at least one healthy neighbor adjacent to \(v\). Thus four node faults are necessary and the four-neighbor set is sufficient. The same local argument applies to links: all four incident edges of \(v\) must be removed, and the four incident edges are sufficient.\(\square\)

Example 2 (single-link repair). Take \(k=3\) and let the tree edge between \((1,0)\) and \((2,0)\) fail. The local 4-cycle \[(1,0)\rightarrow(2,0)\rightarrow(2,1)\rightarrow(1,1)\rightarrow(1,0)\] contains the failed edge and provides a healthy bypass across the top side of the cycle. Thus a single crossing edge reconnects the two pruned tree components.

7 Runtime Micro-Re-Rooting Protocol↩︎

The runtime protocol handles a failed link discovered during broadcast propagation. Suppose node \(u\) attempts to forward a packet to child \(v\) and detects that edge \((u,v)\) is unavailable. The detector reports the failed link and its current layer. The recovery action has three logical phases.

Phase 1: local observation. The detector records the failed link and the partially reached set. In a strictly local implementation, the affected subtree can be treated as the recovery region. In the present experiments, we evaluate the conservative global recovery variant: the detector triggers a re-rooting and repair over the whole broadcast instance. This gives an upper bound on recovery scope and isolates the source-selection and repair behavior.

Phase 2: candidate selection and link test. The candidate generator returns one or more roots. Each candidate is tested by \(\lambda(r,F_E)\), the number of failed links used by its tree. A root with \(\lambda=0\) is preferred. If none is found, the root minimizing failed tree links and maximizing node-leaf score is used.

Phase 3: component repair. The selected tree is pruned, the healthy components are contracted, and a component spanning tree is selected if \(\mathcal{H}_r\) is connected. The detector-to-root relocation is routed through the healthy graph. If relocation is impossible, recovery fails; otherwise, the repaired tree is used to complete delivery.

The transient protocol therefore supports both a global form, used in the experiments, and a local/regional form in which \(\mathcal{H}_r\) is built only for the affected subtree. The local form is the natural hardware optimization because only descendants of the detected failed forwarding edge need to be reconsidered. The global form is the safer validation model because it does not rely on optimistic assumptions about regional containment. Thus the reported transient latency is best interpreted as a conservative upper-level recovery cost rather than a claim that every implementation must pause the whole NoC.

Example 4 (transient discovery). Suppose the propagation front has reached layer \(\ell=7\) when a router discovers that its next forwarding link is unavailable. The detector reports the failed link, the source is relocated by \(d(s,r)\) hops, and the repaired tree then finishes in depth \(D_{\mathrm{repaired}}\). The recovery time decomposition \[T_{\mathrm{recover}}=\ell_{\mathrm{detect}}+d(s,r)+D_{\mathrm{repaired}}\] is reported later through the transient discovery-layer table, where three placement classes exhibit different discovery times but the same logical three-phase structure.

7.1 Regional Recovery Cost Bound↩︎

The global transient experiment is a conservative upper-level model. If a failed tree edge is discovered at layer \(\ell\), then the affected downstream region has remaining height at most \(h=k-\ell\). A Gaussian ball of radius \(h\) contains \(1+2h(h+1)\) vertices, so a regional repair that scans only the affected subtree has the bound \[N_{\mathrm{local}}(\ell)\le 1+2(k-\ell)(k-\ell+1).\] Relative to \(N=1+2k(k+1)\), the scan fraction is at most \[\frac{N_{\mathrm{local}}(\ell)}{N}\le \frac{1+2(k-\ell)(k-\ell+1)}{1+2k(k+1)}.\] For \(k=200\), the measured discovery layers imply the regional upper bounds in Table 3. Boundary-discovered faults require almost no regional scan, random tree-edge failures require about 11.4% of the graph on average, and only near-root failures approach the global cost.

8 Higher-Order Best-Effort Heuristic↩︎

For three or more node faults, a common distance-\(k\) source is not guaranteed. Therefore high-order recovery is explicitly treated as best effort. For a candidate root \(r\), define the leaf score \[L(r)=|\{f\in F_V:\operatorname{dist}(r,f)=k\}|.\] The heuristic ranks roots lexicographically by high \(L(r)\) and low \(\lambda(r,F_E)\). After a root is selected, the repair theorem is still exact: if \(\mathcal{H}_r\) is connected, the repair uses the minimum \(c-1\) edges. What becomes heuristic is the existence and selection of a root that keeps \(\mathcal{H}_r\) connected in arbitrary high-order clustered fault patterns.

Theorem 4 (Re-rooting reliability threshold and triple-intersection criterion). Let \(F_V\) be a node-fault set in \(G_k\). For \(|F_V|\le2\), a root \(r\) satisfying \(\operatorname{dist}(r,f)=k\) for every \(f\in F_V\) always exists, and if \(F_E=\emptyset\) the repaired broadcast requires zero component-crossing repair edges. For \(|F_V|=3\), a zero-repair re-rooting root exists if and only if \[\bigcap_{f\in F_V}\{r\in V:\operatorname{dist}(r,f)=k\}\ne\emptyset. \label{eq:triple95intersection}\tag{8}\] Equivalently, for \(F_V=\{f_1,f_2,f_3\}\), this condition is \[I(f_1,f_2)\cap I(f_1,f_3)\ne\emptyset.\] There is no universal three-node guarantee: for example, in \(G_3\) the three faults \((-3,0)\), \((-1,0)\), and \((1,0)\) have no common distance-three root.

Proof. The \(|F_V|\le2\) case is Corollaries 1 and 2. For three faults, a root gives zero-repair re-rooting precisely when every failed node is at layer \(k\) relative to that root. This is exactly the intersection condition (8 ). For \(F_V=\{f_1,f_2,f_3\}\), the first two constraints define \(I(f_1,f_2)\) and adding the third constraint is equivalent to intersecting with \(I(f_1,f_3)\). The \(G_3\) example can be checked directly on the 25-node coordinate ball: no coordinate \((x,y)\) with \(|x|+|y|\le3\) has Manhattan distance three from all of \((-3,0)\), \((-1,0)\), and \((1,0)\) under the dense Gaussian quotient. Hence the one/two-fault guarantee is the deterministic threshold for universal zero-repair re-rooting, while three-fault success depends on the triple-intersection geometry.\(\square\)

Theorem 4 gives an exact test for three-node zero-repair re-rooting but intentionally does not claim that all three-fault sets are recoverable by re-rooting alone. The hybrid method can still recover many three-fault cases after component repair, but this recovery is conditional on the selected component graph remaining connected.

Proposition 4 (Local-obstruction probability bound). Let \(q\) node faults be sampled uniformly without replacement from \(V(G_k)\), and let \(\mathcal{P}_k\) be any family of local obstruction patterns such that \(|\mathcal{P}_k|\le C N\) and every pattern consists of \(s\) specified faulty vertices, where \(C\) and \(s\) are independent of \(k\). Then \[\begin{align} &\Pr[\exists P\in\mathcal{P}_k:\; P\subseteq F_V] \notag\\ &\qquad\le C N \left(\frac{q}{N}\right)^s = O\!\left(\frac{q^s}{k^{2s-2}}\right). \end{align}\] In particular, the four-neighbor isolation obstruction of Proposition 2 has \(s=4\) and probability \(O(q^4/k^6)\) for fixed \(q\).

Proof. For any fixed pattern \(P\) of size \(s\), the probability that all vertices of \(P\) are sampled is \[\frac{\binom{N-s}{q-s}}{\binom{N}{q}}\le \left(\frac{q}{N}\right)^s.\] A union bound over at most \(C N\) translated local patterns gives the first inequality. Since \(N=2k^2+2k+1=\Theta(k^2)\), the asymptotic form follows. For four-neighbor isolation, \(s=4\) and there is one translated pattern per vertex up to a constant factor.\(\square\)

Proposition 4 is not a complete guarantee that \(\mathcal{H}_r\) is connected; component-graph disconnection can occur through more global arrangements than a single isolated vertex. It does, however, formalize the density effect observed in Table ¿tbl:tab:rootcause?: fixed-size local obstructions become rapidly less likely as \(k\) grows, while close-cluster placements deliberately concentrate faults in the local patterns most likely to defeat repair.

This separation is important. The paper does not claim a universal high-order guarantee. It claims a deterministic repair theorem conditional on component-graph connectivity and then measures how often re-rooting makes this condition true in high-order regimes. The heuristic has no approximation-ratio guarantee: an adversary can choose the four-neighbor or four-incident-link isolating cuts of Proposition 2. The experimental high-order claim is therefore distributional over the tested random, critical, near-source, and close-cluster placements. The close-cluster rows in Table ¿tbl:tab:rootcause? are the stress tests that most closely approximate adversarial local cuts.

9 NoC-Oriented Evaluation Methodology↩︎

The primary large-scale evaluation is graph-level and cycle-count oriented. This is intentional for the full \(k\in\{10,25,50,100,200\}\) campaign: the goal is to test the mathematical recovery boundary, component connectivity, repair-edge count, candidate overhead, and transient discovery behavior over hundreds of thousands of trials. To strengthen the NoC interpretation, we also include patched native Gaussian-link Noxim scheduled replays. The main replay uses \(k=25\) (\(N=1301\)) and an additional \(k=50\) audit checks the larger-router case. In the patched build, the Noxim topology generator instantiates Gaussian physical links \(u\leftrightarrow u\pm k\) and \(u\leftrightarrow u\pm(k+1)\pmod N\); the routing module uses the same Gaussian coordinate-distance rule as the graph model. Thus the graph-level campaign is the large-scale evidence, while the Noxim replay is a focused router-level validation of recovered broadcast operation. It is not a standard unmodified Noxim topology and not a random saturation-throughput experiment; it is a scheduled replay of recovered broadcast and repair traces on a documented Gaussian-link Noxim patch.

9.1 Experimental Settings↩︎

We test \[k\in\{10,25,50,100,200\},\] corresponding to \(N=221,1301,5101,20201,80401\) nodes. Static experiments use 280,000 trials. Transient experiments use 15,000 trials. Static fault regimes include node-only, link-only, and mixed node/link faults under random, critical, near-source, and close placements. Transient trials include critical-near-root, random-tree-edge, and boundary-branch failed links.

9.2 Compared Recovery Modes↩︎

Four modes are evaluated.

1. Baseline no repair: the original source broadcasts on the original tree; failed forwarding nodes or links stop propagation.

2. Re-root avoid-only: select a new source and succeed only if its tree avoids failed links and places node faults as leaves.

3. Fixed-source component repair: keep the original source, prune its tree, and repair components if the component graph is connected.

4. Re-root plus component repair: select a damage-reducing root, prune the selected tree, and repair components. This is the proposed hybrid method.

9.3 Measured Metrics↩︎

We measure success rate, reached healthy nodes, candidate count, candidates checked, scan exhaustion, relocation success, components after pruning, repair edges, repaired depth, total recovery steps, failed tree links used after re-rooting, and root-cause labels for failed hybrid trials. For NoC interpretation, the number of repair edges is also the number of exceptional component-crossing forwarding entries required by the repaired tree. Thus reducing repair edges reduces additional forwarding state and exceptional control actions. The native Noxim replay additionally reports completion cycles, control packets, forwarding exceptions, router delay, throughput, and within-simulator energy per packet.

9.4 Patched Native Gaussian-Link Noxim Scheduled Replay↩︎

The native Noxim validation uses the same \(k=25\) network (\(N=1301\)), but it does not rely on a standard Noxim mesh, torus, or butterfly topology. We used a patched Noxim build in which the topology generator was extended with a GAUSSIAN mode and the routing module was extended with a GAUSSIAN mode. For \(k=25\), the simulator instantiates 1301 routers indexed by \(u\in\mathbb{Z}_{1301}\) and creates the physical adjacency \[\mathrm{Adj}(u)=\{u\pm 25,\;u\pm 26\}\pmod {1301} .\] The routing mode forwards over these native Gaussian links using the same canonical-coordinate distance rule used in the graph model. The command line therefore uses -topology GAUSSIAN, -dimx 1301, -dimy 1, -routing GAUSSIAN, and a hardcoded scheduled-replay traffic file. These flags are not part of unmodified Noxim; they refer to the documented patch used for this experiment.

Unlike the earlier table-probability workload, the scheduled replay is not a random saturation-throughput experiment. Each replay file injects recovery/control traffic and data packets according to the selected repaired broadcast structure. Thus the reported completion time includes recovery setup and scheduled broadcast completion. The purpose is to validate the broadcast recovery operation under router-level execution, not to characterize the saturation throughput of arbitrary application traffic.

Table 4 summarizes the Noxim patch and replay settings. The native replay is a focused collective-operation validation rather than a broad NoC scaling sweep. The \(k=25\) run evaluates five regimes: fault-free, one critical tree link, five critical tree links, a higher-order clustered node-fault stress case, and a two-node/two-link mixed case. The compared methods are baseline no repair, fixed-source component repair, and hybrid re-rooting plus component repair. We run 30 trials per regime and method, for 450 Noxim executions. All native-link runs completed with zero nonzero return codes, zero parse warnings, zero packet mismatches, and zero scheduled-replay violations in the packet/replay audit. A \(k=50\) audit also completed 450/450 Noxim runs, and the only candidate-window warning disappeared after full-root scanning. The output logs verify the use of -topology GAUSSIAN, -dimx N, -dimy 1, -routing GAUSSIAN, and hardcoded scheduled replay traffic.

10 Results↩︎

10.1 Claim-Regime Recovery↩︎

Table 5 summarizes the main recovery regimes. The first three rows are deterministic or theorem-candidate bounded regimes. The multi-link and high-order rows are empirical/best-effort regimes. Figure 6 complements the table by showing the four recovery curves as fault complexity increases.

10.2 Repair-Edge Reduction↩︎

Table ¿tbl:tab:repair95edges? gives the strongest empirical evidence. Fixed-source component repair usually succeeds, but it uses substantially more repair edges. Re-rooting reduces average repair edges to zero in the deterministic node and single-link regimes and remains much lower in mixed and high-order regimes.

max width=

The last column of Table ¿tbl:tab:repair95edges? reports the measured average depth of the selected hybrid repaired tree, not a quantity computed from the repair-edge count \(R\). This notation is used only to summarize how close the hybrid depth remains to the fault-free diameter \(k\) in the tested regimes. Lemma 4 bounds the number of components and hence the minimum number of exceptional component-crossing rules; the longest hop path also depends on where those crossing edges attach inside the affected components. This distinction is essential in the fixed-source rows of Table ¿tbl:tab:noxim95native?, where a small number of repair edges can reconnect deep subtrees and therefore produce depths much larger than \(k+R\). A latency-dominant implementation using \(J_{\alpha,\beta,\gamma}\) can therefore read the edge and depth measurements together: when \(\beta\gg\alpha\), a different root weighting may be preferable, and the tables provide the data needed to evaluate that tradeoff without rerunning the reachability experiments.

The bound in Lemma 4 is tight in the worst case but loose in practice. It is tightest for link faults because each failed tree link can create exactly one additional component; it is loosest for re-rooted node faults because leaf placement suppresses most component creation.

10.3 Single-Link Theorem-Mining Results↩︎

For all tested \(k\) and placements, the single-link regime has 100% candidate found, 100% selected-source link safety, and 100% hybrid recovery. This matches Theorem 3. The result is not merely empirical: single-edge deletion cannot disconnect \(G_k\), and if the failed edge lies in the selected tree, it creates exactly two tree components that are reconnectable by one crossing edge.

10.4 Transient Recovery↩︎

Table 7 reports transient one-link recovery. Discovery layer varies by placement, showing that the simulation records actual detection depth rather than always charging the full diameter. Hybrid recovery succeeds in every transient trial. The discovery-layer values supply the timing inputs for the recovery-latency decomposition.

10.5 Root-Cause Analysis of Non-Perfect Rows↩︎

The two non-100% rows in Table 5 are fully explained by the component-graph condition. Table ¿tbl:tab:rootcause? breaks down all hybrid failures. In the multi-link regime, there is one failure out of 60,000 trials: a \(k=10\) five-link near-source case with a disconnected healthy component graph. In the higher-order heuristic regime, there are 44 failures out of 120,000 trials. Forty-three have successful relocation but disconnected component graphs; one has both a disconnected component graph and failed relocation. The failures are concentrated in five-node close or near-source clustered cuts at small \(k\). These are exactly the patterns expected to be difficult: several faults remove neighboring forwarding and bypass opportunities at once, so the healthy graph may remain large but the component graph induced by the selected tree can become disconnected.

max width=

This table is important for interpretation. The non-100% rows are not unexplained anomalies. They occur precisely where the theorem allows failure: the healthy component graph is disconnected or the relocation path is unavailable. Thus the high-order rows should be interpreted as empirical best-effort recovery rather than deterministic guarantees.

The concentration in close five-node clusters has a structural explanation. A close cluster removes several adjacent side-entry and bypass ports at once. In small \(k\), the boundary is near every local cut, so there are fewer alternate component-crossing edges after quotient identification. Proposition 2 gives the limiting obstruction: four neighboring node faults can isolate a healthy vertex, and four incident link faults can do the same. The observed five-node close failures are not exactly that trivial obstruction in every trial, but they are the same phenomenon at the component level: all crossing edges from one pruned component to the rest of the healthy graph are removed.

10.6 Candidate-Generation Overhead↩︎

Table 1 stated the algorithmic bound. In the full run, the exact one/two node source selection checked one candidate in the guaranteed node rows because the boundary intersection returned a valid candidate immediately. Proposition 3 reduces each failed-link test to constant-time coordinate comparisons, so the link-only candidate phase checks roots without constructing full trees. Link-only avoid-only scans sometimes reached the 20,000 cap for \(k=100\) and \(k=200\) multi-link trials, but the proposed hybrid repair still achieved 100% recovery in those large-\(k\) multi-link rows because component repair does not require perfect link avoidance. Therefore scan-cap effects influence the avoid-only comparator, not the correctness of the component-repair phase. Table 8 reports the actual link-only candidate overhead. The average remains far below the cap for one to three failed links. Five-link cases are the only setting where the cap is sometimes reached; this is exactly the regime already labeled empirical rather than guaranteed.

10.7 Patched Native Gaussian-Link Noxim Scheduled Replay↩︎

Table ¿tbl:tab:noxim95native? reports the patched native Gaussian-link Noxim scheduled replay. The \(k=25\) run contains 450 Noxim executions: five regimes, three methods, and 30 trials per regime/method. All runs completed successfully; the audit reported zero nonzero return codes, zero parse warnings, zero packet mismatches, zero failed-link uses in the scheduled trace, zero faulty endpoints, zero parent-order violations, and zero non-Gaussian replay edges. The link-only sanity checks confirm that the hybrid selector changes the source in all one-link and five-link critical trials. A follow-up \(k=50\) audit produced the same packet/replay/parser outcome; its only warning was traced to scanning roots \(0,\ldots,4999\) in a network with \(N=5101\), and a full-root scan selected root 2475 with zero failed tree links, zero repair edges, complete reach \(5101/5101\), and Noxim return code 0.

max width= max width=

The native replay confirms the structural graph-level trend under router-level execution while showing why completion cycles should not be overclaimed. Hybrid reduces repair edges from 1.00 to 0.00, 5.00 to 0.03, 3.20 to 0.00, and 4.37 to 0.20 in the four faulty regimes, and it keeps repaired depth near \(k\), consistent with Proposition 5. Completion cycles depend on setup and delivery tail: boundary re-rooting can reduce components while spreading the last deliveries across a wider coordinate span than a fixed central source. Hybrid improves the five-link critical completion time by about 18%, is essentially tied in the one-link case, and is slower in the higher-order and two-node/two-link rows under the state objective. Table 9 confirms that zero setup makes the hybrid selectors faster or competitive in all audited regimes, while the latency-weighted selector improves normal completion in the two non-dominant regimes. Thus the safe conclusion is 100% delivery with far fewer repair edges, components, and depth; completion-cycle benefit is regime- and objective-dependent rather than universal.

Critical-regime normal rows appear in Table [tbl:tab:noxim95native]

; zero setup isolates reconfiguration overhead.

11 Discussion↩︎

11.1 Why the Contribution Is Not Merely Incremental↩︎

The hybrid method changes the objective from either source selection or local tree repair alone to damage-minimizing root selection followed by optimal residual repair. Static re-rooting asks whether a root exists that places node faults on the boundary. Component repair asks how to reconnect a given pruned tree. The present paper asks a different question: which root should be selected so that the post-fault component structure is as small as possible, and how should residual link and transient failures be repaired with minimum external edges? This is a new coupled optimization because the chosen root changes the component graph on which the \(c-1\) theorem acts. The empirical consequence is visible in Table ¿tbl:tab:repair95edges?: fixed-source repair often succeeds, but re-rooting changes the component partition and sharply reduces required repair edges. This is why the primary empirical metric is repair-edge reduction, not only success rate.

11.2 NoC Interpretation↩︎

In a NoC implementation, a repair edge corresponds to one exceptional forwarding action between healthy components; hence Table ¿tbl:tab:repair95edges? measures additional forwarding-state cost. The patched native Gaussian-link Noxim replay adds router-level timing, throughput, and within-simulator energy evidence, while the main claim remains recovery correctness and reduction of exceptional repair state. Tables ¿tbl:tab:noxim95native? and 9 show that this advantage can reduce scheduled completion cycles, especially with zero setup or a latency-weighted selector, but completion time is not universally minimized by the state-sensitive selector. The longer tail has a geometric source: distance-\(k\) boundary placement can make the final delivery frontier span the full coordinate-ball diameter even when the component count is minimal. Calibrated EDP, saturation throughput, background traffic, and virtual-channel pressure are natural extensions, not assumptions needed for the current edge-minimum repair claim.

11.3 Why the Graph Theorems Matter↩︎

The component-repair theorem is elementary in its final graph form, but its role in the paper is structural: it converts every complicated node/link fault pattern into a component graph whose repair optimum is known exactly. The nontrivial design question is therefore moved to root selection and damage reduction. This separation is useful for TC-style interconnection work because it prevents empirical success from hiding nonminimal repair. Every successful hybrid trial is accompanied by a certificate: a selected root, a component graph, and exactly \(c-1\) crossing edges.

11.4 Limits↩︎

The deterministic guarantees are intentionally limited. One/two node re-rooting and one-link repair are guaranteed. For multiple links and high-order node faults, the theorem is conditional on the connectedness of \(\mathcal{H}_r\). The root-cause table shows exactly where this condition fails. The failure concentration at small \(k\) has a quantitative explanation. At \(k=10\), the network has \(N=221\) nodes; five close-cluster faults can remove five nodes and many adjacent forwarding opportunities, representing a visible fraction of the local bypass capacity. At \(k=200\), the same five faults represent only \(5/80{,}401\approx0.006\%\) of the network, so the relative bypass-capacity loss is negligible and the component graph almost always remains connected. For fixed fault count, this density scales as \(O(1/k^2)\) because \(N=2k^2+2k+1\). This explains why the failures in Table ¿tbl:tab:rootcause? are concentrated in small-\(k\) close clusters. Proposition 4 gives a first-order union-bound explanation for fixed-size local obstructions, but a complete high-probability connectivity theorem proving that \(\mathcal{H}_r\) is connected with high probability under random uniform faults, for example for \(q=o(k)\), remains open. The transient evaluation is limited to one link discovered during propagation; node transients, sequential multi-link discoveries, and cascading recovery-phase faults are outside scope. A complete characterization of high-order cuts that defeat repair, and a constant-size link-safety selector analogous to the 144-case node selector, remain open.

11.5 Future Cycle-Accurate Evaluation↩︎

The patched native Gaussian-link Noxim replay removes the main topology limitation of the earlier workload-only validation, and the \(k=25/k=50\) audits close the packet-accounting and replay-validity concerns. Larger \(k\) sweeps, more injection rates, background traffic, virtual-channel pressure, calibrated power models, and EDP remain future NoC extensions rather than prerequisites for the present scheduled collective-operation validation.

12 Complexity↩︎

For a fixed root, constructing the tree, pruning it, computing connected components, scanning Gaussian neighbor edges, and building a component spanning tree all take \(O(N)\) time because the network has degree four. Candidate generation costs \(O(k)\) for exact one/two node boundary enumeration in the validation prototype, \(O(1)\) for the shifted sign-case primitive, and \(O(M|F_E|)\) for link-only candidate testing with \(M\le20000\) in the full run. Therefore the full experimental implementation is \(O(N+M|F_E|)\) per trial for a selected root, not \(O(N^2)\). Table 8 shows that the average link-only \(M\) is much smaller than the cap except in five-link stress cases. Lemma 4 bounds the component count and hence the number of external repair rules; Proposition 5 gives the corresponding coarse depth accounting, while the exact repaired depth is measured separately because it also depends on the attachment endpoints and the final rooted orientation.

In a hardware implementation using the constant-size two-node generator and a bounded number of link faults, the candidate phase is constant size and the repair phase can be restricted to the affected components or subtree. The global implementation used here is a conservative validation model.

13 Conclusion↩︎

This paper introduced re-rooting-assisted edge-minimum runtime repair for dense Gaussian broadcast networks under static node faults, static link faults, mixed static faults, and runtime-discovered single-link faults. The method selects a damage-reducing source and then repairs residual fragmentation. If the healthy component graph has \(c\) components and is connected at the component level, exactly \(c-1\) external repair edges are necessary and sufficient; a single failed Gaussian link is always avoided or repaired with at most one crossing edge.

Experiments show that the hybrid method recovers all tested deterministic and bounded mixed regimes, recovers 99.998% of multi-link trials and 99.963% of higher-order heuristic trials, and reduces repair-edge count by 80–100% compared with fixed-source repair. The few failures are fully explained by disconnected component graphs or relocation failure. Patched native Gaussian-link Noxim scheduled replay and audit runs show that this structural reduction yields smaller components and shallower repaired structures under router-level execution. The completion-cycle audit confirms that the replay and parser are clean while also showing that completion time depends on setup, scheduling, delivery tail, and selector objective. Thus completion time is reported as an objective-dependent metric rather than a universal dominance claim.

Data and Reproducibility↩︎

The run uses fixed seeds and writes raw trials, summaries, metadata, and figure-ready CSV outputs. A supplementary artifact package contains graph scripts, raw CSVs, plotting inputs, the patched-Noxim driver, native Gaussian-link patch, scheduled traces, logs, parsers, packet/replay audit tables, and the full-root-scan \(k=50\) correction record, prepared for DOI-linked archival deposition.

References↩︎