Closed-Form and Constant-Time New-Source Selection for Fault-Tolerant Broadcasting in Dense Eisenstein–Jacobi Networks arXiv:2606.18714v1 [cs.DC] 17 Jun 2026
Bader Albader Department of Computer Science, Kuwait University, Kuwait [email protected]
Abstract Fault-tolerant broadcasting in dense Eisenstein–Jacobi networks requires an efficient recovery mechanism when faulty nodes interrupt the original broadcast structure. A recently published re-rooting-based broadcasting method for dense Eisenstein–Jacobi networks proves that, for any two faulty nodes, recovery can be performed by selecting a new source that is at maximum graph distance from both faults. However, the recovery step still benefits from a direct method that selects such a source without scanning the network or testing all boundary candidates. This paper develops a selfcontained closed-form and constant-time new-source counting and selection method for dense Eisenstein–Jacobi networks. The two-fault problem is translated to an equivalent boundary-intersection problem involving the origin and a difference node. The distance-t boundary, where t is the network diameter, is partitioned into six directed sides of the Eisenstein–Jacobi hexagon. Because the network is a quotient network, the intersection equations must be solved modulo the defining Eisenstein–Jacobi lattice. Therefore, the proposed algorithms evaluate seven possible quotient-lattice shifts together with the 6×6 side pairs, giving at most 7·6·6 = 252 algebraic systems. For faults 0 and A, the first algorithm counts all valid new sources exactly. For two arbitrary faults, the second algorithm selects one valid new source by solving translated side-pair systems, verifying the candidate, and shifting it back. Each system is either a nonparallel two-by-two linear system with at most one candidate, or a parallel system whose feasible candidates form an integer interval. Since the number of systems is fixed, both algorithms run in O(1) time under the fixed-word arithmetic model. Computational validation over 500,000 sampled fault pairs and 40,000 re-rooting trials confirms that the direct selector always returns a valid new source and that the recovered broadcast reaches all non-faulty nodes in the tested settings.
Keywords: Dense Eisenstein–Jacobi networks, fault-tolerant broadcasting, re-rooting, newsource selection, interconnection networks, constant-time algorithms, hexagonal networks, graph distance.
1
1
Introduction
Interconnection networks are widely used as models for communication in parallel and distributed systems. Their topology directly affects routing complexity, broadcasting time, diameter, scalability, and robustness under failures. Algebraic interconnection networks are especially useful because their nodes and links can be described by compact coordinate rules. Gaussian and Eisenstein–Jacobi networks are two important examples. Both are constructed from quotient rings, both admit modular coordinate descriptions, and both have small diameter relative to the number of nodes [1, 2, 3]. Recent work on circulant and algebraic network topologies for networks-on-chip continues to emphasize coordinate-based routing, small diameter, deadlock-free communication, and resilience under faults [14, 16, 17, 18, 20, 21]. Dense Eisenstein–Jacobi networks form a degree-six family of hexagonal networks. In this paper, the network is denoted by EJt , where t is the network diameter. The dense network is generated by α = (t + 1) + tω, (1) where ω is an Eisenstein–Jacobi unit satisfying ω 2 + ω + 1 = 0. The number of nodes is N = 3t2 + 3t + 1.
(2)
Equivalently, if the original network parameter is written as n = t+1, then N = 3n2 −3n+1. This paper uses t throughout because it is the diameter notation used in the Eisenstein– Jacobi re-rooting framework. In a fault-free dense Eisenstein–Jacobi network, a source can broadcast to all nodes within t steps. When one or more nodes fail, part of the original broadcast structure may become unusable. The re-rooting method addresses this problem by choosing a new source that is farthest from the faulty nodes. For two faulty nodes A and B, the target condition is dEJ (N S, A) = t,
dEJ (N S, B) = t.
(3)
The published Eisenstein–Jacobi re-rooting paper proves the existence of such a node for two faulty nodes and uses this fact to recover the broadcast [13]. The remaining algorithmic question is how to select such a source as directly as possible. This paper answers that question in a self-contained way for dense Eisenstein–Jacobi networks. The key observation is that the distance-t boundary is a six-sided hexagon. Therefore, the valid-source problem can be reduced to a fixed set of side-pair intersections. The construction developed here is native to the Eisenstein–Jacobi geometry: it uses six boundary sides, 252 translated side-pair systems, and the Eisenstein–Jacobi graph distance in (10). Given two faulty nodes A and B, define the difference node C = modEJt (B − A).
(4)
By translation invariance, it is enough to find a point P satisfying dEJ (P, 0) = t,
dEJ (P, C) = t.
(5)
The new source is then obtained by shifting back: N S = modEJt (A + P ). 2
(6)
Thus, the selection problem becomes an intersection problem between two distance-t boundaries. The main contributions of this paper are as follows. • The distance-t boundary of EJt is partitioned into six directed sides, each containing exactly t nodes. • For faults 0 and A, the exact number of valid new sources is expressed as a closed finite sum of translated side-pair intersection counts over seven quotient shifts and thirty-six side pairs. • A constant-time counting algorithm is developed for faults 0 and A, and a direct sidepair selector is developed for two arbitrary faulty nodes. Both use the same fixed set of 252 translated side-pair systems. • The correctness of the selector is proved through soundness and completeness theorems. • The time complexity of both the counting algorithm and the selection algorithm is shown to be O(1) because each checks at most 252 translated side pairs, independent of t, N , or the boundary size 6t. • Worked examples and figures are included to illustrate the counting and selection procedures. The rest of the paper is organized as follows. Section 2 reviews related work. Section 3 gives the network model and distance notation. Section 4 defines the six-side boundary partition. Section 5 gives the exact number of valid new sources for faults 0 and A. Section 6 presents the constant-time selector for arbitrary fault pairs. Section 7 compares the complexity with search-based alternatives. Section 8 presents the computational validation results. Section 9 discusses the role of the result within the re-rooting framework, and Section 10 concludes the paper.
2
Related Work
Gaussian and Eisenstein–Jacobi interconnection networks were introduced and analyzed as quotient-ring networks with strong symmetry and compact algebraic descriptions [1]. Dense Gaussian networks and Gaussian coordinate representations were later studied for multiprocessor and network-on-chip settings, where small diameter and regular degree are important design properties [2, 3]. Hierarchical extensions and related circulant constructions show that algebraic network families remain useful for large-scale interconnection design [4]. Recent research on circulant and algebraic interconnection networks shows that compact coordinate representations remain useful for scalable routing. Monakhov et al. studied adaptive shortest-path search for networks-on-chip based on circulant topologies, while Romanov et al. investigated routing algorithms for two-dimensional optimal circulant NoCs [14, 15]. Monakhova et al. later developed relative-addressing routing algorithms for optimal degreefour circulant networks, and Sukhov et al. proposed a virtual coordinate system for circulant NoC routing [17, 18]. 3
Fault tolerance is also a central concern in networks-on-chip and related interconnection systems. Surveys and monographs on on-chip communication describe how node and link failures can affect routing reliability and system-level performance [8, 9, 10]. Recent NoC studies continue to investigate fault-tolerant and adaptive mechanisms, including permanentfault router architectures, deadlock-free routing for circulant NoCs, fault-tolerant application mapping, and quality-of-service-aware routing methods [19, 16, 20, 21]. Broadcasting and spanning-tree construction are closely related to the present work because a broadcast algorithm must deliver information from one source to all non-faulty nodes while avoiding failed components. Independent spanning-tree methods and classical studies of highly regular topologies illustrate the importance of having alternative communication structures under faults [11, 12]. The present work is most closely related to the published re-rooting-based fault-tolerant broadcasting method for dense Eisenstein–Jacobi networks [13]. That paper establishes the two-fault existence result and uses it to restore broadcast coverage by selecting a new source at distance t from both faulty nodes. The present paper does not replace that broadcasting model. Instead, it strengthens the source-selection step by replacing boundary search with closed-form counting and constant-time algebraic selection.
3
Preliminaries and Network Model
3.1
Eisenstein–Jacobi Coordinates
A node in EJt is represented by an Eisenstein–Jacobi coordinate X = x + yω,
(7)
which we also write as the ordered pair X = (x, y). Since EJt is a quotient network, different coordinate pairs may represent the same node. The notation modEJt (X)
(8)
denotes the canonical representative of X in the selected coordinate region of EJt . The generator in (1) gives a network with N = 3t2 + 3t + 1
(9)
nodes and diameter t. Throughout the paper, all coordinate sums and differences that represent network nodes are reduced by modEJt (·) when necessary.
3.2
Hexagonal Graph Distance
For a reduced coordinate X = (x, y), the Eisenstein–Jacobi graph distance from the origin is dEJ (0, X) = max{|x|, |y|, |x + y|}. (10) For two nodes U, V ∈ EJt , the distance is computed by reducing the difference: dEJ (U, V ) = dEJ (0, modEJt (U − V )). 4
(11)
The distance is translation invariant. Hence, for any nodes U, V, T ∈ EJt , dEJ (U, V ) = dEJ (modEJt (U + T ), modEJt (V + T )).
(12)
This property is the reason why an arbitrary two-fault problem can be translated to the origin and a difference node.
3.3
Boundary Nodes and Valid New Sources
The distance-t boundary around the origin is Bt = {P ∈ EJt : dEJ (P, 0) = t}.
(13)
More generally, the distance-t boundary around a node A is A + Bt = {modEJt (A + P ) : P ∈ Bt }.
(14)
A node P is a valid new source with respect to faults 0 and A if P ∈ Bt ∩ (A + Bt ).
(15)
The number of such nodes is denoted by CountEJ (A, t) = |Bt ∩ (A + Bt )|.
(16)
For arbitrary faults A and B, a node N S is valid if it satisfies (3).
3.4
Integer Labeling
The coordinate representation is compatible with an integer label modulo N . If the original dense Eisenstein–Jacobi parameter is n = t + 1, then the integer label of x + yω is ϕ(x + yω) ≡ tx − (t + 1)y
(mod N ),
(17)
(mod 3n2 − 3n + 1).
(18)
where N = 3t2 + 3t + 1. This is the same as ϕ(x + yω) ≡ (n − 1)x − ny
The labeling is useful in implementation because differences can be computed either in coordinate form or through their corresponding modular labels. The mathematical development below uses coordinates because the boundary geometry is clearer in the hexagonal representation.
5
Figure 1: Example dense Eisenstein–Jacobi network H3 with integer node labels. This topology illustrates the hexagonal quotient structure and the wrap-around nature used by the counting and selection algorithms.
4
Six-Side Boundary Partition
The boundary Bt is a hexagon. To count and select valid new sources without scanning Bt , we partition it into six directed sides. Let V1 = (t, 0), V2 = (0, t), V3 = (−t, t), V4 = (−t, 0), V5 = (0, −t), V6 = (t, −t),
u1 = (−1, 1), u2 = (−1, 0), u3 = (0, −1), u4 = (1, −1), u5 = (1, 0), u6 = (0, 1).
(19)
For i = 1, . . . , 6, define Si = {Vi + sui : 0 ≤ s ≤ t − 1, s ∈ Z}.
(20)
Each side has exactly t nodes. The endpoint convention in (20) includes the first vertex of each side and excludes the next vertex. Therefore the six sets are disjoint.
6
Figure 2: Six-side partition of the Eisenstein–Jacobi distance-t boundary. The boundary is written as Bt = S1 ∪ · · · ∪ S6 , where each side has t boundary nodes. Lemma 1 (Boundary partition) The sets S1 , . . . , S6 form a disjoint partition of the distancet boundary: 6 [ Bt = Si , Si ∩ Sj = ∅ (i ̸= j). (21) i=1
Consequently, |Bt | = 6t. Proof. For every point P = (x, y) in one of the six sets, the value of max{|x|, |y|, |x + y|} is exactly t. For example, on S1 we have P = (t − s, s), so x + y = t and 0 ≤ x, y ≤ t. Hence dEJ (P, 0) = t. The other five sides are analogous and correspond to y = t, x = −t, x + y = −t, y = −t, and x = t. Conversely, if dEJ (P, 0) = t, then one of the six quantities x, y, −x, −y, x + y, or −(x + y) is equal to t. This places P on one of the six sides. The halfopen endpoint convention assigns each vertex to exactly one side, so the sides are disjoint. Since each side contains t integer points, the boundary contains 6t nodes. □
5
Number of Valid New Sources for Faults 0 and A
This section gives the missing counting component: for a given node A, how many valid new sources exist when the faulty nodes are 0 and A? Figure 3 illustrates why quotient-lattice shifts must be included, and Figure 4 shows a counting example. The answer is the size of the quotient boundary intersection Bt ∩ (A + Bt ) in EJt . 7
(22)
A direct planar intersection of the six sides is not sufficient, because two coordinate points may represent the same node modulo the Eisenstein–Jacobi lattice. Therefore the correct side-pair equation must include the finite set of quotient-lattice shifts that can occur between radius-t representatives.
5.1
Quotient-Lattice Shifts
Let Kt = {(0, 0), ±L1 , ±L2 , ±L3 },
(23)
L2 = (2t + 1, −t − 1),
(24)
where L1 = (t + 1, t),
L3 = (t, −2t − 1).
These are the zero shift and the six shortest nonzero lattice shifts induced by the labeling ϕ(x, y) ≡ tx − (t + 1)y
(mod N ).
(25)
They satisfy ϕ(L) = 0 for every L ∈ Kt , and hence adding any such shift does not change the represented node in EJt . Lemma 2 (Finite shift sufficiency) If P, Q, A are canonical representatives in the radiust hexagon and P ≡ A + Q (mod α), (26) with P, Q ∈ Bt , then there exists a shift L ∈ Kt such that P = A + Q + L.
(27)
Proof. The equality in the quotient means that P − A − Q is a lattice vector in the kernel of the labeling map. Since P, A, Q are canonical radius-t representatives, D(P − A − Q) ≤ D(P ) + D(A) + D(Q) ≤ 3t,
(28)
where D(x, y) = max{|x|, |y|, |x+y|}. Therefore, only kernel vectors whose hexagonal length is at most 3t can appear in a boundary-intersection equation. It remains to identify these short kernel vectors. The kernel lattice is generated by two independent wrap-around vectors, for example L3 = (t, −2t − 1),
L1 = (t + 1, t),
(29)
and the third shortest direction is L2 = L1 + L3 = (2t + 1, −t − 1). Hence every kernel vector can be written as K(a, b) = aL1 + bL3 , a, b ∈ Z. (30) A direct substitution gives K(a, b) = a(t + 1) + bt, at − b(2t + 1) .
8
(31)
Checking the integer pairs (a, b) shows that the only nonzero vectors with D(K(a, b)) ≤ 3t are obtained from (a, b) ∈ {(1, 0), (−1, 0), (0, 1), (0, −1), (1, 1), (−1, −1)},
(32)
which are precisely ±L1 , ±L3 , and ±L2 . All other integer combinations have at least one of |x|, |y|, or |x + y| greater than 3t. Thus the only possible shifts in the present boundaryintersection problem are the zero vector and the six shifts in (23). Hence P − A − Q = L for some L ∈ Kt , which gives P = A + Q + L. □
5.2
Translated Side-Pair Intersection Formula
Let A = (a1 , a2 ).
(33)
ηLij (A, t) = |Si ∩ (A + Sj + L)|.
(34)
For L ∈ Kt and i, j ∈ {1, . . . , 6}, define
Using (20), a point lies in Si ∩ (A + Sj + L) if and only if there exist integers s, u with 0 ≤ s, u ≤ t − 1 such that Vi + sui = A + Vj + uuj + L. (35) Equivalently, s ui −uj = A + Vj + L − Vi , u where the two columns are the two-dimensional vectors ui and −uj . Let Mij = ui −uj , bLij = A + Vj + L − Vi .
(36)
(37)
Then (36) becomes s Mij = bLij . u
(38)
The contribution ηLij (A, t) is the number of integer solutions of (38) satisfying 0 ≤ s, u ≤ t − 1. Theorem 1 (Exact count for faults 0 and A) For any node A ∈ EJt , the exact number of valid new sources for faulty nodes 0 and A is CountEJ (A, t) =
6 X 6 XX
ηLij (A, t)
L∈Kt i=1 j=1
where ηLij (A, t) is obtained from the translated side-pair system (38).
9
(39)
Proof. A node P is valid for faults 0 and A exactly when dEJ (P, 0) = t and dEJ (P, A) = t.
(40)
The first condition means P ∈ Bt . By translation invariance, the second condition means that P − A represents a boundary node. Thus there exists Q ∈ Bt such that P ≡A+Q
(mod α).
(41)
By Lemma 2, this quotient equality is equivalent, for boundary representatives, to P =A+Q+L
(42)
for some L ∈ Kt . Using the disjoint boundary partition, P ∈ Si and Q ∈ Sj for unique side indices i and j. Therefore every valid source is counted by exactly one translated sidepair term ηLij (A, t), with the half-open endpoint convention preventing double counting at vertices. Conversely, every solution of a translated side-pair system gives a point P ∈ Bt satisfying P ≡ A + Q with Q ∈ Bt , and hence dEJ (P, A) = t. Summing over the seven shifts and the thirty-six side pairs proves (39). □
Figure 3: Illustration of the quotient-lattice correction. A valid boundary intersection in the finite dense Eisenstein–Jacobi network satisfies P ≡ A + Q (mod α), which in canonical coordinates becomes P = A + Q + L for a suitable lattice shift L. Without the shift term L, a planar side-pair intersection may miss wrap-around boundary intersections. The count in (39) should be interpreted as a closed finite evaluation rather than as a boundary scan. A boundary scan tests the 6t possible values of P one by one. In contrast, the translated side-pair formula groups boundary nodes into six parametric sides and solves the corresponding intersection equations algebraically. Parallel side pairs may represent several nodes at once, and nonparallel side pairs contribute at most one node. This is why the count can be evaluated with a fixed number of arithmetic tests even though the number of boundary nodes grows linearly with t. 10
5.3
Closed Evaluation of Each Side Pair
The formula (39) is constant-size because it contains at most 7·6·6 = 252 translated side-pair terms. Each term is evaluated as follows. If det(Mij ) ̸= 0, then (38) has at most one solution. Let ∗ s = Mij−1 bLij . (43) u∗ Then
( 1, s∗ , u∗ ∈ Z, 0 ≤ s∗ , u∗ ≤ t − 1, ηLij (A, t) = 0, otherwise.
(44)
If det(Mij ) = 0, then the two sides are parallel. In this case, either the equations are inconsistent and ηLij (A, t) = 0, or they reduce to one linear equation in two bounded integer parameters. The feasible set is an integer interval, and its size is ηLij (A, t) = max{0, U − L + 1},
(45)
where L and U are the lower and upper bounds obtained from 0 ≤ s, u ≤ t − 1 and the remaining linear equation.
5.4
Algorithmic Evaluation of the Count
Algorithm 1 evaluates (39) directly. It is included separately from the source-selection algorithm because it answers a different question: when the faulty nodes are 0 and A, it returns the number of valid new-source choices, not just one choice.
11
Algorithm 1 Constant-Time Count of Valid New Sources for Faults 0 and A Require: Network diameter t; node A ∈ EJt Ensure: The number CountEJ (A, t) of valid new sources for faults 0 and A 1: Q ← 0 2: Construct Kt = {(0, 0), ±(t + 1, t), ±(2t + 1, −t − 1), ±(t, −2t − 1)} 3: for all L ∈ Kt do 4: for i = 1 to 6 do 5: for j = 1 to 6 do 6: M ← [ui − uj ] 7: b ← A + Vj + L − Vi 8: if det(M ) ̸= 0 then 9: Solve M [s u]T = b by Cramer’s rule 10: if s, u are integers and 0 ≤ s, u ≤ t − 1 then 11: Q←Q+1 12: end if 13: else 14: Check consistency of the parallel system 15: if the parallel system is consistent then 16: Compute the feasible interval [Lb , Ub ] 17: if Lb ≤ Ub then 18: Q ← Q + (Ub − Lb + 1) 19: end if 20: end if 21: end if 22: end for 23: end for 24: end for 25: return Q Theorem 2 (Correctness and complexity of the counting algorithm) Algorithm 1 returns the exact value of CountEJ (A, t) and runs in O(1) time with respect to t and N under the fixed-word arithmetic model. Proof. For each shift L ∈ Kt and each pair (i, j), the algorithm solves exactly the translated side-pair system s Mij = A + Vj + L − Vi (46) u with the restrictions 0 ≤ s, u ≤ t − 1. If det(Mij ) ̸= 0, the two sides are nonparallel and there is at most one intersection point; the algorithm adds one precisely when that unique solution is integral and lies in the two parameter ranges. If det(Mij ) = 0, the two sides are parallel; the algorithm first tests consistency and then counts the feasible integer interval by Ub − Lb + 1. Therefore the value added for (L, i, j) is exactly ηLij (A, t). The algorithm sums these values over all seven shifts and all thirty-six side pairs. By Theorem 1, the sum is exactly CountEJ (A, t). The running time is constant because the loops 12
range over the fixed set Kt × {1, . . . , 6} × {1, . . . , 6}, which has 7 · 6 · 6 = 252 elements, and each translated side-pair evaluation uses only a fixed number of arithmetic, range-checking, and interval-bound operations. No node scan and no boundary scan is performed. Hence the complexity is O(1) under the fixed-word arithmetic model. □
Figure 4: Counting valid new sources for faults 0 and A. The highlighted boundary nodes are exactly those P satisfying dEJ (P, 0) = t and dEJ (P, A) = t. In the example shown, t = 4, A = (2, 1), and the number of valid new sources is six. Corollary 1 (Existence from the count) If the re-rooting existence theorem guarantees a common distance-t node for faults 0 and A, then CountEJ (A, t) > 0.
(47)
Moreover, (39) gives the exact number of available choices. Proof. The re-rooting existence theorem gives at least one node in Bt ∩ (A + Bt ). Theorem 1 counts that intersection exactly, so the count is positive and equals the number of choices. □
5.5
Worked Counting Examples for t = 3
For t = 3, the network contains N = 3(3)2 + 3(3) + 1 = 37
(48)
nodes and the boundary contains 6t = 18 nodes. Example 1: faults 0 and A = (1, 0). A direct evaluation of (39) gives CountEJ ((1, 0), 3) = 13. 13
(49)
The thirteen valid choices are (0, 3), (−1, 3), (−2, 3), (−3, 3), (−3, 2), (−3, 1), (−3, 0), (−2, −1), (−1, −2), (0, −3), (1, −3), (2, −3), (3, −3).
(50)
Each of these points is at distance 3 from both 0 and (1, 0). Example 2: faults 0 and A = (2, 0). The count is CountEJ ((2, 0), 3) = 8.
(51)
(0, 3), (−1, 3), (−2, 3), (−3, 1), (−3, 0), (1, −3), (2, −3), (3, −3).
(52)
The valid choices are
Example 3: faults 0 and A = (1, 1). The count is
with valid choices
CountEJ ((1, 1), 3) = 9,
(53)
(−2, 3), (−3, 3), (−3, 2), (−3, 1), (0, −3), (1, −3), (2, −3), (3, −3), (3, −2).
(54)
These examples show why the counting section is useful: the valid new source is not only guaranteed to exist, but the exact number of available candidates can also be computed without scanning the boundary.
6
Direct Constant-Time New-Source Selection
This section presents the main selection algorithm. It selects one valid new source for two arbitrary faulty nodes by translating the problem, solving a fixed number of Eisenstein– Jacobi side-pair systems, verifying the candidate, and shifting back.
6.1
Translation to the Origin
Let A, B ∈ EJt be two faulty nodes. Define C = modEJt (B − A).
(55)
If C = (c1 , c2 ), the translated problem is to find P such that dEJ (P, 0) = t,
dEJ (P, C) = t.
(56)
Once P is found, set N S = modEJt (A + P ).
(57)
Lemma 3 (Translation correctness) If P satisfies dEJ (P, 0) = t and dEJ (P, C) = t, where C = modEJt (B − A), then N S = modEJt (A + P ) satisfies dEJ (N S, A) = t,
dEJ (N S, B) = t. 14
(58)
Proof. Using translation invariance, dEJ (N S, A) = dEJ (modEJt (A + P ), A) = dEJ (P, 0) = t.
(59)
Since C = modEJt (B − A), we have B = modEJt (A + C). Therefore dEJ (N S, B) = dEJ (modEJt (A + P ), modEJt (A + C)) = dEJ (P, C) = t. Thus N S is at distance t from both faults.
6.2
(60) □
Side-Pair Algebra
The point P must lie in Bt ∩ (C + Bt ).
(61)
Therefore, for some shift L ∈ Kt and some side pair (i, j), P ∈ Si ∩ (C + Sj + L).
(62)
Using the same side parameterization, this means Vi + sui = C + Vj + uuj + L, with integers 0 ≤ s, u ≤ t − 1. This is again the two-by-two system s Mij = C + Vj + L − Vi . u
(63)
(64)
The algorithm checks at most 7 · 6 · 6 = 252 translated systems. A nonparallel system gives one possible candidate. A parallel system gives either no candidate or an interval of candidates. In either case, only constant-time arithmetic is required.
6.3
Algorithm 2: Direct Side-Pair Selector
Algorithm 2 is the proposed constant-time selector. It checks a fixed set of translated hexagonal side pairs and therefore does not enumerate the full node set or the distance-t boundary.
15
Algorithm 2 Constant-Time Direct New-Source Selection in EJt Require: Network diameter t; faulty nodes A, B ∈ EJt Ensure: A valid new source N S 1: C ← modEJt (B − A) 2: Construct Kt = {(0, 0), ±(t + 1, t), ±(2t + 1, −t − 1), ±(t, −2t − 1)} 3: for all L ∈ Kt do 4: for i = 1 to 6 do 5: for j = 1 to 6 do 6: M ← [ui − uj ] 7: b ← C + Vj + L − Vi 8: if det(M ) ̸= 0 then 9: Solve M [s u]T = b by Cramer’s rule 10: if s, u are integers and 0 ≤ s, u ≤ t − 1 then 11: P ← Vi + sui 12: if dEJ (P, 0) = t and dEJ (P, C) = t then 13: return modEJt (A + P ) 14: end if 15: end if 16: else 17: Compute the feasible interval [Lb , Ub ] for the parallel system 18: if Lb ≤ Ub then 19: Choose s ← Lb and compute the corresponding u 20: P ← Vi + sui 21: if dEJ (P, 0) = t and dEJ (P, C) = t then 22: return modEJt (A + P ) 23: end if 24: end if 25: end if 26: end for 27: end for 28: end for 29: return failure
Figure 5: Direct new-source selection workflow. The original faults A and B are translated to 0 and C = B − A; a valid translated point P is selected from the boundary intersection; and the final source is obtained by shifting back, N S = A + P . 16
6.4
Correctness Proofs
Theorem 3 (Soundness) If Algorithm 2 returns a node N S, then N S is a valid new source for the faulty nodes A and B. Proof. The algorithm returns only after constructing a point P and verifying dEJ (P, 0) = t,
dEJ (P, C) = t.
(65)
By the translation correctness lemma, the shifted node N S = modEJt (A + P ) satisfies dEJ (N S, A) = t,
dEJ (N S, B) = t.
Therefore the returned node is valid.
(66) □
Theorem 4 (Completeness under the re-rooting existence condition) For any two distinct faulty nodes A, B ∈ EJt for which the re-rooting existence theorem guarantees a common distance-t node, Algorithm 2 returns a valid new source. Proof. Let C = modEJt (B − A). By the re-rooting existence theorem, there exists a point P ∈ EJt such that dEJ (P, 0) = t, dEJ (P, C) = t. (67) Thus P ∈ Bt and P ≡ C + Q (mod α) for some Q ∈ Bt . By Lemma 2, there is a shift L ∈ Kt such that P = C + Q + L. Since the six-side partition is disjoint, P lies on a unique side Si of Bt , and Q lies on a unique side Sj of Bt . Hence P ∈ Si ∩ (C + Sj + L) for some triple (L, i, j). Algorithm 2 checks every triple (L, i, j). For the translated side pair containing P , equation (64) has a feasible integer solution. If the two sides are nonparallel, the solution is unique and Cramer’s rule recovers it. If the two sides are parallel, the feasible solutions form an integer interval, and the interval computation contains at least one feasible endpoint or interior point. The algorithm selects one feasible point, verifies the two distance equations, and returns N S = modEJt (A + P ). By the soundness theorem, the returned node is valid. □ Theorem 5 (Constant-time complexity) Algorithm 2 runs in O(1) time with respect to t and N under the fixed-word arithmetic model. Proof. The algorithm has three fixed loops: one over the seven shifts in Kt and two over the six boundary sides. Therefore it checks at most 7 · 6 · 6 = 252 translated side-pair systems. For each translated system, it performs a fixed number of arithmetic operations: determinant computation, solution by Cramer’s rule or parallel interval computation, range checking, and final distance verification. None of these operations requires scanning the N nodes or the 6t boundary nodes. Hence the total number of coordinate operations is bounded by a constant independent of t and N . Under the fixed-word arithmetic model, the running time is O(1). □
17
6.5
Worked Selection Examples
Example 1: faults 0 and (1, 0) in EJ3 . Here t = 3 and C = (1, 0). One valid translated point is P = (−2, 3). (68) Indeed, dEJ (P, 0) = max{2, 3, 1} = 3,
(69)
and P − C = (−3, 3),
dEJ (P, C) = max{3, 3, 0} = 3.
(70)
Therefore P is a valid new source for faults 0 and (1, 0). Example 2: arbitrary faults in EJ3 . Let A = (1, 0),
B = (2, 0).
(71)
Then C = B − A = (1, 0).
(72)
Using the valid translated point P = (−2, 3) from Example 1, the shifted source is N S = A + P = (−1, 3).
(73)
Now N S − A = (−2, 3),
dEJ (N S, A) = 3,
(74)
N S − B = (−3, 3),
dEJ (N S, B) = 3.
(75)
and Thus N S = (−1, 3) is a valid new source for the faults (1, 0) and (2, 0). Example 3: another translated candidate. For faults 0 and A = (1, 1) in EJ3 , the count is 9 by the counting formula. One valid point is P = (−2, 3) because dEJ (P, 0) = 3,
P − A = (−3, 2),
dEJ (P, A) = 3.
(76)
This example shows that the same distance verification used by the algorithm directly confirms a candidate after the translated side-pair system identifies it.
7
Complexity Comparison
This section compares the proposed direct selector with two search-based alternatives. Let N = 3t2 + 3t + 1.
7.1
Full Node Scan
A brute-force method tests every node X ∈ EJt and checks whether dEJ (X, A) = t,
dEJ (X, B) = t.
(77)
Since there are N = 3t2 + 3t + 1 nodes, the full scan has complexity O(N ) = O(t2 ). 18
(78)
7.2
Boundary Scan
A better search method tests only the boundary around one fault. After translating to 0 and C, it checks all points in Bt . Since |Bt | = 6t, this method has complexity O(t).
7.3
(79)
Direct Side-Pair Selection
Algorithm 2 checks at most 7 · 6 · 6 = 252 translated side-pair systems. Therefore, its complexity is O(1). (80) Table 1 summarizes the comparison. Table 1: Complexity comparison of new-source selection methods in EJt . Method Candidates or cases Complexity Full node scan Boundary scan Proposed selector
N = 3t2 + 3t + 1 O(N ) 6t O(t) 252 translated side-pair systems O(1)
Figure 6: Average search effort for new-source selection. Boundary search grows with t, while the proposed selector remains nearly constant in the tested cases and is bounded by 252 translated side-pair systems.
8
Computational Validation
This section validates the translated side-pair counting and selection algorithms and evaluates the re-rooting recovery performance. The experiments used t ∈ {10, 25, 50, 100, 200}, 19
(81)
with N = 3t2 + 3t + 1. Count validation was exhaustive for t = 10, 25, 50 and sampled 10,000 nodes for t = 100, 200. Direct-selection validation used 100,000 randomly sampled fault pairs for each value of t. The re-rooting experiment used four fault-placement modes, namely random, near, critical, and closepair, with 1000 trials per exact setting.
8.1
Experimental Protocol
All experiments used the canonical coordinate representation defined in Section 3. Node labels were used only for storage and reporting; every distance check was performed by reducing coordinate differences and evaluating the hexagonal distance in (10). For the countvalidation experiment, the output of Algorithm 1 was compared with a brute-force scan of the boundary set Bt . For the direct-selection experiment, each sampled fault pair (A, B) was translated to C = B − A, Algorithm 2 returned a candidate N S, and the implementation verified both distance equations in the original coordinates. For the re-rooting experiment, four faultplacement modes were used. The random mode chooses faults uniformly from the nonsource nodes. The near mode emphasizes faults close to the original source. The critical mode chooses faults on or near the principal broadcast axes. The closepair mode chooses two faults that are adjacent or nearly adjacent.
8.2
Counting Validation
For each tested node A, Algorithm 1 was compared with a brute-force boundary count of all points P ∈ Bt satisfying dEJ (P, A) = t. Table 2 shows that the translated side-pair count matched brute force in every tested case. Table 2: Validation of the translated side-pair count for faults 0 and A. t N Nodes tested Mismatches Max error 10 25 50 100 200
331 1951 7651 30301 120601
331 1951 7651 10000 10000
0 0 0 0 0
20
0 0 0 0 0
Figure 7: Counting-runtime comparison. Algorithm 1 checks exactly 252 translated side-pair systems, while brute-force counting scans the 6t boundary nodes.
8.3
Direct-Selection Validation
For each tested pair A, B, Algorithm 2 returned a candidate N S, and the implementation verified dEJ (N S, A) = t, dEJ (N S, B) = t. (82) Table 3 shows that all 500,000 tested fault pairs produced valid outputs. Table 3: Validation of direct new-source selection over sampled fault pairs. t N Pairs Valid Failed Max checked 10 25 50 100 200
8.4
331 1951 7651 30301 120601
100000 100000 100000 100000 100000
100000 100000 100000 100000 100000
0 0 0 0 0
21 21 21 21 21
Re-Rooting Recovery Results
The re-rooting experiment evaluated the complete recovery behavior using one and two faulty nodes. For each value of t, each fault count, and each fault-placement mode, 1000 trials were executed. Thus, the raw experiment contained 5 × 2 × 4 × 1000 = 40000
(83)
trials. Table 4 aggregates the results over the four modes for each t and fault count. The proposed method achieved 100% success in every setting and reached exactly N − f nodes, where f is the number of faulty nodes.
21
Table 4: Aggregated re-rooting recovery results over all four fault-placement modes. t
N
Faults
10 10 25 25 50 50 100 100 200 200
331 331 1951 1951 7651 7651 30301 30301 120601 120601
1 2 1 2 1 2 1 2 1 2
Trials Baseline success 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000
8.075% 5.225% 4.125% 1.550% 2.250% 1.150% 1.375% 0.500% 0.650% 0.250%
Proposed success 100% 100% 100% 100% 100% 100% 100% 100% 100% 100%
Avg. baseline reach Avg. proposed reach 305.779 282.991 1849.122 1757.920 7320.131 7032.936 29157.713 28182.787 116405.605 112678.853
330.000 329.000 1950.000 1949.000 7650.000 7649.000 30300.000 30299.000 120600.000 120599.000
Expected reach 330 329 1950 1949 7650 7649 30300 30299 120600 120599
Figure 8: Recovery success under one and two faults. The proposed method achieves full recovery in all 40,000 trials, while the baseline broadcast tree loses coverage when faulty nodes interrupt internal broadcast paths.
Figure 9: Proposed reach versus the theoretical maximum. In all tested settings, the proposed re-rooting method reaches exactly N − f non-faulty nodes, where f is the number of faults. 22
8.5
Runtime Comparison
The runtime comparison used the same sampled fault pairs for the boundary-search selector and the proposed direct selector. Table 5 and Figure 10 show that the direct method has fixed overhead for small t, but it becomes faster as the boundary size grows. At t = 200, the measured speedup was approximately 9.80×. Table 5: Average runtime per new-source selection query. t N Boundary ms Direct ms Speedup 10 25 50 100 200
331 1951 7651 30301 120601
0.008189 0.019377 0.046039 0.095780 0.214375
0.016373 0.017221 0.020424 0.020499 0.021875
0.50× 1.13× 2.25× 4.67× 9.80×
Table 6: Average number of checked candidates or algebraic cases. t Boundary search avg. Direct avg. Direct max 10 25 50 100 200
7.810 20.247 41.022 82.881 166.298
9.276 9.630 9.685 9.759 9.757
21 21 21 21 21
Figure 10: Runtime comparison between boundary search and direct selection. The proposed method has fixed algebraic overhead for small t, but becomes faster as the boundary size increases.
23
9
Discussion
The contribution of this paper is algorithmic and algebraic rather than a replacement of the underlying broadcasting model. The broadcasting and recovery framework is inherited from the published Eisenstein–Jacobi re-rooting paper, and the present paper strengthens that framework by replacing the new-source selection step with a direct algebraic construction. The distinction is important. The re-rooting paper answers the existence and recovery question: a suitable new source exists for two faulty nodes and can be used to restore broadcasting. This paper answers the selection question: once two faulty nodes are known, a valid new source can be computed by checking a fixed number of translated side-pair systems. Thus, the two papers are complementary. The first provides the fault-tolerant broadcasting framework, while the present extension improves the algorithmic efficiency of one of its central operations. The proposed method also explains the geometric reason behind the constant-time bound. The distance-t boundary has 6t nodes, but it has only six sides. Searching boundary nodes depends on t. Searching translated side-pair systems depends only on the number of sides and the seven relevant quotient shifts, both of which are fixed. Therefore the method avoids growth with network size. The constant-time method has a fixed overhead. For small values of t, a boundary scan may sometimes be competitive because the boundary itself is small. This does not contradict the complexity result. The benefit of the proposed method becomes clearer as t grows: the boundary-search effort increases with 6t, while the proposed selector remains bounded by the same finite family of translated side-pair systems. A second point is that the count and the selector serve different purposes. The counting algorithm evaluates all translated side-pair systems and gives the exact number of valid choices for faults 0 and A. The selector stops as soon as it finds one verified candidate. This explains why the theoretical worst-case bound is 252 systems, while the observed selector checks were much smaller in the sampled experiments.
10
Conclusion
This paper developed a closed-form and constant-time method for counting and selecting valid new sources in dense Eisenstein–Jacobi networks. The method extends the published re-rooting-based fault-tolerant broadcasting framework by converting the two-fault sourceselection problem into a quotient boundary-intersection problem. For faults 0 and A, the exact number of valid new sources is computed by summing translated side-pair intersections over the seven relevant lattice shifts and the thirty-six hexagonal side pairs. For arbitrary faults A and B, the problem is translated to the origin and the difference node C = B − A, solved by the same translated side-pair systems, and shifted back to obtain the new source. The correctness of the method was proved through boundary partition, finite-shift sufficiency, counting-algorithm correctness, selector soundness, selector completeness, and complexity arguments. Since both algorithms evaluate at most 7 · 6 · 6 = 252 translated side-pair systems and perform only constant-time arithmetic in each case, both run in O(1) time under the fixed-word arithmetic model. Computational validation confirmed that the count 24
matched brute force in all tested cases, the direct selector returned valid outputs for all 500,000 sampled fault pairs, and the re-rooting method achieved 100% recovery over 40,000 trials. Future work includes ranking multiple valid candidates according to broadcast recovery cost, studying implementation-level integration with the complete re-rooting broadcast procedure, and investigating whether similar fixed-case constructions can be developed for larger fault sets or other algebraic network families.
A
Translated Side-Pair System Details
This appendix gives the general algebraic form used by both Algorithm 1 and Algorithm 2. For a center node X, which is either A in the counting problem or C = B −A in the selection problem, a translated side-pair intersection has the form Si ∩ (X + Sj + L),
L ∈ Kt .
(84)
Using the side parameterization Si = {Vi + sui : 0 ≤ s ≤ t − 1}, this intersection is described by Vi + sui = X + Vj + uuj + L, 0 ≤ s, u ≤ t − 1. (85) Moving all parameter terms to the left gives s Mij = bLij (X), u
(86)
where Mij = [ui − uj ],
bLij (X) = X + Vj + L − Vi .
(87)
If det(Mij ) ̸= 0, then the side directions are nonparallel and the system has at most one solution. Writing ui = (r1 , r2 ),
−uj = (r3 , r4 ),
bLij (X) = (b1 , b2 ),
(88)
the determinant is ∆ = r1 r4 − r2 r3 .
(89)
The candidate parameters are s=
b1 r4 − r3 b2 , ∆
u=
r1 b2 − b1 r2 . ∆
(90)
This translated side pair contributes one point if and only if s and u are integers and both lie in the interval [0, t − 1]. Otherwise it contributes zero points. If det(Mij ) = 0, then the side directions are parallel. In that case, consistency is checked by testing whether bLij (X) is parallel to ui . When it is not parallel, the contribution is zero. When it is parallel, the two-parameter equation reduces to one integer linear relation between s and u. The parameter bounds then determine an interval of feasible integer values. The count algorithm adds the length of that interval, while the selector chooses one feasible parameter value and verifies the resulting point. 25
This appendix also clarifies why the algorithms do not scan the boundary. A boundary scan enumerates all 6t values of P . The translated side-pair method instead evaluates a fixed collection of systems indexed by (L, i, j) ∈ Kt × {1, . . . , 6} × {1, . . . , 6}.
(91)
The number of such triples is 7 · 6 · 6 = 252, independent of t.
B
Parallel Side-Pair Computation
This appendix gives a compact implementation form for the parallel case used in Algorithm 2. Consider the side-pair equation Vi + sui = C + Vj + uuj + L,
(92)
with 0 ≤ s, u ≤ t − 1. If det([ui − uj ]) = 0, then the two direction vectors are parallel. Consistency is checked by verifying that C + Vj + L − Vi is parallel to ui . If it is not parallel, the contribution is zero. If the system is consistent, one coordinate equation determines a relation of the form u = ρs + σ,
(93)
where ρ ∈ {1, −1} for the side directions used in this paper and σ is an integer offset. The range restrictions become 0 ≤ s ≤ t − 1,
0 ≤ ρs + σ ≤ t − 1.
(94)
These inequalities give an interval L ≤ s ≤ U.
(95)
The number of feasible integer solutions is max{0, U − L + 1}. For selection, Algorithm 2 chooses s = L when L ≤ U , computes u = ρL + σ, and verifies the two distance equations before returning.
Acknowledgments The authors would like to acknowledge the support of Kuwait University and its Computer Science Department.
References [1] M. Flahive and B. Bose, “The topology of Gaussian and Eisenstein–Jacobi interconnection networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 21, no. 8, pp. 1132–1142, 2010.
26
[2] 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, no. 3, pp. 193–211, 2006. [3] R. Beivide, C. Martı́nez, and E. Vallejo, “Gaussian interconnection networks,” in Proc. Spanish Parallelism Conference, 2005. [4] E. Vallejo, C. Martı́nez, and R. Beivide, “Hierarchical topologies for large-scale two-level networks,” Journal of Parallel and Distributed Computing, vol. 68, no. 4, pp. 461–476, 2008. [5] A. Grama, A. Gupta, G. Karypis, and V. Kumar, Introduction to Parallel Computing, 2nd ed. Pearson, 2003. [6] J. Duato, S. Yalamanchili, and L. Ni, Interconnection Networks: An Engineering Approach. Morgan Kaufmann, 2002. [7] W. J. Dally and B. Towles, Principles and Practices of Interconnection Networks. Morgan Kaufmann, 2004. [8] D. Kliazovich, F. Granelli, and D. Miorandi, “A survey on fault-tolerant communication in network-on-chip architectures,” Computer Networks, vol. 54, no. 14, pp. 2434–2452, 2010. [9] S. Pasricha and N. Dutt, On-Chip Communication Architectures: System-on-Chip Interconnect. Morgan Kaufmann, 2008. [10] J. Flich and D. Bertozzi, Designing Network-on-Chip Architectures in the Nanoscale Era. CRC Press, 2010. [11] J. Wu and H. Huang, “A distributed algorithm for constructing independent spanning trees in parallel systems,” IEEE Transactions on Parallel and Distributed Systems, vol. 10, no. 4, pp. 377–381, 1999. [12] Y. Saad and M. H. Schultz, “Topological properties of hypercubes,” IEEE Transactions on Computers, vol. 37, no. 7, pp. 867–872, 1988. [13] B. Albader, “Re-rooting-based fault-tolerant broadcasting in dense Eisenstein–Jacobi networks,” IEEE Access, 2026. [14] O. G. Monakhov, E. A. Monakhova, A. Y. Romanov, A. M. Sukhov, and E. V. Lezhnev, “Adaptive dynamic shortest path search algorithm in networks-on-chip based on circulant topologies,” IEEE Access, vol. 9, pp. 160836–160846, 2021, doi: 10.1109/ACCESS.2021.3131635. [15] A. Y. Romanov, E. V. Lezhnev, A. Y. Glukhikh, and A. A. Amerikanov, “Development of routing algorithms in networks-on-chip based on two-dimensional optimal circulant topologies,” Heliyon, vol. 6, no. 1, Art. no. e03172, 2020, doi: 10.1016/j.heliyon.2020.e03172. 27
[16] A. Y. Romanov, N. O. Myachin, E. V. Lezhnev, D. A. Ivannikov, and A. El-Mesady, “Ring-Split: Deadlock-free routing algorithm for circulant networks-on-chip,” Micromachines, vol. 14, no. 1, Art. no. 141, 2023, doi: 10.3390/mi14010141. [17] E. A. Monakhova, O. G. Monakhov, and A. Y. Romanov, “Routing algorithms in optimal degree four circulant networks based on relative addressing: Comparative analysis for networks-on-chip,” IEEE Transactions on Network Science and Engineering, vol. 10, no. 1, pp. 413–425, 2023, doi: 10.1109/TNSE.2022.3211985. [18] A. M. Sukhov, A. Y. Romanov, and M. P. Selin, “Virtual coordinate system based on a circulant topology for routing in networks-on-chip,” Symmetry, vol. 16, no. 1, Art. no. 127, 2024, doi: 10.3390/sym16010127. [19] M. Rashid, H. K. Singh, and M. H. Anisi, “Fault-tolerant network-on-chip router architecture design for heterogeneous many-core systems,” Sensors, vol. 20, no. 18, Art. no. 5355, 2020, doi: 10.3390/s20185355. [20] J. Samala, B. B. Mekala, and S. Joshi, “Enhancing fault-tolerant application mapping in network-on-chip through transformer network based reinforcement learning approach,” Discover Computing, vol. 28, Art. no. 16, 2025, doi: 10.1007/s10791-025-09704-0. [21] X. Yu, L. Tang, J. Mi, J. Liu, and L. Long, “Fault tolerant and quality of service aware routing algorithm based on priority technique for scalable network on chip architectures,” Scientific Reports, vol. 15, Art. no. 36578, 2025, doi: 10.1038/s41598-025-203813.
28