Multi-Orientation Edge-Minimum Repair for Non-Redundant Fault-Tolerant Broadcasting in Dense Gaussian Networks arXiv:2606.17528v1 [cs.DC] 16 Jun 2026
Bader A. Albader Department of Computer Science, Faculty of Science, Kuwait University, Kuwait [email protected]
Abstract Dense Gaussian networks are degree-four algebraic interconnection networks with compact diameter and simple modular routing. This paper studies non-redundant oneto-all broadcast repair in the dense Gaussian network generated by α = k+(k+1)i. We propose multi-orientation edge-minimum repair (MOEM), which evaluates a constantsize family of Gaussian broadcast-tree orientations, selects a fault-aware orientation, contracts the fault-pruned tree into healthy components, and reconnects those components using external component-crossing repair edges. The resulting structure is a rooted spanning tree of the healthy subgraph, so each healthy node receives the message exactly once and no faulty node is used. We prove that, for a chosen orientation with c fault-pruned components and a connected healthy component graph, the repair step is non-redundant and uses the minimum possible number c − 1 of external component-repair edges. We also prove that, for every one- or two-fault placement, the MOEM orientation family contains a repair with depth at most k + 2. The depth proof combines a certificate framework, an explicit four-case off-axis analysis, and a five-component orthogonal-axis certificate. Exhaustive validation for k = 5, . . . , 10 and large-scale validation through k = 200 confirm the implementation and show that random two-fault repairs use approximately two external repair edges.
Keywords: Gaussian networks, Cayley graphs, fault-tolerant broadcasting, non-redundant communication, local repair, interconnection networks, Hamiltonian cycles.
1
Introduction
One-to-all broadcasting is a fundamental collective communication primitive in parallel and distributed systems. In a non-redundant broadcast, each healthy node receives the message exactly once. This is desirable because it avoids duplicate traffic, reduces contention, and gives a simple correctness condition: the transmission structure must be a rooted spanning tree of the healthy subgraph. The challenge is that a broadcast tree designed for a fault-free topology can be fragmented by a small number of faulty processors. 1
Algebraic interconnection networks provide attractive settings for structured communication algorithms. Cayley-graph models give symmetry and compact routing descriptions [1]; tori and related networks have long been used to study collective communication and fault tolerance [2, 3, 4]. Gaussian networks are quotient networks over Gaussian integers. They provide degree-four planar algebraic topologies with strong routing, placement, and Hamiltonian properties [11, 13, 15]. The dense Gaussian family considered here has particularly simple integer labels and a natural diameter-level coordinate ball. Let N = k 2 + (k + 1)2 and let Gk be the dense Gaussian network generated by α = k + (k + 1)i. The node set is ZN and the edges are u ∼ u ± k,
u ∼ u ± (k + 1)
(mod N ).
The map ϕ(x + yi) ≡ kx + (k + 1)y
(mod N )
(1)
identifies the Manhattan ball Bk = {(x, y) ∈ Z2 : |x| + |y| ≤ k} with the N nodes of Gk . The ball has exactly 2k 2 + 2k + 1 = N points. Hence, a sourcecentered Gaussian broadcast tree can reach all nodes in depth at most k in the fault-free case. The problem studied in this paper is the following. Definition 1 (Non-redundant local broadcast repair). Given a source s and a fault set F ⊆ V (Gk ) with s ∈ / F , construct a rooted spanning tree of Gk − F rooted at s. The construction should use no faulty node, should give every healthy non-source node exactly one parent, should keep the number of repair edges small, and should keep the broadcast depth close to the fault-free depth k. A single fixed Gaussian broadcast tree is vulnerable to trunk faults. If a fault lies on a major branch, the tree may split into several components. A depth-safe repair can reconnect the healthy nodes by adding many candidate crossing edges and taking a breadth-first tree, but this may substantially increase the repair count. The central observation of this paper is that one should not repair a poor orientation when another valid orientation may be much less damaged. This distinction between static placement and post-fault broadcast repair motivates the orientation-selection step in MOEM. This paper proposes multi-orientation edge-minimum repair (MOEM). MOEM constructs a small family of deterministic Gaussian broadcast-tree orientations. For each orientation, it removes the faults, forms the component graph of the resulting forest, and applies an edgeminimum component repair. The final output is the valid candidate with best lexicographic score, primarily minimizing depth and then repair count. In the final data, MOEM avoids fallback entirely for random trials with k ≥ 25. The main contributions are as follows. 2
• We formulate non-redundant local repair for dense Gaussian one-to-all broadcasting under one and two processor faults. • We introduce MOEM: an eight-orientation Gaussian broadcast family followed by edgeminimum component repair. • We prove that repairing a chosen fault-pruned orientation with c components requires and attains exactly c − 1 external component-crossing edges. • We prove a k + 2 repaired-depth theorem for every one- and two-fault placement using coordinate certificates, including an explicit O3 off-axis classification and an O6 orthogonal-axis certificate. • We validate all one- and two-fault placements for k = 5 through 10 and large-scale cases through k = 200, and we identify hard cases showing that the balanced-smaller-first orientation is indispensable within the tested family. This paper focuses on the first nontrivial multi-fault regime, |F | ≤ 2. This scope enables a complete coordinate proof of the k + 2 depth law. The component-repair theorem applies to any selected orientation and any fault count with a connected healthy component graph, while the depth-certificate theorem is proved here for one and two faults; Section 7 sketches the three-fault certificate classes suggested by the proof.
2
Related Work
Akers and Krishnamurthy gave a group-theoretic model for symmetric interconnection networks, providing a foundation for algebraic network design [1]. Classical texts cover meshes, tori, hypercubes, and collective communication patterns [2, 3]. AlMohammad and Bose studied non-redundant fault-tolerant communication in toroidal networks [4]; their work is conceptually related because it preserves collective communication after faults, but it does not repair a pruned dense Gaussian broadcast tree under an external component-crossing edge metric. Gaussian and Eisenstein–Jacobi networks were developed as algebraic interconnection topologies with compact routing and useful symmetry. Martinez et al. modeled toroidal networks using Gaussian integers and studied dense Gaussian networks as low-degree on-chip multiprocessor topologies [5, 6]; related Martinez-group work includes hierarchical Gaussian, EJ/hexagonal, and lattice-derived models [7, 8, 9, 10]. Flahive and Bose studied Gaussian and Eisenstein–Jacobi topology and resource placement [11, 13]. Dense Gaussian networks also have strong Hamiltonian, routing, and path properties [12, 14, 15, 18]. Network-on-chip references motivate compact low-degree graphs [17, 16, 19], but this paper does not claim chip-level latency, bandwidth, or power evaluation. The present work differs from placement, routing, Hamiltonian-cycle construction, and precomputed tree-diversity mechanisms. MOEM starts with a specific diameter-level broadcast tree after the fault set is known, preserves its healthy components, and minimizes new external component-crossing repair edges. A global BFS rebuild may restore connectivity
3
but can replace Θ(N ) parent edges; precomputed tree-diversity methods optimize path diversity rather than post-fault local repair. Thus fixed-orientation local repair is the nearest same-objective comparator.
3
Dense Gaussian Network Model
Let Gk = (V, E) be the dense Gaussian network with V = ZN and N = k 2 + (k + 1)2 . For u, v ∈ V , (u, v) ∈ E ⇐⇒ v − u ≡ ±k or ± (k + 1) (mod N ). Edges of difference ±k are called H1 -type edges, and edges of difference ±(k + 1) are called H2 -type edges. In the dense case, gcd(k, k + 1) = 1, so each generator induces a Hamiltonian cycle.
3.1
Coordinate Representation
Equation (1) maps the coordinate ball Bk onto ZN . Since |Bk | = 1 + 2k(k + 1) = k 2 + (k + 1)2 = N, this representation is bijective. Moving from (x, y) to (x + 1, y) changes the label by k, and moving from (x, y) to (x, y + 1) changes the label by k + 1. Therefore unit Manhattan moves in Bk correspond exactly to Gaussian graph edges.
3.2
Fault-Free Oriented Broadcast Trees
For a fixed orientation θ, define a parent rule that maps each nonzero coordinate (x, y) to a neighbor closer to the origin. The x-first tree, for example, uses ( (x − sgn(x), y), x ̸= 0, px (x, y) = (2) (x, y − sgn(y)), x = 0, y ̸= 0. Applying ϕ to these parent relations gives a spanning tree of Gk rooted at the source. The depth of coordinate (x, y) is |x| + |y| ≤ k. Lemma 1. For any coordinate-reduction orientation that decreases |x| + |y| by one at every non-source node, the induced parent relation is a spanning tree of Gk with depth at most k. Proof. Each non-source node (x, y) is assigned a parent obtained by changing one nonzero coordinate by one unit toward zero. Hence the parent is adjacent in Gk and the value |x|+|y| decreases by one. Repeated parent application reaches (0, 0) after exactly |x| + |y| steps, so cycles are impossible and all nodes are connected to the source. Since |x| + |y| ≤ k for all coordinates in Bk , the depth is at most k. MOEM uses eight deterministic orientations: x-first, y-first, positive-preference variants, negative-preference variants, larger-coordinate-first, and smaller-coordinate-first. This family is intentionally small and constant-size, so orientation selection does not change the asymptotic complexity. 4
4
Multi-Orientation Edge-Minimum Repair
4.1
Component Graph
Let Tθ be the broadcast tree for orientation θ. Removing the faulty vertices and their incident tree edges gives a forest Tθ − F = C1 ∪ C2 ∪ · · · ∪ Cc . Let Cs be the component containing the source. The component graph Cθ has one vertex for each component Cj . Two component vertices are adjacent in Cθ if there exists at least one healthy Gaussian graph edge joining the corresponding components. Fig. 1 shows the component-level reduction: once the fault-pruned tree is contracted into c healthy components, any non-redundant repair must connect those components using at least c − 1 external crossing edges.
Figure 1: Component contraction view of MOEM: fault-pruned tree components, the induced component graph, and the minimum c − 1 repair edges. The repair problem at the component level is to connect Cs to all other components using component-crossing graph edges. Every selected crossing edge becomes an external repair edge.
4.2
Edge-Minimum Component Repair
At each step, MOEM chooses a crossing edge (a, b) where a is already in the connected repaired part and b is in an unrepaired component C. The selected edge minimizes the predicted depth D(a, b, C) = dist(s, a) + 1 + eccC (b), (3) where eccC (b) is the maximum distance from b to a node in component C using the current internal tree of C. Ties prefer H2 -type repair edges, then smaller components, and then a deterministic edge order.
5
Algorithm 1 Edge-Minimum Repair for One Orientation Require: Dense Gaussian network Gk , source s, fault set F , orientation tree Tθ Ensure: A repaired rooted tree over Gk − F , or failure 1: Remove F and incident tree edges from Tθ 2: Compute components C1 , . . . , Cc and the source component Cs 3: Initialize the repaired component set R ← {Cs } 4: Initialize the repaired edge set with the tree edges inside Cs 5: while |R| < c do 6: Find all Gaussian edges from a component in R to a component outside R 7: Select the edge minimizing (3), with deterministic tie-breaks 8: Add the selected crossing edge and the new component to the repaired tree 9: end while 10: Root the resulting edge set at s and validate the tree
4.3
Multi-Orientation Selection
The full MOEM algorithm evaluates the full constant-size family of eight orientations. The final candidate is selected lexicographically by (success, depth, repair edges, maximum out-degree, orientation rank), where successful candidates are ranked before unsuccessful candidates. Algorithm 2 MOEM Broadcast Repair Require: Gk , source s, fault set F , orientation family Θ Ensure: Non-redundant broadcast tree over Gk − F 1: Use the full orientation family, ΘF ← Θ 2: B ← ∅ 3: for all θ ∈ ΘF do 4: Construct the fault-free oriented Gaussian tree Tθ 5: Apply Algorithm 1 to Tθ 6: Insert the validated candidate into B 7: end for 8: Return the best valid candidate in B under the lexicographic score
4.4
Correctness
Lemma 2. Let T be a spanning tree of Gk , and let F be a set of faulty vertices not containing the source. If T − F has c connected components, then any repaired broadcast tree that uses all healthy vertices must add at least c − 1 component-crossing edges. Proof. Contract each connected component of T − F to one supernode. A broadcast tree spanning all healthy vertices must connect these c supernodes. Any connected graph on c vertices has at least c−1 edges. Each such edge corresponds to a healthy graph edge crossing between two components. Thus at least c − 1 component-crossing edges are necessary. 6
Theorem 1. Suppose the component graph Cθ of Tθ − F is connected. Then the edgeminimum repair step returns a non-redundant broadcast tree over all healthy vertices and uses exactly c − 1 external component-repair edges. Proof. Because Cθ is connected, there exists a spanning tree of the component graph rooted at the source component. The repair procedure selects one crossing edge for each non-source component, so it adds exactly c − 1 external edges. Inside each component, the original fault-pruned structure is a tree. Contracting each component after the selected crossings are added gives exactly the chosen component-level tree; therefore any cycle in the repaired graph would contract to a cycle in that component tree, which is impossible. Hence connecting these component trees cannot create a cycle and connects all healthy vertices. Rooting the resulting connected acyclic graph at s gives exactly one parent to every healthy non-source node and no parent to s. Therefore the resulting structure is a non-redundant broadcast tree. Corollary 1. MOEM returns a correct non-redundant broadcast whenever at least one tested orientation has a connected healthy component graph. The experiments in Section 6 found this condition in all tested one- and two-fault cases. Theorem 2 (Orientation dominance). Let S(·) be the lexicographic candidate score used by MOEM. Since MOEM evaluates the full orientation family Θ, if Tθ is any fixed orientation in Θ, then the candidate returned by MOEM has score no worse than the repaired candidate obtained from Tθ alone. Proof. MOEM evaluates every orientation in Θ and returns the valid candidate with minimum score. Since the repaired candidate of any fixed Tθ ∈ Θ is one of the candidates considered, the selected candidate cannot have a worse score. The result follows directly from the minimization step.
5
The k + 2 Depth Theorem
The previous section proves that, after an orientation has been selected, the componentrepair phase is correct and uses the minimum possible number of external component-crossing repair edges. This section proves the depth bound used by MOEM. The proof has three ingredients. First, a certificate lemma converts local attachment inequalities into a global depth bound. Second, a finite set of coordinate repair templates covers one-fault, sameaxis, opposite-axis, and separated off-axis two-fault placements. Third, the formerly hard orthogonal-axis pattern is handled by an explicit O6 five-component decomposition. Definition 2 (Repair certificate). Fix an orientation θ and let Tθ − F have components C1 , . . . , Cc , with source component Cs . A K-depth repair certificate is an ordering of the non-source components and crossing edges (aj , bj ),
j = 1, . . . , c − 1,
7
where aj lies in the union of the source component and previously attached components, bj ∈ Cj , and dj (aj ) + 1 + eccCj (bj ) ≤ K. (4) Here dj (aj ) is the depth of aj in the partially repaired tree before Cj is attached, and eccCj (bj ) is measured inside the original fault-pruned tree component Cj . Lemma 3 (Certificate implies bounded depth). If an orientation θ admits a K-depth repair certificate, then there exists a non-redundant repaired broadcast tree of depth at most K. Proof. Attach the components in the order specified by the certificate. When component Cj is attached through (aj , bj ), every vertex v ∈ Cj obtains a path from the source through aj , then the crossing edge (aj , bj ), then the unique internal tree path in Cj from bj to v. Therefore dist(s, v) ≤ dj (aj ) + 1 + distCj (bj , v) ≤ dj (aj ) + 1 + eccCj (bj ) ≤ K. Previously attached components already satisfy the same bound by induction. Each step connects a new tree component to the already repaired tree by one crossing edge, so no cycle is created and every healthy vertex is included exactly once. Hence the repaired structure is non-redundant and has depth at most K.
Table 1: Coordinate repair templates used in the k + 2 proof. Fault signature
Orientation choice
Detached component shape
Certificate bound
One off-axis fault (u, v), uv ̸= 0
One monotone triangular or trapezoidal suffix with a lateral boundary edge One axis interval or one-row cap
(ρ(f )+1)+1+(k−ρ(f )) ≤ k+2
Two faults on the same ray
Reduce the smaller absolute coordinate first; ties use the transverse sign preference Use a transverse-first orientation near the cut Sign preference keeps the source-side interval intact
One or two nested axis intervals
Two faults on opposite rays
Use the sign-preference orientation that separates the tails
Two independent axis intervals on opposite sides
Separated off-axis O3 pair
Four-case split: Case A (y1 ̸= y2 ); Case B (y1 = y2 , same sign, ancestor); Cases C–D reduce to Case A
Two independent chains, an inner/outer same-row pair, or one/two-node boundary microcomponents
Orthogonal-axis (a, 0), (0, b)
Use the O6 orientation with lower half-ball in the source component
Axis tail, two row fragments, and upper cap
Attach the outer interval first; each value is at most k+2 Each interval has a source-side lateral entry and remaining length at most k − r Cases B–D have value ≤ k; Case A has value k, except boundary wraparound microcomponents with value k + 1 ≤ k + 2 Explicit four-edge certificate in Lemma 9
One axis fault (a, 0)
pair
(a+1)+1+(k−a) ≤ k+2
Lemma 4 (Greedy preserves an ordered depth certificate). Suppose the non-source components of Tθ − F admit an ordering such that, before each component in the ordering is attached, there exists at least one available crossing edge with predicted depth value at most K. Then Algorithm 1, run on this orientation, produces a candidate of depth at most K. Proof. At any iteration, the hypothesis supplies an available edge with predicted value at most K. Algorithm 1 selects a crossing edge minimizing the predicted value in (3); therefore 8
the edge it actually selects also has value at most K. After this selection, the repaired side contains at least the components that would have been available in the certificate ordering at the same stage, so the next certified edge remains available when its component is considered. Repeating this argument gives a sequence of selected edges satisfying (4). Lemma 3 then gives depth at most K. In Lemmas 6–9, the certificate edges are given in an explicit attachment order. Therefore the availability condition in Lemma 4 is verified inside the case proofs rather than assumed separately in Theorem 3.
5.1
Coordinate Templates
For a point u = (x, y), let ρ(u) = |x| + |y|. A detached component is called an r-suffix if every vertex in it lies on layers at least r and every internal parent step reduces the layer by one until the cut vertex is reached. Table 1 summarizes the finite coordinate templates used in the k + 2 proof. The following elementary observation is used repeatedly. Lemma 5 (Layer-suffix attachment). Let C be a detached suffix whose entry vertex b has minimum layer at least r + 1, and suppose there is a healthy crossing edge (a, b) with a in the repaired part and dist(s, a) ≤ r + 1. If eccC (b) ≤ k − r, then attaching C through (a, b) has certificate value at most k + 2. Proof. Substituting the three assumed inequalities gives dist(s, a) + 1 + eccC (b) ≤ (r + 1) + 1 + (k − r) = k + 2. Thus the crossing edge satisfies (4) with K = k + 2.
5.2
One-Fault Shielding
Lemma 6 (One-fault k + 2 certificate). For every non-source fault f ∈ Gk , at least one MOEM orientation admits a (k + 2)-depth repair certificate for Tθ − {f }. Proof. By symmetry it is enough to consider f = (u, v) with u ≥ 0 and v ≥ 0; the other quadrants are obtained by reflecting signs and using the corresponding sign-preference orientation. Let r = u + v. If u, v > 0, choose the orientation that first reduces the smaller of u and v. If u = v, choose the deterministic transverse tie orientation. In this orientation the vertices whose parent chain passes through f form a monotone suffix of the quadrant rooted at the children of f . The suffix has remaining height at most k − r, because every internal parent step increases or decreases the layer by exactly one and no vertex of Bk has layer larger than k. The transverse child of a neighbor of f gives a lateral crossing edge (a, b) from the source component into the suffix. The attaching endpoint a lies on layer at most r + 1. Therefore Lemma 5 gives a certificate value at most k + 2. If f = (a, 0) is on an axis, choose an orientation that avoids making the whole adjacent half-ball depend on the positive x-axis when a transverse reduction is available. The detached set is then either the interval {(x, 0) : a + 1 ≤ x ≤ k} or a one-row cap adjacent to it. The 9
interval entry is adjacent to a vertex of depth at most a + 1, and the farthest endpoint is at internal distance at most k−a. Hence the certificate value is at most (a+1)+1+(k−a) = k+2. The same calculation applies to the one-row cap, whose internal eccentricity is no larger than the remaining radius to the boundary. Thus every one-fault placement has a (k + 2) certificate.
5.3
Two-Fault Generic Shielding
Lemma 7 (Same-axis and opposite-axis two-fault certificates). Let F = {f1 , f2 } with both faults on one coordinate axis, or on two opposite coordinate rays. Then some MOEM orientation admits a (k + 2)-depth repair certificate for Tθ − F . Proof. Consider first two faults on the same ray, say (a, 0) and (b, 0) with 1 ≤ a < b ≤ k. Use the sign-preference orientation whose source component contains the layer immediately before the first fault. Removing the two faults can detach only axis intervals: the finite interval between the faults and the tail beyond the second fault, with empty intervals ignored. The interval between the faults is entered from a source-side lateral neighbor at depth at most a + 1 and has length at most b − a − 1 ≤ k − a − 1. Its certificate value is therefore at most (a + 1) + 1 + (k − a − 1) = k + 1. The tail beyond b is entered from a lateral neighbor of depth at most b + 1 and has remaining length at most k − b, giving at most k + 2. If the faults lie on opposite rays, for example (a, 0) and (−b, 0), choose the sign-preference orientation that keeps the two tails on different sides of the source component. Each detached tail has a lateral entry adjacent to the source-side segment. For the positive tail the same bound as above gives (a+1)+1+(k −a) ≤ k +2; for the negative tail the reflected calculation gives (b + 1) + 1 + (k − b) ≤ k + 2. The y-axis cases are coordinate-swapped copies. Hence a certificate exists in all same-axis and opposite-axis cases. Lemma 8 (Separated off-axis two-fault certificate). Let F = {f1 , f2 } be a two-fault placement in which both faults are off-axis, and assume that the pair is not reducible to a sameaxis, opposite-axis, or orthogonal-axis pair by sign reflection and coordinate exchange. Then at least one MOEM orientation admits a (k + 2)-depth repair certificate for Tθ − F . More strongly, every separated off-axis component has certificate value at most k, except for boundary wrap-around microcomponents whose value is k + 1. Proof. Write fi = (xi , yi ) and ri = ρ(fi ) = |xi | + |yi |. A normalized representative means the image of the fault pair after applying sign reflections and, if necessary, exchanging the two coordinates, so that the detached chain being analyzed is entered from the positive-x side and yi ̸= 0. The relative position of two off-axis faults falls into the four cases below. Case
Relative position
Certificate value
A
y1 ̸= y2
B C–D
y1 = y2 , same sign, ancestor remaining same-row cases
two independent chains; value k, or k + 1 for boundary wrap-around microcomponents inner component < k, outer component k reduce by reflection or priority exchange to Case A
Case A: different rows, y1 ̸= y2 . The two detached components are two independent monotone chains. For the chain generated by fi , use the crossing whose repaired-side end10
point is ai = (xi + 1, yi − sgn(yi )), and whose component-side endpoint bi is the adjacent first vertex of the detached chain. This is a unit Gaussian edge in the coordinate model. The endpoint ai lies in the source component because the row shift yi 7→ yi − sgn(yi ) moves to the transverse side of the chain, and the two faults lie on different rows, so they cannot both block this side entry. In the normalized representative, ρ(ai ) = |xi + 1| + |yi − sgn(yi )| = |xi | + |yi | = ri . The remaining internal chain length from bi is ecc(bi ) = k − ri − 1. Therefore the certificate value is dist(s, ai ) + 1 + ecc(bi ) = ri + 1 + (k − ri − 1) = k. The only boundary subcase occurs when the detached component is a single boundary node or a two-node boundary component. Let b be the boundary entry vertex of the detached component and let e ∈ {(1, 0), (−1, 0), (0, 1), (0, −1)} be the unit step from b toward the repaired side in the infinite Gaussian grid. If b + e ∈ Bk , this is the ordinary side-entry crossing. Otherwise choose the unique quotient-lattice shift λ = m(k, k + 1) + n(−(k + 1), k) such that a = b + e − λ ∈ Bk . The vertices a and b+e represent the same residue class modulo the Gaussian ideal generated by k + (k + 1)i, so ϕ(a) ≡ ϕ(b + e) (mod N ) and {a, b} is a valid Gaussian generator edge in Gk . For the one-node boundary component, eccC (b) = 0; for the two-node boundary component, eccC (b) = 1. The wrapped repaired-side endpoint is reached one layer later than the ordinary side entry, so the corresponding certificate value is at most k + 1 ≤ k + 2. Case B: same row, same sign, ancestor relation. Suppose y1 = y2 and the two faults have the same row sign. If one fault is an ancestor of the other in the selected row orientation, the deletion creates an inner component and an outer component. Attach the inner component first using the Case-A crossing at the inner fault f1 after the local coordinate swap that exposes the transverse side row. Since the inner component terminates before the outer boundary layer, its certificate value is strictly less than k. Then attach the outer component through the layer-eccentricity crossing at the outer fault f2 . The repaired-side endpoint has depth equal to the cut layer, and the remaining eccentricity is exactly the remaining distance to the boundary. Hence the outer certificate value is k. Cases C and D: same-row reductions. The remaining same-row configurations are the non-ancestor and opposite-side same-row configurations. In both cases, a reflection of the row or an exchange of the two coordinate priorities separates the two damaged chains by a healthy transverse side entry. After that reduction, each detached component is exactly 11
the independent-chain situation of Case A. Thus each such component has certificate value at most k, with only the same one- or two-node boundary wrap-around exception of value k + 1. For two off-axis faults, either the row coordinates differ, or they are equal; in the equalrow case the faults are either in an ancestor relation, a non-ancestor relation under the selected priority, or lie in the opposite-side same-row configuration. Thus the four cases are exhaustive. Therefore every separated off-axis two-fault placement admits a repair certificate of value at most k + 1, and hence at most k + 2.
5.4
Orthogonal-Axis Case
The exhaustive proof-mining pass identified the orthogonal-axis pattern as the only case in which a single obvious priority tree may have only one good orientation. The O6 component inspection closes this case. The statement below is written for the positive pair; the other three sign patterns follow by reflection, and exchanging the two axes gives the coordinateswapped case.
Figure 2: O6 orthogonal-axis certificate: five fault-pruned components and four repair edges achieving depth at most k + 2.
12
Lemma 9 (Orthogonal-axis two-fault certificate). Assume, up to symmetry, that F = {(a, 0), (0, b)},
1 ≤ a, b,
a + b ≤ k.
Then there is a MOEM orientation whose fault-pruned tree has a (k + 2)-depth repair certificate. Proof. Use the sign-symmetric orientation whose source component contains the lower halfball and whose positive-axis faults cut only forward suffixes. The O6 component inspection shows that removing (a, 0) and (0, b) produces exactly five components. The source component is denoted by C0 . The four detached components are Cx = {(x, 0) : a + 1 ≤ x ≤ k}, Cb− = {(x, b) : −(k − b) ≤ x ≤ −1}, Cb+ = {(x, b) : 1 ≤ x ≤ k − b}, and C↑ = {(x, y) : b + 1 ≤ y ≤ k, |x| + y ≤ k}. Thus the two faults do not create arbitrary fragmentation; they create one positive x-axis tail, two row fragments on row y = b, and one upper cap. Fig. 2 visualizes this five-component decomposition and the four certificate edges used in the proof. Attach the row fragments first. The left row fragment Cb− is attached by e1 = {(−a, b − 1), (−a, b)}, where (−a, b − 1) ∈ C0 and (−a, b) ∈ Cb− . The farthest vertex of Cb− from (−a, b) is (−(k − b), b), so eccC − (−a, b) = (k − b) − a. b
Since (−a, b − 1) has depth a + b − 1, the certificate value is (a + b − 1) + 1 + ((k − b) − a) = k. The right row fragment Cb+ is attached by e2 = {(1, b − 1), (1, b)}. The attaching endpoint (1, b − 1) has depth b, and the farthest vertex of Cb+ from (1, b) is (k − b, b), at internal distance k − b − 1. Hence b + 1 + (k − b − 1) = k. Next attach the positive x-axis tail by e3 = {(a + 1, −1), (a + 1, 0)}. The endpoint (a + 1, −1) lies in C0 and has depth a + 2. The farthest vertex of Cx from (a + 1, 0) is (k, 0), at internal distance k − a − 1. Therefore (a + 2) + 1 + (k − a − 1) = k + 2. 13
Finally attach the upper cap through the already repaired right row fragment by e4 = {(1, b), (1, b + 1)}. After Cb+ is attached, the vertex (1, b) has depth b + 1. The entry point (1, b + 1) reaches every vertex of C↑ within at most k − b internal tree steps, because the cap has remaining height k − b and each parent step inside the cap decreases the Manhattan layer by one. Hence the cap certificate value is (b + 1) + 1 + (k − b) = k + 2. All four detached components therefore admit attachments of value at most k + 2. By Lemma 3, the orthogonal-axis case has a non-redundant repaired tree of depth at most k + 2. Theorem 3 (MOEM k + 2 depth theorem for one and two faults). For every k ≥ 5 and every fault set F ⊆ V (Gk ) with |F | ≤ 2 and source not faulty, the MOEM orientation family contains an orientation whose edge-minimum repair has depth at most k + 2. Consequently, MOEM returns a valid non-redundant broadcast tree of depth at most k + 2. Proof. If |F | = 0, the fault-free oriented broadcast tree has depth at most k. If |F | = 1, Lemma 6 gives an ordered (k + 2) certificate. If |F | = 2, then the pair is one of the following: same-axis or opposite-axis, separated off-axis, or orthogonal-axis after sign reflection and coordinate exchange. These cases are covered by Lemmas 7, 8, and 9, respectively. In each case, the proof gives both the crossing edges and the order in which the corresponding components are attached, so the hypothesis of Lemma 4 is satisfied for that orientation. Hence the edge-minimum repair candidate for the certified orientation has depth at most k + 2. MOEM selects the valid candidate of minimum lexicographic score, with depth preceding repair count among successful candidates. Therefore its selected candidate has depth no larger than this certified candidate. Correctness and non-redundancy follow from Theorem 1, and the external repair-edge count for the selected orientation is minimum by Theorem 1. Corollary 2 (Minimum repair count under the depth bound). For every one- or two-fault placement covered by Theorem 3, the returned MOEM tree simultaneously satisfies the depth bound k + 2 and uses exactly c − 1 external component-repair edges for its selected faultpruned orientation, where c is the number of components of that orientation after deleting the faults. Proof. The depth bound follows from Theorem 3. The exact count c − 1 follows from Theorem 1. The minimum necessity follows from the component lower bound lemma.
6
Experimental Validation
The proof is supported by two validation layers. First, exhaustive proof mining covers all one- and two-fault placements for k = 5, . . . , 10. Second, large-scale validation covers k = 10, 25, 50, 100, 200 under random and structured placements. Each reported case checks 14
coverage, parent uniqueness, acyclicity, source reachability, fault exclusion, repair-edge count, and final depth. Table 2 gives the condensed exhaustive results split by fault count. For each tested k, both fault counts have 100% success, zero validation failures, maximum overhead two, and maximum repair count at most four. The six two-fault cases with exactly one good orientation are orthogonal-axis signatures; they require the balanced-smaller-first orientation within the tested family and attain depth k + 2. Table 2: Condensed exhaustive validation split by fault count. k
N
|F |
Cases
Max depth
Max repair
Min good
5 5 6 6 7 7 8 8 9 9 10 10
61 61 85 85 113 113 145 145 181 181 221 221
1 2 1 2 1 2 1 2 1 2 1 2
60 1,770 84 3,486 112 6,216 144 10,296 180 16,110 220 24,090
7 7 8 8 9 9 10 10 11 11 12 12
1 4 1 4 1 4 1 4 1 4 1 4
6 1 6 1 6 1 6 1 6 1 6 1
Table 3 gives the full distribution of depth-safe orientations in the exhaustive run. It shows why orientation selection is essential: most placements are easy, but the two-fault regime contains six cases with exactly one good orientation. Those six cases are precisely the orthogonal-axis hard signatures handled by Lemma 9. Table 3: Good-orientation counts in the exhaustive proof-mining run. |F |
1
2
4
5
6
7
8
1 2
0 6
0 12
0 190
0 332
22 2,891
0 39
778 58,498
Table 4 reports the large-scale random-fault validation with 1,000 trials per row. For k ≥ 25, MOEM succeeds in all trials, uses no fallback, keeps maximum depth at k + 2, and has average repair count close to |F |. Table 4: Large-scale random-fault validation of MOEM. k
N
|F |
Trials
Succ.
Fallback
Avg. comp.
Avg. repair
Avg. depth
Max depth
Avg. ms
10 10 25 25 50 50 100 100 200 200
221 221 1,301 1,301 5,101 5,101 20,201 20,201 80,401 80,401
1 2 1 2 1 2 1 2 1 2
1,000 1,000 1,000 1,000 1,000 1,000 1,000 1,000 1,000 1,000
100% 100% 100% 100% 100% 100% 100% 100% 100% 100%
15.7% 26.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0%
2.007 2.897 1.943 2.943 2.003 2.977 1.997 2.990 1.993 2.980
2.357 4.363 0.943 1.943 1.003 1.977 0.997 1.990 0.993 1.980
10.167 10.303 25.077 25.240 50.073 50.110 100.013 100.063 200.013 200.027
11 11 27 27 52 52 102 102 202 202
5.6 6.8 49.0 53.1 338.6 352.7 2058.8 2711.6 10936.3 15531.7
15
Table 5: Deterministic structured MOEM stress tests at k = 200, |F | = 2. Mode
Succ.
Fall.
Comp.
Repair
Max depth
axis trunk boundary leaf branch internal H1 close H2 close near boundary source adjacent two branches
100% 100% 100% 100% 100% 100% 100% 100%
0% 0% 0% 0% 0% 0% 0% 0%
3.0 1.0 2.0 2.0 2.0 3.0 4.0 3.0
2.0 0.0 1.0 1.0 1.0 2.0 3.0 2.0
202 200 202 202 202 201 202 202
Figure 3 summarizes the repair-count contrast. Fixed-orientation local repair can require a number of local adjustments that grows with k under trunk-like or same-cycle stress, whereas MOEM’s orientation selection keeps the corresponding close-generator repair count near |F | and preserves the k + 2 depth bound.
Figure 3: Repair-edge scalability: MOEM stays near |F |, while fixed-orientation stress repair grows with k. The hard O6 example is shown in Fig. 2. For k = 10 and F = {(3, 0), (0, 4)}, the faultpruned tree has five components, four external repair edges, and final depth 12 = k + 2. The simulation code and data used to generate the validation tables are available from the corresponding author upon reasonable request. 16
7
Discussion
The proved guarantees are intentionally separated from empirical observations. Theorems 1 and 3 prove non-redundancy, c−1 external repair-edge optimality for the selected orientation, and depth at most k + 2 for |F | ≤ 2. The validation results quantify typical repair counts, identify rare hard signatures, and check the implementation at larger sizes. The eight-orientation family is proved sufficient but not claimed minimal. The exhaustive data give a partial lower bound: the six one-good-orientation hard signatures are handled only by the balanced-smaller-first orientation. Hence any subfamily of the tested orientations that omits this orientation fails the k + 2 theorem on those cases. The main limitation is the restriction to |F | ≤ 2. The component-repair theorem itself is more general: for any fixed fault set and any selected orientation whose healthy component graph is connected, MOEM repairs the components using the minimum possible c−1 external crossing edges. Since the oriented broadcast trees have degree at most four, deleting q nonsource vertices creates at most 1 + 3q components, so the component-repair cost remains O(q). What remains open for q ≥ 3 is the depth-certificate theorem. Three collinear faults should be handled by nested axis-interval certificates; two off-axis faults plus one axis fault combine the O3 crossing with an axis-tail certificate unless the axis fault blocks the side entry. A natural conjecture is that a finite extension of the O3/O6 certificate library gives depth k + O(1) for three faults while preserving c − 1 repair optimality. As a concrete partial three-fault certificate, consider three collinear faults on the positive x-axis, F = {(a, 0), (b, 0), (c, 0)} with 1 ≤ a < b < c ≤ k. In the transverse sign-preference orientation, the lower-side entries remain healthy, and the deleted vertices create at most two bounded axis intervals and one outer tail. A bounded interval cut after layer p and ending before layer q can be attached through ((p + 1, −1), (p + 1, 0)) with certificate value at most (p + 2) + 1 + (q − p − 2) = q + 1 ≤ k + 1. The outer tail beyond c is attached through ((c + 1, −1), (c + 1, 0)) with value (c + 2) + 1 + (k − c − 1) = k + 2, with empty intervals ignored. Thus this representative three-fault family follows the same nested-interval logic as Lemma 7; the open cases are those where non-collinear faults block the side entries used by such interval certificates. Finally, the baseline choice is dictated by the objective. BFS rebuild and precomputed tree-diversity methods are useful resilience mechanisms, but they optimize connectivity or path diversity rather than the number of external component-crossing repair edges needed to preserve a damaged diameter-level tree. Fixed-orientation local repair is therefore the nearest same-objective baseline, and Fig. 3 shows the cost of omitting orientation selection.
8
Complexity
For each tested orientation, the fault-pruned forest can be computed in O(N ) time. Crossing edges can be found by scanning the four neighbors of each healthy vertex, also O(N ). For each tree component, all entry-vertex eccentricities can be computed in linear time in that component by the standard two-sweep tree-diameter method. Summed over all components, this preprocessing is O(N ) for one orientation. Since MOEM evaluates a constant number of orientations, the total running time remains O(N ) for the one- and two-fault setting, with 17
a moderate constant factor.
9
Conclusion
This paper introduced MOEM, a multi-orientation edge-minimum repair method for nonredundant one-to-all broadcasting in dense Gaussian networks. MOEM evaluates a constantsize family of Gaussian broadcast-tree orientations, selects a fault-aware candidate, contracts the fault-pruned tree into healthy components, and reconnects those components using an externally edge-minimum set of repair edges. For a selected orientation with c healthy components, exactly c − 1 external component-crossing repair edges are necessary and sufficient. For every one- or two-fault placement, the MOEM family contains an orientation admitting a repaired broadcast tree of depth at most k + 2. The proof uses certificate preservation, coordinate shielding templates, an explicit four-case O3 proof for separated off-axis pairs, and a five-component O6 certificate for the orthogonal-axis hard case. Exhaustive validation over 62,768 cases for k = 5 through 10, together with large-scale validation through k = 200, confirms the proof-derived behavior. The component-repair theorem extends to arbitrary fault counts when the healthy component graph is connected; the collinear three-fault example suggests how the certificate program can begin, while the main next step is to complete the depth-certificate classification for interacting non-collinear faults.
Acknowledgment The author thanks the Department of Computer Science, Faculty of Science, Kuwait University, for its support and research environment. This work did not receive a specific grant from any funding agency in the public, commercial, or not-for-profit sectors.
References [1] S. B. Akers and B. Krishnamurthy, “A group-theoretic model for symmetric interconnection networks,” IEEE Transactions on Computers, vol. 38, no. 4, pp. 555–566, Apr. 1989. [2] F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. San Mateo, CA, USA: Morgan Kaufmann, 1992. [3] W. J. Dally and B. Towles, Principles and Practices of Interconnection Networks. San Francisco, CA, USA: Morgan Kaufmann, 2004. [4] B. F. A. AlMohammad and B. Bose, “Fault-tolerant communication algorithms in toroidal networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 10, no. 10, pp. 976–983, Oct. 1999. [5] C. Martinez, R. Beivide, E. Stafford, M. Moreto, and E. M. Gabidulin, “Modeling toroidal networks with the Gaussian integers,” IEEE Transactions on Computers, vol. 57, no. 8, pp. 1046–1056, Aug. 2008. 18
[6] C. Martinez, E. Vallejo, R. Beivide, C. Izu, and M. Moreto, “Dense Gaussian networks: Suitable topologies for on-chip multiprocessors,” International Journal of Parallel Programming, vol. 34, no. 3, pp. 193–211, 2006. [7] M. Moreto, C. Martinez, R. Beivide, E. Vallejo, and M. Valero, “Hierarchical Gaussian topologies,” in Advanced Computer Architecture and Compilation for Embedded Systems (ACACES), 2006. [8] C. Martinez, E. Stafford, R. Beivide, and E. M. Gabidulin, “Modeling hexagonal constellations with Eisenstein–Jacobi graphs,” Problems of Information Transmission, vol. 44, no. 1, pp. 1–11, 2008. [9] C. Camarero, C. Martinez, and R. Beivide, “Symmetric interconnection networks from cubic crystal lattices,” arXiv:1311.2019, 2013. [10] C. Camarero, C. Martinez, E. Vallejo, and R. Beivide, “Projective networks: Topologies for large parallel computer systems,” arXiv:1512.07574, 2015. [11] M. Flahive and B. Bose, “The topology of Gaussian and Eisenstein–Jacobi interconnection networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 21, no. 8, pp. 1132–1142, Aug. 2010. [12] B. A. Albader, B. Bose, and M. Flahive, “Efficient communication algorithms in hexagonal mesh interconnection networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 1, pp. 69–77, Jan. 2012. [13] M. Flahive and B. Bose, “On resource placements in Gaussian and EJ networks,” IEEE Transactions on Computers, vol. 62, no. 3, pp. 623–626, Mar. 2013. [14] O. Alsaleh, B. Bose, and B. Hamdaoui, “One-to-many node-disjoint paths routing in dense Gaussian networks,” The Computer Journal, 2013, doi: 10.1093/comjnl/bxt142. [15] B. A. Albader and B. Bose, “Edge disjoint Hamiltonian cycles in Gaussian networks,” IEEE Transactions on Computers, vol. 65, no. 1, pp. 315–321, Jan. 2016. [16] 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. [17] S. Pasricha and N. Dutt, On-Chip Communication Architectures: System on Chip Interconnect. San Francisco, CA, USA: Morgan Kaufmann, 2008. [18] E. A. Monakhova, O. G. Monakhov, and A. Y. Romanov, “Routing algorithms for optimal degree-four circulant networks based on relative addressing,” IEEE Access, vol. 8, pp. 215010–215019, 2020. [19] T. Song, X. Jiang, and Y. Yang, “Gaussian-based optical networks-on-chip: Performance evaluation and analysis,” Sustainable Computing: Informatics and Systems, vol. 28, 2020.
19