Closed-Form and Constant-Time New-Source Selection for Fault-Tolerant Broadcasting in Dense Gaussian Networks arXiv:2606.18715v1 [cs.DC] 17 Jun 2026
Bader Albader Department of Computer Science, Kuwait University, Kuwait [email protected]
Abstract Fault-tolerant broadcasting in dense Gaussian networks can be recovered by rerooting the broadcast at a new source that is at maximum graph distance from the faulty nodes. This paper extends the published re-rooting framework by replacing its boundary-search source-selection step with a quotient-lattice-aware algebraic construction. The first contribution is a constant-time counting method for valid new sources. The counting problem is formulated as an intersection of two diameter-k boundary sets in the Gaussian quotient. A compact piecewise expression is retained for the local, unshifted boundary intersection, and the exact quotient-network count is obtained by a fixed union of side-pair intervals over the nine relevant quotient-lattice copies. This gives a closed-form constant-size counting procedure without scanning either the network or the boundary. The second contribution is a shifted direct selector for two arbitrary faulty nodes. Given faulty nodes A and B, the problem is translated to C = modGk (B − A), and the selector finds a point P satisfying d(P, 0) = d(P, C) = k. For each of nine quotient-lattice shifts, the selector checks sixteen signed linear systems. Nonparallel systems are solved using Cramer’s rule, while parallel systems are handled by interval-endpoint selection. Thus, at most 9 × 16 = 144 shifted sign cases are evaluated, giving O(1) source selection under the standard word-RAM model. Computational validation reports zero count mismatches over 26,623 tested nodes, 500,000 valid outputs over 500,000 sampled fault pairs, and 40,000 successful re-rooted broadcast trials. Runtime results show that the shifted selector has a small fixed overhead for small networks but remains nearly stable as k increases, achieving a 5.92× speedup over boundary search at k = 200. These results strengthen the re-rooting approach by making new-source selection algebraic, bounded, and independent of the network size.
Keywords: Dense Gaussian networks, fault-tolerant broadcasting, re-rooting, new-source selection, interconnection networks, constant-time algorithms, graph distance.
1
Introduction
Interconnection networks play an important role in the design of parallel and distributed computing systems. Their topology directly affects communication latency, fault tolerance, 1
routing complexity, and broadcasting efficiency [6, 7, 8]. Among many well-known network structures, circulant-based networks and Gaussian networks have received attention because they combine regularity, symmetry, and relatively small diameter [1, 2, 3]. These properties make them useful models for studying communication algorithms, routing strategies, and fault-tolerant information dissemination. Dense Gaussian networks form a special class of degree-four interconnection networks constructed over Gaussian integers [2, 3]. A dense Gaussian network with parameter k, denoted by Gk , contains N = k 2 + (k + 1)2 nodes and has diameter k. Each node can be represented either by a Gaussian integer coordinate or by an equivalent integer label modulo N . This algebraic structure provides a compact way to describe routing paths, coordinate differences, and wrap-around connections. Related algebraic approaches using Gaussian integers and circulant structures have also been studied in connection with domination, routing, and scalable network construction [4, 5]. As a result, dense Gaussian networks offer a useful setting for the study of broadcasting and fault-tolerant communication. Broadcasting is a fundamental communication operation in which one source node sends information to all other nodes in the network. In a fault-free dense Gaussian network, the regular structure of Gk allows a source node to reach all other nodes within k steps. However, when one or more nodes fail, some broadcast paths may be interrupted. This can prevent the original broadcast tree from covering all non-faulty nodes. Fault-tolerant communication is therefore a major concern in interconnection networks and network-onchip architectures [9, 10, 11]. A fault-tolerant broadcasting method must not only detect the effect of faulty nodes, but also provide an efficient mechanism for restoring coverage. The published re-rooting-based broadcasting method addresses this problem by selecting a new source node when faults occur [14]. The main idea is to restart or continue the broadcast from a carefully selected node that is farthest from the faulty nodes in terms of graph distance. In particular, for two faulty nodes A and B, a valid new source N S should satisfy d(N S, A) = k and d(N S, B) = k. Such a node allows the recovered broadcast to begin from a position that avoids the faulty region and preserves the maximum-distance structure of the network. Although the re-rooting approach provides an effective recovery mechanism, the selection of a valid new source raises an important mathematical and algorithmic question. Existing treatment mainly establishes the existence of a suitable new source or obtains one through search-based procedures. A direct closed-form method for counting and selecting valid new sources is still needed. Without such a method, the new-source selection step may depend on scanning network nodes or testing boundary candidates, which obscures the algebraic structure of the problem and may increase the cost of recovery. The present work is a direct extension of the re-rooting-based method introduced in [14]. In that work, the re-rooting framework was proposed, the existence of a common distance-k 2
node was proved for any two faulty nodes, and an O(k) boundary-search procedure was used to find a valid new source. In contrast, the present paper does not propose a new broadcasting model. Instead, it strengthens the mathematical and algorithmic foundation of the source-selection step by deriving the exact number of valid new sources and by replacing the boundary-search procedure with a constant-time algebraic construction. This paper extends the re-rooting framework by developing a quotient-lattice-aware counting and selection theory for valid new sources in dense Gaussian networks. The first part of the paper studies the number of valid new sources. For a given node A = (ax , ay ), we count the number of nodes p satisfying d(0, p) = k and d(A, p) = k. These nodes are exactly the candidates that are simultaneously at maximum graph distance from the origin and from A. By expressing the position of A using a = max{|ax |, |ay |} and b = min{|ax |, |ay |}, we derive a compact piecewise formula for the local boundary-intersection count and then extend it to an exact quotient-lattice-aware count using a fixed set of side-pair interval computations. This shows that every nonzero node has at least four valid new sources and also accounts for wrap-around boundary intersections. The second part of the paper uses this structure to develop a direct method for two arbitrary faulty nodes. Given faulty nodes A and B, the problem is translated to an equivalent problem involving the origin and the difference node C = modGk (B − A). A valid point P is then found such that d(P, 0) = k and d(P, C) = k. The desired new source is obtained by translating back: N S = modGk (A + P ). The proposed method solves this problem by considering a fixed set of quotient-lattice copies and a fixed set of sign configurations. Specifically, it checks nine lattice shifts and sixteen sign tuples per shift, for at most 9 × 16 = 144 algebraic cases. Since this bound is independent of k and N , the selection procedure runs in O(1) time under the standard word-RAM model. The main contributions of this paper are summarized as follows: 3
• We formulate the valid new-source problem as an intersection problem between two k-step boundary sets in Gk . • We derive a compact piecewise formula for the local boundary-intersection count and an exact quotient-lattice-aware constant-time counting formula for the full Gaussian quotient network. • We prove that every nonzero node has at least four valid new sources, strengthening the existence argument used in re-rooting-based fault-tolerant broadcasting. • We develop a quotient-lattice-aware direct algebraic construction for selecting a valid new source for two arbitrary faulty nodes. The construction handles wrap-around boundary copies, nonparallel signed systems, and parallel signed systems without scanning the network or the boundary. • We show that the proposed shifted direct-selection method runs in O(1) time because it checks at most 9×16 = 144 algebraic cases and performs only constant-time arithmetic in each case, independent of the network size. The rest of this paper is organized as follows. Section 2 reviews related work on Gaussian networks, circulant topologies, fault-tolerant communication, and algebraic routing methods. Section 3 introduces the required notation and background on dense Gaussian networks. Section 4 derives the local piecewise count and the exact quotient-lattice-aware counting formula for valid new sources. Section 5 presents the shifted constant-time construction for two arbitrary faulty nodes. Section 6 compares the proposed method with search-based alternatives. Section 7 presents computational validation of the counting formula and the direct-selection algorithm. Section 8 concludes the paper and discusses future work. Finally, Appendix A gives the side-pair interval formulas used by the quotient-lattice-aware counter.
2
Related Work
Gaussian and circulant-based interconnection networks have been widely studied because they provide regular structures, small diameter, and algebraic representations that are useful for routing and broadcasting. Flahive and Bose studied the topology of Gaussian and Eisenstein–Jacobi interconnection networks and showed how quotient rings of Gaussian and Eisenstein–Jacobi integers can be used to construct interconnection networks with desirable topological properties [1]. Dense Gaussian networks were later studied as degree-four circulant-based topologies suitable for on-chip multiprocessors, where their smaller diameter and two-dimensional labeling provide advantages over traditional torus-based structures [2]. Related work on Gaussian interconnection networks also introduced coordinate-based representations that simplify analysis, routing, and broadcasting in these networks [3]. In addition, the connection between circulant graphs, Gaussian integers, and domination problems further demonstrates the usefulness of algebraic methods in this family of networks [4]. Hierarchical and scalable versions of these networks have also been considered. Vallejo, Martı́nez, and Beivide studied hierarchical topologies for large-scale two-level networks, extending the use of Gaussian and circulant-based structures to larger systems [5]. More generally, interconnection networks are central to parallel and distributed computing because 4
network topology directly affects routing cost, communication latency, bisection bandwidth, and fault tolerance [6]. Standard treatments of interconnection networks emphasize that regularity, symmetry, degree, and diameter are important design factors for scalable communication systems [7, 8]. Fault tolerance and reliable communication are major concerns in interconnection networks and network-on-chip architectures. Kliazovich, Granelli, and Miorandi surveyed faulttolerant communication in network-on-chip architectures and emphasized the importance of maintaining communication under link or node failures [9]. Pasricha and Dutt discussed on-chip communication architectures and showed how topology and routing decisions affect system-level performance and reliability [10]. Flich and Bertozzi also studied network-on-chip design in the nanoscale era, where reliability, scalability, and routing efficiency are critical concerns [11]. Broadcasting and spanning-tree construction are also closely related to the present work. Wu and Huang developed a distributed algorithm for constructing independent spanning trees in parallel systems, which is relevant because independent or alternative spanning structures can improve communication reliability [12]. Saad and Schultz studied topological properties of hypercubes, including structural properties important for communication algorithms in parallel systems [13]. Recent work has continued to study circulant and Gaussian-related topologies for networkson-chip. Romanov et al. developed routing algorithms for networks-on-chip based on twodimensional optimal circulant topologies, showing the continued relevance of circulant structures for efficient routing in NoC environments [15]. Monakhova, Monakhov, and Romanov proposed routing algorithms for optimal degree-four circulant networks based on relative addressing, which is particularly relevant because their approach uses algebraic and coordinatebased routing ideas in degree-four circulant networks [16]. Song et al. studied Gaussian-based optical networks-on-chip and reported performance advantages related to diameter and hop distance, further supporting the use of Gaussian-based topologies in modern communication architectures [17]. The present paper differs from these prior works in its objective. Existing work mainly studies topology, routing, broadcasting, or general fault-tolerant communication. Recent rerooting-based broadcasting work showed that a broadcast in a dense Gaussian network can be recovered by selecting a valid new source when faults occur [14]. However, the new-source selection step remained primarily an existence or search-based step. This paper addresses that gap by deriving a closed-form formula for the number of valid new sources and by developing a constant-time algebraic method for selecting one.
3
Preliminaries and Network Model
This section introduces the notation and basic properties used throughout the paper. The network considered in this work is the dense Gaussian network Gk , where k is a positive integer parameter. The node set of Gk can be represented by Gaussian integer coordinates with wrap-around equivalence. The total number of nodes is N = k 2 + (k + 1)2 . 5
The graph has diameter k, meaning that every node can be reached from any other node in at most k steps.
3.1
Node Representation
A node in Gk is represented by an ordered pair A = (ax , ay ), which corresponds to the Gaussian integer ax + ay i. Throughout the paper, we use coordinate notation and Gaussian-integer notation interchangeably whenever the meaning is clear. Because Gk is a wrap-around network, different coordinate pairs may represent the same node. Therefore, whenever a coordinate expression produces a point outside the chosen representative region of Gk , it is reduced modulo the Gaussian network. We denote this reduction by modGk (·).
3.2
Graph Distance
For two nodes U, V ∈ Gk , the graph distance between them is denoted by d(U, V ). This distance is the minimum number of graph edges required to move from U to V in Gk . Since Gk has diameter k, we have d(U, V ) ≤ k for all nodes U, V ∈ Gk . Because Gk is a wrap-around network, a coordinate difference may have several equivalent Gaussian-integer representatives. Throughout this paper, whenever a difference node is written as X = modGk (U − V ) = (x, y), we assume that modGk (·) returns the canonical reduced representative whose Manhattan length is minimum among all equivalent representatives. Therefore, the graph distance from the origin is computed by d(0, X) = |x| + |y|. Equivalently, d(U, V ) = |x| + |y| ,
where (x, y) = modGk (U − V ).
Thus, a reduced node X = (x, y) lies on the k-step boundary of the origin precisely when |x| + |y| = k. 6
The distance function is translation invariant. That is, for any three nodes U, V, T ∈ Gk , d(U, V ) = d(modGk (U + T ), modGk (V + T )) . Equivalently, d(U, V ) = d(modGk (U − V ), 0) . This property is essential for reducing the two-fault new-source problem to the case where one faulty node is the origin.
3.3
Boundary Nodes
The boundary of radius k around the origin is defined as ∂Gk (0) = {P ∈ Gk : d(0, P ) = k}. More generally, the boundary of radius k around a node A is ∂Gk (A) = {P ∈ Gk : d(A, P ) = k}. Since the diameter of Gk is k, boundary nodes are the nodes that are farthest from the center node. In the context of re-rooting-based broadcasting, such farthest nodes are important because they preserve the maximum-distance structure needed for full broadcast recovery. For the origin, the number of boundary nodes is |∂Gk (0)| = 4k. These nodes form the set of possible farthest nodes from the origin.
3.4
Valid New Sources
Let A ∈ Gk be a node. A node P ∈ Gk is called a valid new source with respect to 0 and A if d(0, P ) = k and d(A, P ) = k. Thus, P must lie in the intersection of two boundary sets: P ∈ ∂Gk (0) ∩ ∂Gk (A). The number of such nodes is denoted by count(A, k) = |∂Gk (0) ∩ ∂Gk (A)| . For two arbitrary faulty nodes A, B ∈ Gk , a node N S ∈ Gk is called a valid new source if d(N S, A) = k and d(N S, B) = k. The goal of the direct-selection problem is to find such an N S without scanning all nodes of Gk . 7
3.5
Difference Node for Two Faults
Given two faulty nodes A, B ∈ Gk , define the difference node C = modGk (B − A). If C = (c, d), then the problem of finding a node N S satisfying d(N S, A) = k and d(N S, B) = k can be translated into the equivalent problem of finding a node P satisfying d(P, 0) = k and d(P, C) = k. Once such a point P is found, the required new source is obtained by shifting back: N S = modGk (A + P ). This translation is valid because of distance translation invariance. Indeed, d(N S, A) = d modGk (A + P ), A = d(P, 0), and since B = A + C in Gk , d(N S, B) = d modGk (A + P ), modGk (A + C) = d(P, C). Therefore, if P is at distance k from both 0 and C, then N S is at distance k from both faulty nodes A and B.
3.6
Integer Labeling
The coordinate representation can also be connected to an integer labeling modulo N . Let ϕ : Gk → ZN be defined by ϕ(x + yi) ≡ kx + (k + 1)y
(mod N ),
where N = k 2 + (k + 1)2 . This mapping assigns an integer label modulo N to each node of Gk . Moreover, coordinate differences are preserved under the labeling in the sense that ϕ(U − V ) ≡ ϕ(U ) − ϕ(V )
(mod N ).
This algebraic representation is useful when implementing the proposed direct-selection method, since the difference node C = B − A can be computed either in coordinate form or through the corresponding modular labels. 8
4
Counting the Number of Valid New Sources
This section counts the valid new sources that are simultaneously at maximum graph distance from the origin and from a given node. Let Gk be a dense Gaussian network of diameter k, and let A = (ax , ay ) ∈ Gk . A node P ∈ Gk is valid with respect to 0 and A when d(0, P ) = k,
d(A, P ) = k.
Equivalently, P ∈ ∂Gk (0) ∩ ∂Gk (A). We denote the number of such nodes by count(A, k) = |{P ∈ Gk : d(0, P ) = k, d(A, P ) = k}| . The important point is that the second boundary is taken in the quotient network. Hence, a boundary intersection may occur not only with the central translated copy A + ∂Gk (0), but also with one of its neighboring quotient-lattice copies. The counting method below keeps the compact piecewise expression for the local intersection and then gives the exact quotient-lattice-aware formula used in validation.
4.1
Boundary Partition
Let Dk = {(x, y) ∈ Z2 : |x| + |y| ≤ k} be the canonical diamond of representatives. Its boundary is ∂Dk = {(x, y) ∈ Z2 : |x| + |y| = k}. We partition ∂Dk into four disjoint directed sides: S1 = {(t, k − t) : 0 ≤ t ≤ k}, S2 = {(−t, k − t) : 1 ≤ t ≤ k}, S3 = {(−t, −k + t) : 0 ≤ t ≤ k − 1}, S4 = {(t, −k + t) : 1 ≤ t ≤ k − 1}. These sets are disjoint and have sizes k + 1, k, k, and k − 1, respectively. Therefore, |∂Dk | = 4k. This partition is used only as a counting device; distances are still interpreted in the Gaussian quotient network.
9
Lemma 1. A node P is a valid new source with respect to 0 and A if and only if P ∈ ∂Gk (0) ∩ ∂Gk (A). Equivalently, after translating by A, P ∈ ∂Gk (0),
P − A ∈ ∂Gk (0).
Proof. By definition, validity means d(0, P ) = k and d(A, P ) = k. The first condition is exactly P ∈ ∂Gk (0). By translation invariance of graph distance in Gk , d(A, P ) = d(0, P − A). Thus, d(A, P ) = k if and only if P − A ∈ ∂Gk (0), or equivalently P ∈ A + ∂Gk (0) = ∂Gk (A).
4.2
Local Piecewise Boundary Count
Before incorporating quotient-lattice copies, consider the local intersection obtained from the central copy only. Define count0 (A, k) = |∂Dk ∩ (A + ∂Dk )| . Let a = max{|ax |, |ay |},
b = min{|ax |, |ay |}.
Solving the sixteen side-pair intersections between the four sides of ∂Dk and the four sides of A + ∂Dk gives the following compact local count: 4k, a = b = 0, 2k + 2 − a, a = b, 2k + 1, (a, b) = (1, 0), count0 (A, k) = a = b + 1, k + 4 − a + I(a a < 0), x y (a, b) ̸= (1, 0), 4, a ≥ b + 2. Here I(·) is 1 when the condition is true and 0 otherwise. The five cases in this expression correspond to the five possible geometric overlap patterns between the two unshifted diamond boundaries. When a = b = 0, the two centers coincide, so the two boundaries are identical and all 4k boundary nodes are counted. When a = b > 0, the shift lies on a diagonal direction; in this case two long side-overlap intervals remain, and their combined length decreases linearly as the diagonal offset a increases, giving 2k + 2 − a. The adjacent-axis case (a, b) = (1, 0) is separated because the axis shift creates an additional endpoint contact that is not captured by the neighboring near-diagonal expression. When a = b + 1, the two diamonds are one step away from diagonal alignment; the overlap consists of one main interval and several endpoint contacts, with one extra endpoint appearing exactly 10
when ax and ay have opposite signs. Finally, when a ≥ b + 2, all interval overlaps disappear and only the four corner-to-side endpoint intersections remain. Table 1: Local unshifted boundary-intersection count by position type of A. Condition on A Local count count0 (A, k) a = 0, b = 0 4k 2k + 2 − a a=b 2k + 1 (a, b) = (1, 0) a = b + 1, (a, b) ̸= (1, 0) k + 4 − a + I(ax ay < 0) 4 a≥b+2 Table 1 is useful because it explains the geometry of the boundary intersection. It also shows that, even before considering wrap-around copies, every nonzero node has at least four local candidates. However, the exact count in Gk must include quotient-lattice copies, as described next.
Figure 1: Boundary-intersection view of valid new sources. Yellow nodes represent the boundary ∂Gk (0), light-blue nodes represent the shifted boundary ∂Gk (A), and green underlined nodes represent valid new sources in ∂Gk (0) ∩ ∂Gk (A).
11
4.3
Exact Quotient-Lattice-Aware Count
The quotient lattice generated by k + (k + 1)i has basis vectors e1 = (k, k + 1),
e2 = (−(k + 1), k).
Only the central copy and the eight adjacent quotient-lattice copies can intersect the canonical boundary. Therefore, define the fixed shift set Lk = {me1 + ne2 : m, n ∈ {−1, 0, 1}}. For each side Si , let Pi (t) be its linear parameterization and let Ri be its integer parameter range. For a fixed shift L ∈ Lk and a side pair (i, j), define Tij (A, L) = {t ∈ Ri : Pi (t) = A + L + Pj (u) for some u ∈ Rj }. Each set Tij (A, L) is either empty, a single integer, or an integer interval obtained by solving two linear equations in t and u. Since multiple quotient copies can represent the same boundary node, duplicate parameter values on each side are removed by interval union. Theorem 1. For every node A ∈ Gk , the exact number of valid new sources in the Gaussian quotient network is 4 4 X [ [ count(A, k) = Tij (A, L) . i=1 L∈Lk j=1
The formula uses a fixed number of side-pair interval computations and therefore gives an O(1) counting procedure with respect to k and N . Proof. By Lemma 1, valid new sources are exactly the nodes in ∂Gk (0) ∩ ∂Gk (A). In the coordinate cover, ∂Gk (A) is represented by the shifted copies A + L + ∂Dk , where L ranges over quotient-lattice vectors. A copy can intersect the canonical boundary ∂Dk only if it is one of the nine shifts in Lk ; all other copies are separated from Dk by more than the boundary diameter in at least one lattice direction. Thus, every valid intersection is represented by some side pair Si and A + L + Sj with L ∈ Lk . For each fixed (i, j, L), equating the two side parameterizations gives a pair of linear equations in t and u, whose valid solutions form Tij (A, L). Taking the union over all j and L for each side Si removes duplicate representations, and summing over the four disjoint sides counts each boundary node exactly once. Corollary 1. For every nonzero node A ∈ Gk , count(A, k) ≥ 4. Proof. The exact quotient count contains the local central-copy contribution. From the local piecewise count in Table 1, every nonzero node has at least four local boundary intersections. Therefore, the exact quotient count is also at least four.
12
4.4
Examples for k = 5
For k = 5, the boundary of the origin contains 4k = 20 nodes. The local count gives count0 ((0, 0), 5) = 20, count0 ((1, 0), 5) = 2(5) + 1 = 11, count0 ((1, 1), 5) = 2(5) + (2 − 1) = 11, and count0 ((2, −1), 5) = 5 + (4 − 2) + 1 = 8. The quotient-lattice-aware formula in Theorem 1 evaluates the exact count in Gk by adding all valid shifted-copy intersections and removing duplicates.
5
Direct New-Source Selection for Two Faulty Nodes
The previous section showed how valid new sources can be counted without scanning the network. This section gives a direct construction for selecting one such source for two arbitrary distinct faulty nodes. Let A = (a1 , a2 ), B = (b1 , b2 ) be two distinct faulty nodes in Gk . We seek N S ∈ Gk such that d(N S, A) = d(N S, B) = k. If A = B, the problem reduces to the one-fault case, where any node on ∂Gk (A) is valid. Thus, the nontrivial case is A ̸= B.
5.1
Translation to the Origin
Define the difference node C = modGk (B − A) = (c, d). Instead of searching directly for N S, we first find P = (p, q) satisfying d(P, 0) = k,
d(P, C) = k.
Then the required new source is N S = modGk (A + P ).
13
Figure 2: Translation of the two-fault new-source problem. The original faulty-node pair A, B is translated to 0, C, where C = modGk (B − A). After finding P such that d(P, 0) = d(P, C) = k, the source is shifted back as N S = modGk (A + P ). Lemma 2. Let A, B ∈ Gk and C = modGk (B − A). If P ∈ Gk satisfies d(P, 0) = d(P, C) = k, then N S = modGk (A + P ) satisfies d(N S, A) = d(N S, B) = k. Proof. By translation invariance of graph distance, d(modGk (A + P ), A) = d(P, 0). Also, since B = modGk (A + C), d(modGk (A + P ), B) = d(P, C). The result follows from d(P, 0) = d(P, C) = k.
5.2
Shifted Algebraic Construction of P
A purely unshifted construction would solve |p| + |q| = k,
|p − c| + |q − d| = k.
This is not sufficient in the quotient network because the second boundary may intersect the first boundary through a neighboring quotient-lattice copy. Therefore, we use the fixed shift set Lk = {m(k, k + 1) + n(−(k + 1), k) : m, n ∈ {−1, 0, 1}}. For each L = (Lx , Ly ) ∈ Lk , set c′ = c + L x ,
d′ = d + Ly .
14
The selector solves |p| + |q| = k,
|p − c′ | + |q − d′ | = k.
The absolute values are removed by considering the signs of p,
q,
p − c′ ,
q − d′ .
For a sign tuple (s1 , s2 , s3 , s4 ) ∈ {±1}4 , the signed system is s1 p + s2 q = k, s3 p + s4 q = M,
M = k + s 3 c′ + s 4 d ′ .
Let D = s1 s4 − s2 s3 . If D ̸= 0, Cramer’s rule gives p=
ks4 − s2 M , D
q=
s1 M − ks3 . D
The candidate is accepted only if p and q are integers and the two graph-distance conditions hold. If D = 0, the two signed equations are parallel. When (s3 , s4 ) = (s1 , s2 ), consistency requires M = k and the first boundary line is parameterized by p = s1 t,
q = s2 (k − t),
0 ≤ t ≤ k.
The second boundary imposes max(0, s1 c′ ) ≤ t ≤ min(k, k − s2 d′ ). When (s3 , s4 ) = (−s1 , −s2 ), consistency requires M = −k and the valid interval is max(0, k − s2 d′ ) ≤ t ≤ min(k, s1 c′ ). In either parallel case, a valid endpoint is selected if the interval is nonempty. Lemma 3. For a canonical difference node C ∈ Dk , any intersection between ∂Dk and a quotient copy of C + ∂Dk is represented by one of the nine shifts in Lk . Proof. Let e1 = (k, k + 1), e2 = (−(k + 1), k), L = me1 + ne2 . Suppose that a shifted copy contributes an intersection. Then there exist P, Q ∈ ∂Dk such that P = C + L + Q. 15
Thus, C + L = P − Q. Since P, Q ∈ Dk , we have ∥P ∥1 ≤ k and ∥Q∥1 ≤ k, and hence ∥C + L∥1 = ∥P − Q∥1 ≤ ∥P ∥1 + ∥Q∥1 ≤ 2k. Also, because C is the canonical representative of a node in Gk , C ∈ Dk and therefore ∥C∥1 ≤ k. The reverse triangle inequality then gives the necessary condition ∥L∥1 ≤ ∥C + L∥1 + ∥C∥1 ≤ 3k. Now compute the Manhattan length of a quotient-lattice shift: ∥L∥1 = |mk − n(k + 1)| + |m(k + 1) + nk|. A direct case check on the signs of m and n shows that if (m, n) is outside the block {−1, 0, 1}2 , then |mk − n(k + 1)| + |m(k + 1) + nk| > 3k. Therefore, any quotient copy that can intersect the canonical boundary must have m, n ∈ {−1, 0, 1}, which gives exactly the central copy and the eight adjacent copies.
16
Algorithm 1 Shifted Constant-Time Direct New-Source Selection Require: Network parameter k; faulty nodes A, B ∈ Gk Ensure: A valid new source N S 1: C ← modGk (B − A); write C = (c, d) 2: e1 ← (k, k + 1), e2 ← (−(k + 1), k) 3: for all m, n ∈ {−1, 0, 1} do 4: (Lx , Ly ) ← me1 + ne2 5: c′ ← c + Lx , d′ ← d + Ly 6: for all (s1 , s2 , s3 , s4 ) ∈ {±1}4 do 7: M ← k + s3 c′ + s4 d′ 8: D ← s1 s4 − s2 s3 9: if D ̸= 0 then 10: p ← (ks4 − s2 M )/D 11: q ← (s1 M − ks3 )/D 12: if p, q are integers and |p| + |q| = k and |p − c′ | + |q − d′ | = k then 13: N S ← modGk (A + (p, q)) 14: if d(N S, A) = k and d(N S, B) = k then 15: return N S 16: end if 17: end if 18: else 19: Apply the parallel interval rules for c′ , d′ 20: if a verified endpoint candidate (p, q) is obtained then 21: return modGk (A + (p, q)) 22: end if 23: end if 24: end for 25: end for Theorem 2 (Correctness of the shifted direct-selection algorithm). For any two distinct faulty nodes A, B ∈ Gk , Algorithm 1 returns a valid new source N S satisfying d(N S, A) = d(N S, B) = k. Proof. The published re-rooting result guarantees that a common distance-k node exists for every two-fault configuration in Gk . By Lemma 3, the corresponding boundary intersection is represented by one of the nine shifts in Lk . For that shift, the signs of p, q, p−c′ , q−d′ determine one of the sixteen signed systems. If the system is nonparallel, Cramer’s rule recovers the candidate. If it is parallel, the interval rule recovers a candidate from the nonempty interval. The final verification accepts only candidates satisfying d(P, 0) = d(P, C) = k. Lemma 2 then gives d(N S, A) = d(N S, B) = k.
17
5.3
Worked Example
Let k = 5 and suppose the two faulty nodes are A = (1, 1),
B = (3, 1).
Then C = modG5 (B − A) = (2, 0). Using the unshifted copy L = (0, 0) and the sign tuple (s1 , s2 , s3 , s4 ) = (1, 1, −1, 1), we have M = 5 + (−1)(2) + (1)(0) = 3,
D = 2.
Thus, p=
5(1) − 1(3) = 1, 2
q=
1(3) − 5(−1) = 4. 2
So P = (1, 4), and |P |1 = |1| + |4| = 5,
|P − C|1 = |1 − 2| + |4| = 5.
Therefore d(P, 0) = d(P, C) = 5. Shifting back gives N S = modG5 (A + P ) = modG5 (2, 5) = (−3, −1). A direct distance check gives d(N S, A) = d(N S, B) = 5, so N S = (−3, −1) is a valid new source.
5.4
Constant-Time Selection
The shifted direct construction checks nine quotient-lattice shifts and sixteen sign tuples for each shift. Therefore, the maximum number of algebraic cases is 9 × 16 = 144. Each case uses a constant number of arithmetic operations. Under the standard word-RAM model, where arithmetic on node coordinates is treated as constant time, the selector runs in O(1) time. This replaces the O(k) boundary-search step used in the published re-rooting method with a constant-time algebraic selection step.
6
Complexity Comparison
This section compares the proposed shifted direct selector with two search-based alternatives. Let Gk contain N = k 2 + (k + 1)2 nodes and have diameter k. 18
A full node scan tests every node X ∈ Gk and checks whether d(X, A) = d(X, B) = k. Its worst-case complexity is O(N ), equivalently O(k 2 ). A boundary scan first translates the problem to the origin and then tests the 4k nodes of ∂Gk (0), giving O(k) complexity. The proposed method checks only nine quotient-lattice shifts and sixteen sign tuples for each shift, giving at most 144 algebraic cases and O(1) complexity. Table 2: Complexity comparison of new-source selection methods. Method Candidates or cases Full node scan N = k 2 + (k + 1)2 Boundary scan 4k 9 × 16 = 144 Proposed shifted selector
Complexity O(N ) O(k) O(1)
The comparison shows that the proposed selector has a fixed algebraic workload independent of both k and N . This is the central algorithmic improvement over the published boundary-search source-selection step.
7
Computational Validation
This section validates the quotient-lattice-aware counting formula and the shifted direct new-source selector. The validation uses the dense Gaussian networks with k ∈ {10, 25, 50, 100, 200},
N = k 2 + (k + 1)2 .
All distance checks are performed using graph distance in Gk .
7.1
Validation of the Counting Formula
For each tested node A ∈ Gk , the quotient-lattice-aware count from Theorem 1 was compared with brute-force counting over the 4k boundary nodes. For k = 10, 25, and 50, all nodes were tested. For k = 100 and k = 200, 10,000 nodes were sampled. Table 3 shows zero mismatches and zero maximum error in every tested case. Table 3: Validation of the quotient-lattice-aware counting formula. k N Nodes tested 10 221 221 25 1301 1301 50 5101 5101 100 20201 10000 200 80401 10000
7.2
Mismatches Max error 0 0 0 0 0 0 0 0 0 0
Validation of Direct New-Source Selection
The second experiment validates the shifted direct selector for arbitrary distinct faulty nodes. For each value of k, 100,000 random fault pairs were tested. For every pair, the returned 19
source was verified by checking d(N S, A) = k,
d(N S, B) = k.
No boundary-search fallback was used. Table 4 reports 500,000 valid outputs and zero failures. The maximum observed number of checked shifted sign cases was 51, well below the theoretical bound of 144. Table 4: Validation of shifted direct new-source selection. k N Pairs 10 221 100000 25 1301 100000 50 5101 100000 100 20201 100000 200 80401 100000
7.3
Valid Failed 100000 0 100000 0 100000 0 100000 0 100000 0
Max cases 51 51 51 51 51
Re-Rooting Broadcast Validation
A full re-rooting validation was also performed using one- and two-node fault scenarios and four fault-placement modes: random, near-source, critical-position, and close-pair. For each k, each fault count, and each mode, 1000 trials were generated, giving 40,000 total raw trials. The proposed method succeeded in every trial and reached exactly N − f non-faulty nodes, where f is the number of faulty nodes. Table 5 gives the results aggregated by k and fault count. Table 5: Re-rooting broadcast validation aggregated across all four fault-placement modes. k 10 10 25 25 50 50 100 100 200 200
7.4
N Faults 221 1 221 2 1301 1 1301 2 5101 1 5101 2 20201 1 20201 2 80401 1 80401 2
Trials 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000
Base succ. (%) 5.275 2.350 2.425 0.725 1.150 0.325 0.450 0.100 0.250 0.075
Prop. succ. (%) 100.000 100.000 100.000 100.000 100.000 100.000 100.000 100.000 100.000 100.000
Avg. base reach 202.452 194.500 1209.836 1193.119 4855.743 4838.786 19302.131 19253.217 76962.268 76748.182
Avg. prop. reach Avg. total steps 220.000 18.418 219.000 17.815 1300.000 46.202 1299.000 44.491 5100.000 92.252 5099.000 88.730 20200.000 184.587 20199.000 177.260 80400.000 369.395 80399.000 354.469
Runtime Comparison
The final experiment compares the original boundary-search selector with the proposed shifted direct selector. For each k, the runtime is averaged over 100,000 randomly sampled fault pairs. Table 6 shows that the shifted selector has a small fixed overhead for small networks, but its runtime remains nearly stable as k grows. It becomes faster for larger networks and reaches a 5.92× speedup at k = 200.
20
Table 6: Average runtime per new-source selection query. k N Boundary ms 10 221 0.003800 0.011542 25 1301 50 5101 0.024058 0.043175 100 20201 200 80401 0.113837
Shifted ms 0.012471 0.017004 0.017400 0.015310 0.019244
Speedup 0.30× 0.68× 1.38× 2.82× 5.92×
Table 7: Search-space size or algebraic-case bound for each method. k Full scan Boundary scan 10 221 40 1301 100 25 50 5101 200 100 20201 400 200 80401 800
Shifted direct 144 144 144 144 144
Overall, the validation confirms three points. First, the quotient-lattice-aware count matches brute force in all tested cases. Second, the shifted selector returned valid new sources for all 500,000 sampled pairs without fallback. Third, the complete re-rooting simulation achieved 100% proposed recovery across 40,000 trials.
8
Conclusion
This paper extended the published re-rooting-based fault-tolerant broadcasting framework for dense Gaussian networks by replacing the O(k) boundary-search source-selection step with a constant-time algebraic method. The counting problem was formulated as a boundaryintersection problem in the Gaussian quotient. A compact piecewise formula was retained for the local unshifted boundary intersection, and an exact quotient-lattice-aware counting formula was developed using a fixed union of side-pair intervals over nine quotient-lattice copies. For two faulty nodes A and B, the source-selection problem was translated to the difference node C = modGk (B − A). The proposed shifted selector searches a fixed set of nine lattice shifts and sixteen sign configurations for each shift. Nonparallel systems are solved using Cramer’s rule, while parallel systems are handled by constant-time interval-endpoint selection. Hence, at most 9 × 16 = 144 shifted sign cases are checked, and the method runs in O(1) time under the standard word-RAM model. Computational validation confirmed the theoretical claims. The quotient-lattice-aware count produced zero mismatches over 26,623 tested nodes. The shifted selector returned valid new sources for all 500,000 sampled fault pairs. In the re-rooting broadcast validation, the proposed method achieved 40,000 successful recoveries out of 40,000 trials and reached exactly N −f non-faulty nodes in every configuration. Runtime results show that the shifted
21
selector becomes faster than boundary search for larger networks, with a 5.92× speedup at k = 200. Future work may investigate source ranking when multiple valid candidates exist, extend the method to link failures or dynamic faults, and study whether similar quotient-latticeaware constant-time recovery rules can be developed for other algebraic interconnection networks.
A
Side-Pair Interval Counting Details
This appendix gives the constant-size side-pair interval calculation used in Theorem 1. Each side Si is written as Pi (t) = oi + vi t, t ∈ Ri , where oi vi Ri i 1 (0, k) (1, −1) [0, k] 2 (0, k) (−1, −1) [1, k] 3 (0, −k) (−1, 1) [0, k − 1] 4 (0, −k) (1, 1) [1, k − 1]. For a node A = (ax , ay ), a quotient-lattice shift L = (Lx , Ly ), and a side pair (i, j), an intersection point satisfies oi + vi t = A + L + oj + vj u. Equivalently, vi t − v j u = A + L + o j − o i . This is a 2 × 2 integer linear system in the side parameters t and u. If the determinant is nonzero, there is at most one solution, and it is counted only when both parameters lie in their valid integer ranges. If the determinant is zero, the two side lines are parallel. The consistency condition is checked first; if the system is consistent, the valid values of t form an integer interval after imposing the range restriction on u. For each fixed first side Si , the intervals obtained from all j and all L ∈ Lk are merged before counting. This removes duplicate quotient representations of the same boundary node. The exact count is therefore count(A, k) =
4 4 X [ [
Tij (A, L) ,
i=1 L∈Lk j=1
which is the formula used in Theorem 1 and in the computational validation.
Acknowledgments The authors would like to acknowledge the support of Kuwait University and its Computer Science Department.
22
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. [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] C. Martı́nez, R. Beivide, J. Gutiérrez, and E. M. Gabidulin, “On the perfect tdominating set problem in circulant graphs and codes over Gaussian integers,” in Proc. IEEE International Symposium on Information Theory (ISIT), 2005, pp. 254–258. [5] 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. [6] A. Grama, A. Gupta, G. Karypis, and V. Kumar, Introduction to Parallel Computing, 2nd ed. Pearson, 2003. [7] J. Duato, S. Yalamanchili, and L. Ni, Interconnection Networks: An Engineering Approach. Morgan Kaufmann, 2002. [8] W. J. Dally and B. Towles, Principles and Practices of Interconnection Networks. Morgan Kaufmann, 2004. [9] 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. [10] S. Pasricha and N. Dutt, On-Chip Communication Architectures: System-on-Chip Interconnect. Morgan Kaufmann, 2008. [11] J. Flich and D. Bertozzi, Designing Network-on-Chip Architectures in the Nanoscale Era. CRC Press, 2010. [12] 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. [13] Y. Saad and M. H. Schultz, “Topological properties of hypercubes,” IEEE Transactions on Computers, vol. 37, no. 7, pp. 867–872, 1988. [14] B. Albader, M. R. Al-Mulla, and G. Hassan, “Re-rooting-based fault-tolerant broadcasting in dense Gaussian networks,” IEEE Access, 2026. 23
[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. [16] 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. [17] T. Song, Y. Xie, Y. Ye, Y. Du, B. Liu, and Y. Liu, “Gaussian-based optical networkson-chip: Performance analysis and optimization,” Nano Communication Networks, vol. 24, Art. no. 100286, 2020.
24