arXiv CSopen access

Local Fault Repair of Perfect Resource Placements in Dense Gaussian Networks

Local Fault Repair of Perfect Resource Placements in Dense Gaussian Networks Bader A. Albader Department of Computer Science, Faculty of Science, Kuwait University, Kuwait

arXiv:2606.17527v1 [cs.DC] 16 Jun 2026

[email protected]

Abstract Perfect resource placement in dense Gaussian networks partitions the network into Lee balls centered at resource nodes. The fault-free placement problem is already classified; this paper studies the complementary post-deployment problem of repairing such placements after resource faults. The paper gives exact local repair theorems for the dense Gaussian placement generated by t + (t + 1)i; by conjugation and rotation symmetry, the same results hold for the companion generator (t + 1) + ti. For one failed resource, we prove failure-cell locality, derive the exact replacement number ρG (1) = 3 and ρG (t) = 2 for all t ≥ 2, and prove the sharp minimum-overlap formula ΩG (t) = t + 1 among minimum-size repairs. The overlap lower bound is proved from the corner structure of equal-size Lee balls in the rotated coordinates u = x + y and v = x − y, where Gaussian Lee balls become parity-constrained squares. For two failed resources, we prove exact additivity: every pair of failed resource cells requires exactly four local replacements for t ≥ 2, and four always suffice. The two-fault lower bound reduces all relevant resource displacements to two canonical neighboring cases and exhibits four mutually incompatible failed-cell corners in each case. For multifailure repairs, we prove a general inclusion–exclusion identity for overlap inside the failed region; hence the formula remains exact for arbitrary higher-order dense cores. When a canonical repair instance is certified to have maximum multiplicity three, the identity reduces to the compact correction Ωextra = P2 − A − C3 . A ground-truth audit over 7,494 Gaussian cases recomputes coverage from lattice geometry, verifies all exact formulas, and records reproducible multiplicity witnesses.

Keywords: Gaussian networks, resource placement, perfect dominating sets, local repair, fault tolerance, interconnection networks, Lee metric.

1

Introduction

Resource placement in interconnection networks asks how special service nodes, such as storage modules, I/O units, controllers, or replicated software services, should be distributed so that all processors have bounded access cost. A particularly strong placement is a perfect t-placement: every vertex is within distance t of exactly one resource. Equivalently, the radius-t balls centered at the resource nodes partition the network. 1

For Gaussian interconnection networks, the fault-free perfect-placement problem is already essentially complete. Gaussian networks were modeled using the Gaussian integers in [2], and Mary and Bose later classified the canonical perfect placements in Gaussian and Eisenstein–Jacobi networks [1]. This paper therefore does not attempt to rediscover the perfect placement. Instead, it starts after deployment: assume a classified perfect Gaussian placement is already active, and ask what happens after one or more resource nodes fail. Fault tolerance in graph-based networks has also been studied through complementary robustness parameters, including fault-tolerant metric dimension in multistage interconnection networks [7], conditional and extra diagnosability of interconnection networks [8], and fault-tolerant variants of domination such as power domination [9]. The broader domination literature also contains surveys and taxonomies of perfect, efficient, and independent domination terminology [10, 11]. In parallel, Gaussian-network research has studied structural and communication aspects of dense Gaussian topologies, including routing and broadcasting in on-chip multiprocessor networks [12]. The present paper is different in focus: the fault-free resource set is already a perfect dominating set, and the objective is not to design a globally fault-tolerant set in advance but to determine the exact local replacement cost after resource failures. The operational goal is local repair. When a resource fails, the vertices that were served by that resource become uncovered. Rather than globally recomputing a new perfect placement, the network may activate nearby replacement resources. This creates a new optimization problem: restore t-domination locally, minimize the number of replacement resources, and quantify the unavoidable overlap inside the failed cells. The contributions of this paper are as follows. • We formulate local fault repair for perfect resource placements in dense Gaussian networks as a post-deployment domination-recovery problem. • We show that the two Mary–Bose dense Gaussian generator families are isometric for local repair, so it suffices to prove the results for t + (t + 1)i. • We prove locality: after one resource fails, the only uncovered vertices are the vertices of the failed Lee ball, and useful replacement candidates lie within distance 2t. • We prove the exact one-failure replacement numbers ρG (1) = 3 and ρG (t) = 2 for all t ≥ 2. • We prove the exact one-failure minimum-overlap formula ΩG (t) = t+1 among minimumsize repairs. • We prove exact two-fault additivity for t ≥ 2: every pair of failed Gaussian resource cells requires exactly four local replacements, and four always suffice. • We prove a general multi-failure overlap identity using exact inclusion–exclusion over replacement multiplicities in the failed region. • We give a certificate-based triple-core specialization for canonical local repairs and include an independent ground-truth audit of 7,494 Gaussian cases, recomputing coverage and overlap directly from lattice geometry. 2

Table 1 summarizes the main formal results.

Setting One failed resource

One failed resource, minimum overlap Two failed resources

General multifailure overlap Certified triple-core instances

2

Table 1: Main results and proof locations. Result Proof method ρG (1) = 3 and ρG (t) = 2 for Lee-ball extremal points and ext≥2 plicit diagonal/anti-diagonal repairs ΩG (t) = t + 1 for t ≥ 2 Rotated-coordinate slice lower bound and tight interface construction (2) ρG (t, ∆) = 4 for every pair Rotated-square displacement reand every t ≥ 2 duction and four incompatible corners P Exact vertexwise inclusion– O(R) = j≥2 (−1)j Pj (R) exclusion over replacement multiplicities Ωextra = P2 − A − C3 when Conditional corollary plus mulmax µR ≤ 3 tiplicity certificate

Gaussian Preliminaries

The Gaussian integer grid is Z[i] = {x + yi : x, y ∈ Z} with adjacency defined by differences ±1 and ±i. In coordinate form we write vertices as integer pairs (x, y), and the graph distance from the origin is the Lee distance dG ((0, 0), (x, y)) = |x| + |y|.

(1)

The radius-t ball centered at c is Bt (c) = {u : dG (u, c) ≤ t},

(2)

|Bt (0)| = 2t2 + 2t + 1.

(3)

and Definition 1 (Perfect t-placement). A resource set S in a finite Gaussian network is a perfect t-placement if every vertex u is covered by exactly one resource ball: |{s ∈ S : dG (u, s) ≤ t}| = 1.

(4)

Theorem 1 (Gaussian case of Mary–Bose classification [1]). Let Gα be a Gaussian network generated by α. Then Gα has a perfect t-dominating set exactly in the canonical divisibility cases, generated by associates of t + (t + 1)i. (5) In these cases the resource set is a translate of the corresponding ideal placement. 3

Proposition 1 (Companion-generator symmetry). The two dense Gaussian generator families α1 = t + (t + 1)i and α2 = (t + 1) + ti are equivalent for the local repair problem. The map Φ(z) = iz is an isometry of the Gaussian grid that sends α1 to α2 . Consequently, all local replacement numbers and all overlap identities proved for t + (t + 1)i hold unchanged for the companion generator (t + 1) + ti. Proof. For z = x + yi, Φ(z) = i(x − yi) = y + xi, so Φ swaps the two integer coordinates. Therefore dG (Φ(z), Φ(w)) = |yz − yw | + |xz − xw | = dG (z, w). Also Φ(t + (t + 1)i) = i(t − (t + 1)i) = (t + 1) + ti. Thus Φ maps radius-t Lee balls to radius-t Lee balls, maps perfect-placement cells in the first dense family to the corresponding cells in the companion family, and preserves coverage multiplicities. Since the repair model is defined only through these metric and incidence relations, the two families have identical local repair behavior. By Proposition 1, it suffices to present the proofs for one representative of the two dense Gaussian generator families. Throughout the paper we take the quotient induced by α = t + (t + 1)i,

(6)

N = t2 + (t + 1)2 = 2t2 + 2t + 1.

(7)

so that the network size is

3

Fault-Recovery Model

Let S be a perfect t-placement and let F ⊆ S be the set of failed resource nodes. The active resources are S \ F . A local repair activates a replacement set R of non-failed nodes. The repaired resource set is S ′ = (S \ F ) ∪ R. (8) For one failed resource r, a repair is valid if Bt (r) ⊆

[

Bt (x).

(9)

x∈R

For several failed resources F = {r1 , . . . , rq }, the failed region is U (F ) =

q [

Bt (rj ),

(10)

j=1

and a repair is valid if U (F ) is covered by the replacement balls. For a one-failure repair, define ρG (t) to be the minimum number of replacements needed to restore domination. Among minimum-size repairs, define ΩG (t) to be the minimum number of vertices in the failed cell covered by at least two replacement balls. 4

4

Locality Theorems

Theorem 2 (Failure-cell locality). Let S be a perfect t-placement and let r ∈ S fail. Then the only vertices that can become uncovered are the vertices in Bt (r). Proof. Since S is a perfect t-placement, every vertex u is covered by exactly one resource in S. If u ∈ / Bt (r), then r was not the resource covering u. Thus the unique resource that covered u remains active after r is removed. Only vertices originally covered by r, namely the vertices in Bt (r), can become uncovered. Theorem 3 (Candidate locality). If a replacement node x satisfies dG (x, r) > 2t, then Bt (x) ∩ Bt (r) = ∅. Hence x cannot contribute to repairing the failed cell Bt (r). Proof. If u ∈ Bt (x) ∩ Bt (r), then by the triangle inequality, dG (x, r) ≤ dG (x, u) + dG (u, r) ≤ 2t,

(11)

contradicting dG (x, r) > 2t.

5

One-Fault Exact Local Repair

By translation, assume that the failed resource is the origin. The failed cell is Bt (0). Lemma 1 (One replacement is impossible). No single replacement node x ̸= 0 can cover the entire failed cell Bt (0). Proof. If Bt (0) ⊆ Bt (x), then the two finite balls have the same size, hence Bt (0) = Bt (x). The four extreme points (t, 0), (−t, 0), (0, t), and (0, −t) determine the center of a Lee ball uniquely, forcing x = 0. This contradicts that the failed resource itself is unavailable as a replacement. The constructive proof uses rotated coordinates v = x − y.

u = x + y,

(12)

The Lee ball becomes the parity sublattice of an axis-aligned square: Bt (0) = {(x, y) : |u| ≤ t, |v| ≤ t, u ≡ v

5

(mod 2)}.

(13)

Figure 1: Rotated-coordinate representation. The Lee ball Bt (0) in (x, y) coordinates becomes a parity-constrained square in (u, v) coordinates. This geometric picture is the basis for all one-fault and two-fault lower bounds. Lemma 2 (t = 1 exception). For t = 1, the failed cell B1 (0) has five vertices, two replacement balls cannot cover it, and three can. Hence ρG (1) = 3. Proof. The failed cell is B1 (0) = {(0, 0), (1, 0), (−1, 0), (0, 1), (0, −1)}.

(14)

A radius-one ball centered at a nonzero node covers the origin only when the center is one of the four neighbors of the origin, and then it covers exactly the origin and its own center inside B1 (0). A radius-one ball centered at a diagonal node covers two boundary vertices but not the origin; a distance-two axial center covers one boundary vertex. Therefore two candidates cannot cover all five vertices: either the origin is uncovered, or at most three of the four boundary vertices are covered. Three replacements suffice, for example R = {(−1, −1), (0, 1), (2, 0)}.

(15)

These cover the two negative boundary vertices, the origin and north boundary vertex, and the east boundary vertex, respectively.

6

Figure 2: Special case t = 1. Two replacement balls cannot cover all five vertices of the failed cell, while the repair set {(−1, −1), (0, 1), (2, 0)} covers the cell. Theorem 4 (Two-replacement construction). For t ≥ 2 and every 1 ≤ a ≤ t, the diagonal pair Ra+ = {(−a, −a), (t − a, t − a)} (16) covers Bt (0). The anti-diagonal pair Ra− = {(−a, a), (t − a, −t + a)}

(17)

also covers Bt (0). Proof. It is enough to prove the diagonal case. In the coordinates (12), the ball centered at (−a, −a) contains a failed-cell point exactly when max{|u + 2a|, |v|} ≤ t.

(18)

Inside Bt (0), the inequality |v| ≤ t already holds, so this reduces to u ≤ t − 2a. Similarly, the ball centered at (t − a, t − a) contains a failed-cell point exactly when u ≥ t − 2a. Every failed-cell point satisfies one of these two inequalities, so the two balls cover Bt (0). Reflection gives the anti-diagonal construction. Example 1 (Worked t = 2 repair). For t = 2, choose a = 1 in Theorem 4. The repair pair is R = {(−1, −1), (1, 1)}. In rotated coordinates, the two centers are (−2, 0) and (2, 0). For any point of B2 (0), the first replacement ball covers exactly the side with u ≤ 0, while the second covers exactly the side with u ≥ 0. Their common interface is the parity-valid slice u = 0, containing the three vertices (−1, 1), (0, 0), (1, −1). Thus the concrete t = 2 instance already shows both the two-replacement coverage mechanism and the sharp overlap value t + 1 = 3. 7

Figure 3: Diagonal one-fault repair. The two replacement balls split the failed square at an interface slice; the two balls overlap on exactly t + 1 parity-valid vertices. Theorem 5 (Exact one-fault Gaussian repair number). For dense Gaussian networks with canonical perfect t-placements, ( 3, t = 1, ρG (t) = (19) 2, t ≥ 2. Proof. For t ≥ 2, Theorem 4 gives a two-replacement repair, while Lemma 1 rules out one replacement. For t = 1, Lemma 2 gives necessity and sufficiency of three replacements.

6

Minimum Overlap for One Fault

Let a two-replacement repair be R = {p, q}. The overlap inside the failed cell is |Bt (p) ∩ Bt (q) ∩ Bt (0)|.

(20)

Lemma 3 (Corner pairing in a two-square cover). Let two radius-t Gaussian balls centered away from the origin cover Bt (0). In rotated coordinates, their two parity-constrained squares cover the four corners of Q0 . Then, up to interchanging u and v and reflecting coordinates, one square covers the two left corners of Q0 and the other covers the two right corners of Q0 . Proof. A radius-t square distinct from Q0 cannot contain two opposite corners of Q0 . Indeed, the only axis-aligned square of side length 2t containing both (−t, −t) and (t, t) is Q0 itself, and the same holds for the other opposite pair (−t, t) and (t, −t). Since the failed resource at the origin is unavailable, neither replacement square can cover an opposite-corner pair. Thus each replacement square can cover at most two adjacent corners of Q0 . Because the two squares together must cover all four corners, their covered corner pairs must be complementary adjacent pairs. Up to symmetry, these are the left pair and the right pair. The other possibility, bottom and top, is obtained by interchanging u and v. Lemma 4 (Forced interface slice). Let two replacement balls cover Bt (0) for t ≥ 2. Then their overlap inside Bt (0) contains a complete parity-valid slice of Bt (0) containing exactly t + 1 vertices. 8

Proof. By Lemma 3, it is enough to consider the case in which one replacement square covers the left corners of Q0 and the other covers the right corners. Write their rotated centers as (U1 , V1 ) and (U2 , V2 ). To contain both left corners (−t, −t) and (−t, t), the first square must have V1 = 0 and U1 ≤ 0. To contain both right corners (t, −t) and (t, t), the second square must have V2 = 0 and U2 ≥ 0. Their projections on the u-axis are the intervals [U1 − t, U1 + t] and [U2 − t, U2 + t]. Since the two balls cover every vertex of Q0 , these intervals cover every integer slice −t ≤ u ≤ t; hence U2 − U1 ≤ 2t. (21) Therefore the overlap of the two u-intervals contains the integer interval [U2 − t, U1 + t].

(22)

This interval is nonempty. Because V1 = V2 = 0, both squares contain the full v-range [−t, t] on every slice whose u-coordinate lies in this interval. The centers of Gaussian vertices satisfy Uj ≡ Vj (mod 2) because Uj = xj + yj and Vj = xj −yj have the same parity for every integer Gaussian vertex (xj , yj ). Since V1 = V2 = 0 and 0 is even, the congruences U1 ≡ V1 and U2 ≡ V2 (mod 2) imply that both U1 and U2 are even. If the interval has more than one integer value, it contains a value c ≡ t (mod 2). If the interval has exactly one value, then U2 − U1 = 2t and that value is c = U1 + t = U2 − t, again satisfying c ≡ t (mod 2). Thus the overlap contains a full slice u = c with c ≡ t (mod 2). On such a slice, the parity-valid values of v in [−t, t] are −t, −t + 2, . . . , t,

(23)

so the slice contains exactly t + 1 Gaussian vertices. Hence the two replacement balls overlap inside Bt (0) on at least t + 1 vertices. Theorem 6 (Exact Gaussian minimum-overlap formula). For t ≥ 2, among all minimumsize one-failure repairs, ΩG (t) = t + 1. (24) Proof. By Theorem 5, a minimum repair has two replacements. Lemma 4 shows that any two-replacement repair has at least t + 1 overlapped vertices in the failed cell. The construction in Theorem 4 is tight: its two balls meet inside Bt (0) exactly on the interface slice u = t − 2a, which has t + 1 parity-valid vertices. Therefore the minimum overlap is exactly t + 1.

7

Exact Two-Fault Additive Repair

For two failed resources r1 , r2 , let U2 (r1 , r2 ) = Bt (r1 ) ∪ Bt (r2 ).

9

(25)

Figure 4: Two-fault side-neighbor obstruction. Four marked corners p1 , . . . , p4 force four distinct replacement balls in the side-neighbor case of Lemma 6.

7.1

Rotated-square representation

We use the rotated coordinates v = x − y.

u = x + y,

(26)

In these coordinates the Lee ball centered at (U0 , V0 ) is the parity-constrained square Qt (U0 , V0 ) = {(u, v) : |u − U0 | ≤ t, |v − V0 | ≤ t, u ≡ v (mod 2)}.

(27)

In the dense Gaussian perfect placement generated by t + (t + 1)i, the resource-center lattice has rotated-coordinate generators e1 = (2t + 1, −1),

e2 = (−1, −(2t + 1)).

(28)

Theorem 7 (Two-fault additive construction). For t ≥ 2, any two failed Gaussian resource cells can be repaired using at most four replacement nodes. Proof. Translate the two-replacement construction of Theorem 4 to r1 and to r2 . The first translated pair covers Bt (r1 ) and the second translated pair covers Bt (r2 ). Their union therefore covers U2 (r1 , r2 ). Hence four replacements always suffice. 10

Lemma 5 (Relevant neighboring displacements). Let t ≥ 2. If a single replacement ball can intersect both failed cells, then, up to sign, rotation, and reflection of the rotated square coordinates, the displacement between the two failed resource centers is one of (2t + 1, −1)

or

(2t + 2, 2t).

(29)

Proof. Let the two failed resource centers have rotated displacement D = (Du , Dv ). A replacement ball of radius t can intersect both failed cells only if the two failed radius-t squares are within 2t of one another in the L∞ metric. Hence ∥D∥∞ ≤ 4t.

(30)

D = m(2t + 1, −1) + n(−1, −(2t + 1)),

(31)

Write where m, n ∈ Z. Put a = 2t + 1. Then Du = am − n,

Dv = −m − an.

(32)

Solving gives m=

aDu − Dv , a2 + 1

n=−

Du + aDv . a2 + 1

(33)

Since |Du |, |Dv | ≤ 4t, |aDu − Dv | ≤ 4t(a + 1) = 8t(t + 1) < 2(a2 + 1),

(34)

for a = 2t + 1. Therefore |m| < 2. Similarly, |n| < 2. Hence m, n ∈ {−1, 0, 1}. The nonzero possibilities are (±1, 0), (0, ±1), and (±1, ±1). The cases (±1, 0) and (0, ±1) are equivalent under the isometry of the rotated-square model that interchanges the uand v-axes and then reflects signs as needed. Therefore they give the same side-neighbor displacement type (2t + 1, −1) up to the allowed lattice symmetries. The cases (±1, ±1) are likewise equivalent and give the displacement type (2t + 2, 2t). Lemma 6 (Four incompatible corners for side-neighbor cells). Let the two failed cells have centers C1 = (0, 0), C2 = (2t + 1, −1) (35) in rotated coordinates. Then any repair requires at least four replacement balls. Proof. Let Q1 = Qt (C1 ) and Q2 = Qt (C2 ). Consider the four failed-cell corner vertices p1 = (−t, −t), p3 = (t + 1, −t − 1),

p2 = (t, t), p4 = (3t + 1, t − 1).

(36)

The points p1 , p2 are opposite corners of Q1 , and p3 , p4 are opposite corners of Q2 . All four points satisfy the required parity condition u ≡ v (mod 2). A radius-t square can cover two points only if their L∞ distance is at most 2t. Moreover, the only radius-t square containing two opposite corners of the same failed square is the failed 11

square itself. Hence p1 and p2 can be covered together only by the failed center C1 , and p3 and p4 can be covered together only by the failed center C2 . Both centers are unavailable. For the cross pairs, ∥p1 − p3 ∥∞ = 2t + 1, ∥p2 − p3 ∥∞ = 2t + 1,

∥p1 − p4 ∥∞ = 4t + 1, ∥p2 − p4 ∥∞ = 2t + 1.

(37)

Each value is greater than 2t. Therefore no valid radius-t replacement ball can cover any cross pair. Thus the four vertices p1 , p2 , p3 , p4 must be covered by four distinct replacement balls, and at least four replacements are necessary. Lemma 7 (Four incompatible corners for diagonal-neighbor cells). Let the two failed cells have centers C1 = (0, 0), C2 = (2t + 2, 2t) (38) in rotated coordinates. Then any repair requires at least four replacement balls. Proof. Let Q1 = Qt (C1 ) and Q2 = Qt (C2 ). Consider the four failed-cell corner vertices q2 = (t, −t), q4 = (3t + 2, t).

q1 = (−t, t), q3 = (t + 2, 3t),

(39)

The points q1 , q2 are opposite corners of Q1 , and q3 , q4 are opposite corners of Q2 . Again, all four points satisfy u ≡ v (mod 2). The pair q1 , q2 can be covered together only by the failed center C1 , and the pair q3 , q4 can be covered together only by the failed center C2 . Both centers are unavailable. For the cross pairs, ∥q1 − q3 ∥∞ = 2t + 2, ∥q2 − q3 ∥∞ = 4t,

∥q1 − q4 ∥∞ = 4t + 2, ∥q2 − q4 ∥∞ = 2t + 2.

(40)

Each value is greater than 2t for t ≥ 2. Therefore no valid replacement ball can cover a cross pair. The four vertices q1 , q2 , q3 , q4 require four distinct replacement balls, and every repair has size at least four. Lemma 8 (Far failed cells require independent repairs). If two failed resource centers have rotated displacement D with ∥D∥∞ > 4t, (41) then any replacement ball intersects at most one failed cell. Consequently, at least four replacement balls are required. Proof. If a radius-t replacement ball intersected both failed cells, then the two failed radius-t squares would be within 2t of each other in the L∞ metric. Since each failed cell itself has radius t, this would imply ∥D∥∞ ≤ 4t, contradicting the hypothesis. Thus every replacement ball can contribute to at most one failed cell. By Theorem 5, one failed Gaussian cell requires at least two replacement balls for t ≥ 2. Therefore two such cells require at least four replacements. 12

Theorem 8 (Exact two-fault Gaussian additivity). For every t ≥ 2 and every pair of failed resource centers in the dense Gaussian perfect placement, (2)

ρG (t, ∆) = 4.

(42)

(2)

Proof. The upper bound ρG (t, ∆) ≤ 4 follows from Theorem 7. It remains to prove the lower bound. Let D be the rotated displacement between the two failed resource centers. If ∥D∥∞ > 4t, Lemma 8 gives the lower bound four. Otherwise, ∥D∥∞ ≤ 4t. By Lemma 5, up to the symmetries of the Gaussian lattice, D is either (2t + 1, −1) or (2t + 2, 2t). In the first case, Lemma 6 gives the lower bound four. In the second case, Lemma 7 gives the lower bound four. Thus every two-fault repair requires at least four replacement balls. Since four always (2) suffice, the exact value is ρG (t, ∆) = 4.

8

Multi-Fault Overlap Accounting

Figure 5: Multi-fault overlap and dense cores. For q = 3 or q = 4, overlapping replacement squares can create vertices covered by three or more balls; these vertices are exactly what the inclusion–exclusion correction accounts for. Let U (F ) =

[

Bt (r)

(43)

r∈F

be the failed region and let R be any valid local replacement set. For z ∈ U (F ) define the replacement multiplicity µR (z) = |{x ∈ R : z ∈ Bt (x)}|. (44)

13

Since R is a valid repair, µR (z) ≥ 1 for all z ∈ U (F ). The true overlap mass inside the failed region is X O(R) = (µR (z) − 1). (45) z∈U (F )

For j ≥ 2, define the j-fold coverage mass X µR (z)

Pj (R) =

z∈U (F )

j

.

Lemma 9 (Vertexwise binomial identity). For every integer m ≥ 1,   m X j m . m−1= (−1) j j=2

(46)

(47)

Proof. The binomial identity m X

  m (−1) =0 j j=0 j

(48)

holds for m ≥ 1. Separating the j = 0 and j = 1 terms gives   m X j m 1−m+ (−1) = 0, j j=2

(49)

which is equivalent to (47). Theorem 9 (Exact multi-failure overlap identity). For any valid local repair R of any failed resource set F , M X (−1)j Pj (R), (50) O(R) = j=2

where M = max µR (z).

(51)

z∈U (F )

Proof. Apply Lemma 9 to m = µR (z) at each failed-region vertex z ∈ U (F ) and sum over all z. Exchanging the finite sums gives X O(R) = (µR (z) − 1) z∈U (F )

=

R (z) X µX

j

(−1)

z∈U (F ) j=2



 µR (z) j

M X X µR (z) j = (−1) j j=2 z∈U (F )

=

M X (−1)j Pj (R). j=2

14

(52)

Corollary 1 (Triple-core specialization). If a repair set R satisfies max µR (z) ≤ 3,

(53)

O(R) = P2 (R) − P3 (R).

(54)

z∈U (F )

then Moreover, if C3 (R) denotes the number of failed-region vertices covered by exactly three replacement balls, then P3 (R) = C3 (R) and O(R) = P2 (R) − C3 (R).

(55)

Proof. If M ≤ 3, Theorem 9 has only the j = 2 and j = 3 terms. Also, when no vertex
µR (z) has multiplicity above three, is one exactly at vertices of multiplicity three and zero 3 elsewhere. Hence P3 (R) = C3 (R). Theorem 10 (Certified dense-core correction). For any canonical local repair instance for which the ground-truth certificate verifies max µR (z) ≤ 3,

(56)

Ωextra (R) = P2 (R) − A(R) − C3 (R).

(57)

z∈U (F )

the dense-core correction is exactly Proof. By Corollary 1, O(R) = P2 (R) − C3 (R). Subtracting the additive prediction A(R) gives (57). Remark 1 (Scope of the certified specialization). Theorem 9 is unconditional and applies to every local repair. The compact dense-core formula in Theorem 10 is a specialization for instances whose certificate proves M ≤ 3. This distinction prevents the multi-failure result from relying on an unproved universal pattern classification: if a future repair family produces M > 3, the same theorem still applies with the additional P4 , P5 , . . . terms.

9

Validation and Audit

Table 2 verifies the exact one-failure construction and minimum-overlap values for representative radii. Table 3 verifies the multiplicity certificate required to specialize the general inclusion–exclusion identity to the triple-core formula. Every reported quantity is recomputed from raw lattice geometry. Table 2: Exact one-failure validation for representative radii. t N candidates min K best overlap 1 2 5 10 15 20

5 13 61 221 481 841

12 40 220 840 1860 3280

3 2 2 2 2 2 15

0 3 6 11 16 21

Table 3: Dense-core audit summary. All quantities were recomputed from lattice geometry. Faults q

Cases Extra cases

Max extra

Max cover C3 max

Residual max

≥ 4-cover cases

1 2 3 4 5 6

6 288 1800 1800 1800 1800

0 0 56 182 382 573

0 0 15 24 58 56

2 2 3 3 3 3

0 0 1 2 8 8

0 0 0 0 0 0

0 0 0 0 0 0

Total

7494

1193

58

3

8

0

0

10

Discussion

The Gaussian-only formulation gives a focused post-deployment repair problem rather than another classification of perfect placements. The companion dense generator (t + 1) + ti is not omitted as a separate case: Proposition 1 shows that it is the image of t + (t + 1)i under a Gaussian-grid isometry, so the local repair results transfer unchanged. The one-fault replacement and overlap formulas are exact, and the two-fault repair number is exact for all t ≥ 2 by the rotated-square corner-incompatibility argument. The multi-failure result has a different role. It is not needed to prove the one- or two-fault replacement numbers; rather, it gives exact overlap accounting when several local repairs interact. The final theorem is a general inclusion–exclusion identity over replacement multiplicities, so it remains correct even if a non-canonical repair produces fourth- or higher-order overlaps. The simpler dense-core expression P2 −A−C3 is used only when the accompanying certificate verifies maximum multiplicity three.

11

Conclusion

This paper introduced local fault repair for perfect resource placements in dense Gaussian networks. The two dense Gaussian generator families in the Mary–Bose classification are isometric for this problem, so the proofs for t + (t + 1)i also cover the companion generator (t + 1) + ti. After a resource node fails, the uncovered region is exactly one Lee ball, and all useful replacements lie in a radius-2t neighborhood. The exact one-fault repair number is 3 for t = 1 and 2 for t ≥ 2, and the minimum overlap among minimum-size repairs is t + 1. For two faults, four local replacements are always sufficient and, for t ≥ 2, always necessary. The lower bound follows from the rotated-square representation of Gaussian Lee balls and a finite reduction to two neighboring displacement types. For multi-failure repairs, the overlap inside the failed region is given by an exact inclusion–exclusion identity over replacement multiplicities. When the canonical repair certificate verifies maximum multiplicity three, this reduces to the dense-core correction P2 − A − C3 .

16

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] M. Flahive and B. Bose, “On resource placement in Gaussian and EJ interconnection networks,” IEEE Transactions on Computers, vol. 62, no. 3, pp. 623–626, Mar. 2013. [2] C. Martı́nez, R. Beivide, E. Stafford, M. Moretó, and E. M. Gabidulin, “Modeling toroidal networks with the Gaussian integers,” IEEE Transactions on Computers, vol. 57, no. 8, pp. 1046–1056, Aug. 2008. [3] M. M. Bae and B. Bose, “Resource placement in torus-based networks,” IEEE Transactions on Computers, vol. 46, no. 10, pp. 1083–1092, Oct. 1997. [4] M. Livingston and Q. F. Stout, “Perfect dominating sets,” in Proceedings of the TwentyFirst Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Congressus Numerantium, vol. 79, pp. 187–203, 1990. [5] P. Ramanathan and S. Chalasani, “Resource placement with multiple adjacency constraints in k-ary n-cubes,” IEEE Transactions on Parallel and Distributed Systems, vol. 6, no. 5, pp. 511–519, May 1995. [6] N.-F. Tzeng and G.-L. Feng, “Resource allocation in cube network systems based on the covering radius,” IEEE Transactions on Parallel and Distributed Systems, vol. 7, no. 4, pp. 328–342, Apr. 1996. [7] S. Prabhu, V. Manimozhi, M. Arulperumjothi, and S. Klavžar, “Twin vertices in faulttolerant metric sets and fault-tolerant metric dimension of multistage interconnection networks,” Applied Mathematics and Computation, vol. 420, Art. 126897, May 2022. [8] E. Cheng, Y. Mao, K. Qiu, and Z. Shen, “A general approach to deriving diagnosability results of interconnection networks,” Journal of Interconnection Networks, vol. 22, no. 3, Art. 2250011, 2022. [9] L. Girish and K. Somasundaram, “Bound for the k-fault-tolerant power-domination number,” Symmetry, vol. 16, no. 7, Art. 781, 2024. [10] W. F. Klostermeyer, “A taxonomy of perfect domination,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 18, nos. 1–2, pp. 105–116, 2015. [11] W. Goddard and M. A. Henning, “Independent domination in graphs: A survey and recent results,” Discrete Mathematics, vol. 313, no. 7, pp. 839–854, 2013.

17

[12] C. Martı́nez, E. Vallejo, R. Beivide, C. Izu, and M. Moretó, “Dense Gaussian networks: Suitable topologies for on-chip multiprocessors,” International Journal of Parallel Programming, vol. 34, pp. 193–211, 2006. [13] M. Flahive and B. Bose, “The topology of Gaussian and Eisenstein–Jacobi interconnection networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 21, no. 8, pp. 1132–1142, Aug. 2010.

18