Fault-Tolerant Shared-Relay Communication in Circulant Interconnection Networks Bader Albader, Galal Hassan, and Mohamed R. Al-Mulla
arXiv:2606.19833v1 [cs.DC] 18 Jun 2026
Department of Computer Science, Faculty of Science, Kuwait University, Kuwait [email protected]
Abstract Circulant interconnection networks provide symmetric addressing, compact generator descriptions, and uniform local connectivity. This paper maps a degree–redundancy landscape for a fault-tolerant two-hop primitive in directed circulants: given n nodes and degree budget m, how large can the worst-case shared-relay multiplicity R(n, m) be? A node is a shared relay for an ordered terminal pair if it has outgoing links to both terminals; an f -relay-fault-tolerant circulant requires at least f + 1 such relays for every pair. The underlying feasibility condition is a cyclic difference-multiplicity condition, which we use as a mathematical tool rather than claim as a new object. The contribution is the network-design framework around this tool: the parameters R(n, m) and Df (n), a negative theorem for interval circulants, relay-table preprocessing and lookup algorithms, adversarial and random failure guarantees, load-balance scope, certified upper-bound interpretation of heuristic designs, exact small-n calibration, a software lookup-versus-search microbenchmark, and a reproducible study of 526,539 generator sets. The results show that generator choice critically determines worst-case relay survivability: optimized threshold designs achieve f -relay-fault tolerance within about 1.16–1.63 of the counting lower bound, while standard interval generators can fail structurally even at much larger degrees.
Keywords: Circulant networks, Cayley graphs, interconnection networks, fault-tolerant communication, shared relay, two-hop recovery, relay routing, difference bases, network robustness.
1
Introduction
Circulant interconnection networks are natural models for parallel and distributed systems because a node can be addressed by one integer modulo n and its outgoing links are obtained by adding a fixed generator set. A directed circulant is written as G = Cay(Zn , S), where S ⊆ Zn and x→y
⇐⇒ 1
y − x ∈ S.
Thus every node has the same out-degree |S|, the same local connection pattern, and the same routing table up to translation. This paper studies a local fault-tolerance primitive that is different from conventional graph connectivity, diameter, or fault diameter. For two distinct terminal nodes u, v ∈ Zn , a node r is a shared relay for the ordered pair (u, v) if r → u and r → v. If every ordered terminal pair has many shared relays, then pairwise relay-assisted communication, acknowledgement aggregation, rendezvous communication, replicated control signaling, or local recovery can survive relay-node failures without running a global rerouting search. Fig. 1 illustrates the idea on two small directed circulants. The same terminal offset can have no shared relay under a poorly distributed generator set, while a more distributed generator set creates multiple immediate relay alternatives for the same pair.
Figure 1: Shared relays in two small directed circulants. Nodes are arranged on a ring. Red nodes are the terminals. Green nodes are shared relays and highlighted green arcs show the two outgoing relay links. For the same terminal offset, the weaker generator set has no shared relay. Red dashed arcs indicate one-sided attempts that reach u but not v, while orange dashed arcs indicate attempts that reach v but not u. The stronger generator set has two shared relays. The relevant design question is a degree–redundancy question: how much circulant degree is required to guarantee many immediate relay alternatives for every terminal pair? We formalize this through two parameters. The first is Df (n), the minimum directed circulant degree required so that every ordered terminal pair survives any f relay failures. The second is R(n, m), the maximum worst-case shared-relay multiplicity achievable by a degree-m circulant on n nodes. The difference-multiplicity equivalence is the bridge, not the destination. The networkdesign question studied here is: for a fixed degree budget m on n nodes, what worst-case relay redundancy R(n, m) is achievable, and how should a network exploit the resulting relay alternatives after failures? This R(n, m) landscape has not previously been mapped 2
for practical circulant generator families. The paper therefore treats known difference-basis theory as background and focuses on the network-layer consequences: failure semantics, relay tables, recovery algorithms, load metrics, memory costs, exact small-instance calibration, measured lookup costs, and empirical design guidance for circulant interconnection networks.
1.1
Contributions
The paper makes the following contributions, grouped by role. • Network metric and theory. It defines shared-relay multiplicity as a local faulttolerance metric, introduces Df (n) and R(n, m) as degree–redundancy parameters, and proves the exact relay–difference equivalence, counting lower bounds, monotonicity, transfer bounds, adversarial recovery guarantees, and random-failure survival probabilities. • Implementable relay layer. It gives preprocessing, deterministic recovery, loadaware relay selection, and vectorized greedy construction algorithms. The recovery algorithms are proved correct, while the greedy construction is explicitly treated as a heuristic whose outputs are evaluated exactly. • Systems cost and balance. It quantifies preprocessing, routing-table storage, online lookup cost, and a scoped translation-invariant relay-balance property for complete offset sweeps, while explicitly stating that non-uniform traffic requires measured load counters or traffic-aware ordering. • Reproducible design study. It reports a checkpointed experiment over 526,539 circulant designs with n ∈ {251, 503, 1009, 2003, 5003, 10007} and f ∈ {0, . . . , 5}. The optimized run completed in about 3995 seconds and produced exact multiplicity values for every design.
1.2
What This Enables Beyond the Difference-Basis Statement
The difference-basis equivalence alone says that a set of generator differences covers every terminal offset. It does not specify how a network should store relay alternatives, skip failed relays, choose among multiple surviving relays, quantify relay-table memory, compare adversarial and random failure models, or expose why common generator families behave poorly under worst-case relay redundancy. Those questions are the systems contribution of this paper. The framework converts the abstract multiplicity condition into a routing-table primitive: for every offset d, store the offset pairs (a, b) with b − a = d; for terminals (u, v), convert each (a, b) into relay r = u − a = v − b; skip failed relays; optionally choose the least-loaded survivor.
3
2
Related Work
2.1
Circulant and Cayley Interconnection Networks
Circulant and Cayley networks have long been studied because they combine symmetry, compact addressing, and efficient routing. Their standard matrix representation and algebraic shift structure are treated in classical circulant-matrix references [6, 7]; this is the algebraic basis for representing every local connection pattern by a single generator vector. Classical network work considers connectivity, diameter, broadcasting, containers, wide diameter, fault diameter, and routing in circulant and Cayley networks [2, 1, 8, 9, 3, 4, 5]. Circulant and loop-network routing also appears in fault-tolerant distributed-loop routing and recent network-on-chip studies [10, 11, 12]. Ring interconnects, which are degree-two circulants, have also appeared in commercial and research multicore settings [16, 17]. The present paper addresses a complementary local primitive: common in-neighborhood relay multiplicity for immediate two-hop relay alternatives without path search.
2.2
Difference Bases, g-Difference Bases, and Difference Covers
A subset B of an abelian group G is a difference basis if every group element can be represented as a − b for some a, b ∈ B. Banakh and Gavrylkiv studied difference bases in cyclic groups and proved lower and upper bounds for the cyclic difference size [13]. Multiplicity variants require every element to have at least g difference representations. Schmutz and Tait studied cardinalities of g-difference bases and proved asymptotic results for normalized sizes in their setting [14]. Recent work of Li and Yip treats generalized additive and difference bases in finite abelian groups [15]. The latter two sources are cited as arXiv preprints; therefore, the multiplicity-g asymptotic discussion below is stated as a transfer statement rather than as a new unconditional theorem for cyclic circulants.
2.3
Common-Neighbor Counts
Common-neighbor counts also arise in special Cayley and circulant graphs. Klotz and Sander derived formulas for common neighbors in unitary Cayley graphs [18]. In contrast, the present paper attaches a fault-tolerance semantics to the common in-neighborhood: it is the set of immediate relay alternatives that survive relay-node failures.
4
3
Network Model, Notation, and Parameters Table 1: Notation used throughout the paper. Symbol Meaning n Zn S m G u, v d R(u, v) λS (d) R(S) R(n, m) Df (n) F Pd
number of nodes cyclic node set {0, . . . , n − 1} circulant generator set, S ⊆ Zn \ {0} directed degree, m = |S| directed circulant Cay(Zn , S) ordered terminal pair, u ̸= v terminal offset d = v − u (mod n) shared-relay set of (u, v) number of ordered generator pairs with b − a = d worst-case nonzero relay multiplicity best possible R(S) among degree-m circulants minimum degree for f -relay-fault tolerance failed relay-node set relay-offset table for terminal offset d
Let n ≥ 2 and let S ⊆ Zn . The directed circulant G = Cay(Zn , S) has vertex set Zn and directed edge set E = {(x, y) : y − x ∈ S}. The directed degree is m = |S|. Unless otherwise stated, 0 ∈ / S, so self-loops are excluded. For a node u, its in-neighborhood is N − (u) = {r ∈ Zn : u − r ∈ S} = u − S. Definition 1 (Shared-relay set). For distinct u, v ∈ Zn , the shared-relay set of (u, v) is R(u, v) = N − (u) ∩ N − (v). Thus r ∈ R(u, v) if and only if r → u and r → v. Definition 2 (Difference multiplicity). For d ∈ Zn , define λS (d) = |{(a, b) ∈ S 2 : b − a = d}|. The worst-case nonzero shared-relay multiplicity is R(S) =
min λS (d).
d∈Zn \{0}
The definition of λS (d) includes all ordered pairs in S 2 . For d ̸= 0, every counted pair automatically has a ̸= b. For d = 0, because S is a set, the only counted pairs are (a, a) and hence λS (0) = m. Throughout the paper, fault tolerance depends only on nonzero offsets. 5
Definition 3 (f -relay-fault tolerance). The circulant Cay(Zn , S) is f -relay-fault-tolerant if for every ordered pair u ̸= v and every set F ⊆ Zn with |F | ≤ f , there exists a relay r ∈ R(u, v) \ F. Definition 4 (Degree–redundancy parameters). For 0 ≤ m ≤ n − 1, define R(n, m) =
max R(S).
S⊆Zn \{0} |S|=m
For the base case m = 0, the maximum is taken over the single empty generator set and R(n, 0) = 0. For f ≥ 0, define Df (n) = min{m ∈ {0, . . . , n − 1} : R(n, m) ≥ f + 1}, when such a degree exists.
4
Relay–Difference Equivalence and Design Bounds
Theorem 1 (Relay–difference equivalence). For any distinct u, v ∈ Zn , |R(u, v)| = λS (v − u). Moreover, the map (a, b) ∈ S 2 ,
b−a=v−u
to r =u−a=v−b is a bijection between difference representations of v − u and shared relays of (u, v). Proof. If (a, b) ∈ S 2 and b − a = v − u, define r = u − a. Then u − r = a ∈ S and v − r = v − u + a = b ∈ S, so r ∈ R(u, v). Conversely, if r ∈ R(u, v), set a = u − r and b = v − r. Then a, b ∈ S and b − a = (v − r) − (u − r) = v − u. The two maps are inverse to each other, proving the bijection. Counting gives the equality. Corollary 1. A directed circulant Cay(Zn , S) is f -relay-fault-tolerant if and only if R(S) ≥ f + 1. Proof. By Theorem 1, every ordered pair with offset d ̸= 0 has exactly λS (d) shared relays. Thus every pair has at least f + 1 shared relays if and only if R(S) ≥ f + 1. Removing at most f failed relays cannot exhaust a set of size at least f + 1. Conversely, if some pair (u, v) has at most f relays, the adversary may choose F = R(u, v); then |F | ≤ f and every shared-relay option for that pair is failed. 6
Theorem 2 (Counting upper bound on R(n, m)). For every n and m, m(m − 1) R(n, m) ≤ . n−1 Proof. For nonzero offsets, every ordered pair (a, b) ∈ S 2 with a ̸= b contributes to exactly one d = b − a ̸= 0. Since there are m(m − 1) ordered pairs with a ̸= b, X λS (d) = m(m − 1). d̸=0
The minimum over n − 1 nonzero offsets is at most the average. Maximizing over S gives the result. Theorem 3 (Interval circulants are structurally weak). Let Sm = {1, 2, . . . , m} ⊆ Zn . If n > 2m − 1, then R(Sm ) = 0. More precisely, for 1 ≤ d ≤ m − 1, λSm (d) = m − d; for n − m + 1 ≤ d ≤ n − 1, λSm (d) = m − (n − d); and all remaining nonzero offsets have multiplicity zero. Proof. For a, b ∈ Sm , the ordinary integer difference b − a lies in [−m + 1, m − 1]. Therefore, modulo n, the only nonzero residues represented by such differences are 1, . . . , m − 1 and n−m+1, . . . , n−1. If n > 2m−1, then n−m+1 > m, so the upper arc {n−m+1, . . . , n−1} begins strictly above the lower arc {1, . . . , m − 1}; the two arcs are therefore disjoint and together cover exactly 2(m−1) of the n−1 nonzero offsets, leaving n−1−2(m−1) = n−2m+ 1 ≥ 1 offsets with multiplicity zero. For 1 ≤ d ≤ m−1, the pairs are (1, 1+d), . . . , (m−d, m), giving m−d representations. The negative offsets are symmetric: residue n−d has the m−d representations (1 + d, 1), . . . , (m, m − d). All other nonzero offsets have no representation. The boundary is tight: when n = 2m − 1, the lower arc and upper arc partition all nonzero residues. This theorem gives a non-empirical reason why interval generator sets are poor sharedrelay designs: unless their degree is already at least roughly half the network size, they are not even 0-relay-fault-tolerant. Corollary 2 (Degree lower bound). If Cay(Zn , S) is f -relay-fault-tolerant with |S| = m, then m(m − 1) ≥ (f + 1)(n − 1). Consequently, & Df (n) ≥
' p 1 + 1 + 4(f + 1)(n − 1) . 2
Proof. By Corollary 1, every nonzero offset must have multiplicity at least f + 1. Summing over the n − 1 nonzero offsets gives the first inequality. The displayed lower bound follows by solving the quadratic inequality in m.
7
Proposition 1 (Monotonicity). For fixed n, R(n, m) is nondecreasing in m, and Df (n) is nondecreasing in f . Proof. If S has degree m and x ∈ / S ∪ {0}, then every old difference representation remains present in S ∪ {x}. Hence R(S ∪ {x}) ≥ R(S). For every degree-m set S, the set S ∪ {x} is one admissible degree-(m + 1) set, so R(n, m + 1) = max R(T ) ≥ R(S ∪ {x}) ≥ R(S). |T |=m+1
Taking the maximum over all degree-m sets S gives R(n, m + 1) ≥ R(n, m). Since the requirement R(S) ≥ f + 1 becomes stronger as f increases, Df (n) is nondecreasing in f . Proposition 2 (Verifiable certificates for relay redundancy). For a fixed generator set S with |S| = m, the value R(S) can be verified in O(m2 + n) time and O(n) auxiliary space by enumerating all ordered pairs (a, b) ∈ S 2 , incrementing the counter for d = b − a, and taking the minimum over the n − 1 nonzero counters. Consequently, the decision problem ∃S ⊆ Zn \ {0},
|S| = m,
R(S) ≥ t
belongs to NP when S is used as the certificate. Proof. There are m2 ordered pairs in S 2 . Each pair contributes to exactly one modular difference counter, and the m diagonal pairs contribute only to the zero offset. After all counters are built, scanning the n − 1 nonzero counters gives R(S). If R(S) ≥ t, the set S is a polynomial-size certificate for the displayed existential statement, and the verification just described is polynomial in the input size when the group elements are listed explicitly. Corollary 3 (Certified upper bounds from constructed designs). If an experiment outputs a degree-m generator set S with R(S) ≥ f + 1, then the output is a verifiable certificate that Df (n) ≤ m. If an exhaustive search additionally proves that no degree below m achieves R(S) ≥ f + 1, then Df (n) = m. Proof. The first statement is immediate from Definition 4 and Corollary 1. The second adds the matching nonexistence certificate over all smaller degrees. Proposition 3 (Transfer from loop-tolerant multiplicity). Let A ⊆ Zn be a set, possibly containing 0, such that every nonzero d has at least g ordered representations b − a = d with a, b ∈ A. Let S = A \ {0}. Then for every d ̸= 0, λS (d) ≥ λA (d) − 2. Consequently, if g ≥ f + 3, then S is f -relay-fault-tolerant. Proof. For a fixed nonzero d, the representations counted by λA (d) that use 0 are only (0, d) and (−d, 0), when the corresponding nonzero elements belong to A. Thus deleting 0 removes at most two representations. The final statement follows from λS (d) ≥ g − 2 ≥ f + 1. 8
Example 1 (The zero-removal loss can be two). In Z8 , let A = {0, 1, 6, 7} and consider d = 1. The representations are (0, 1),
(6, 7),
(7, 0),
so λA (1) = 3. Removing 0 leaves S = {1, 6, 7} and only (6, 7) remains, so λS (1) = 1. The loss is exactly two. By contrast, if A = {0, 1, 6}, then deleting 0 removes only the representation (0, 1) for d = 1. Theorem 4 (Unconditional lower-bound scale). For every fixed f ≥ 0, p Df (n) = Ω (f + 1)n . More explicitly, & Df (n) ≥
1+
' p 1 + 4(f + 1)(n − 1) . 2
Proof. This is exactly Corollary p 2; the asymptotic form follows because the leading term of the displayed lower bound is (f + 1)n. Remark 1 (Conditional construction-transfer context). For f = 0, the lower-bound scale can be compared with peer-reviewed cyclic difference-basis upper bounds such as those of Banakh and Gavrylkiv [13]. For f ≥ 1, we do not state a peer-reviewed unconditional cyclic upper-bound theorem here. √ Instead, any explicit cyclic multiplicity-(f + 3) difference-basis n) would transfer through Proposition 3 to a directed circulant construction of size Of ( √ family with Df (n) = Of ( n). This observation is used only as context for future hybrid design and not as a claimed theorem of the present paper.
4.1
Worked Difference-Multiplicity Examples
Example 2 (A small generator set). Let n = 13 and S = {1, 3, 9}. The nonzero multiplicities are d 1 2 3 4 5 6 7 8 9 10 11 12 λS (d) 0 1 0 0 1 1 1 1 0 0 1 0. Therefore R(S) = 0. For d = 4, there is no pair (a, b) ∈ S 2 with b − a ≡ 4 (mod 13), so a terminal pair at offset 4 has no shared relay. Example 3 (Interval generators fail worst-case coverage). Let n = 13 and S = {1, 2, 3, 4}. Then (λS (1), . . . , λS (12)) = (3, 2, 1, 0, 0, 0, 0, 0, 0, 1, 2, 3), so R(S) = 0. In particular, offsets 4, 5, 6, 7, 8, 9 have no shared relays. A same-degree translated Singer difference set, for example S ′ = {1, 2, 4, 10}, has λS ′ (d) = 1 for every d ̸= 0 in Z13 and hence is 0-relay-fault-tolerant. This is self-contained in the following ordered-pair table:
9
d
(a, b)
d
(a, b)
d
(a, b)
1 4 7 10
(1,2) (10,1) (10,4) (4,1)
2 5 8 11
(2,4) (10,2) (2,10) (4,2)
3 6 9 12
(1,4) (4,10) (1,10) (2,1)
Each entry satisfies b − a ≡ d (mod 13); for example, the d = 7 entry uses (a, b) = (10, 4) because 4 − 10 ≡ −6 ≡ 7 (mod 13). Fig. 2 visualizes this phenomenon at a larger size. The worst-case bar, not the average bar, determines the relay-fault tolerance.
Figure 2: Difference-multiplicity spectra for two degree-22 generator sets on n = 251. The interval set has many offsets below the threshold, while the greedy set lifts all nonzero offsets to at least one shared relay.
5
Failure Models and Recovery Guarantees
Theorem 5 (Worst-case relay recovery). If R(S) ≥ f + 1, then after any failed relay set F ⊆ Zn with |F | ≤ f , every ordered terminal pair u ̸= v has a surviving relay in R(u, v) \ F . Proof. By Theorem 1, |R(u, v)| = λS (v − u) ≥ R(S) ≥ f + 1. A set F of at most f failed nodes cannot contain all elements of R(u, v). Theorem 6 (Random relay failures). Fix a terminal pair (u, v) with k = |R(u, v)|. If 0 ≤ q ≤ n failed relay nodes are chosen uniformly at random from Zn , then the pair survives with probability Psurv (n, k, q) = 1 − where the numerator is interpreted as 0 if q < k.
10
n−k q−k n q
,
Proof. The pair fails exactly when all k of its shared relays are included among the q failed nodes. If q < k, this event is impossible. If q ≥ k, the number offailure sets containing all k relays is n−k , while the number of all q-node failure sets is nq . Subtracting this failure q−k probability from one gives the formula. Corollary 4 (Independent relay failures). If each relay node fails independently with probability p, then a terminal pair with k shared relays fails with probability pk . In particular, if R(S) ≥ f + 1, then every pair has independent-failure survival probability at least 1 − pf +1 . Proof. A pair fails exactly when all of its k shared relays fail. Under independent node failures this event has probability pk . Since k ≥ R(S) ≥ f + 1, the failure probability is at most pf +1 . Example 4 (Worst-case versus random failures). For a worst-case pair with k = R(S) = 6 relays in a network with n = 251, any adversarial set of at most five failed relays leaves at least one relay alive. Under random failures, the same pair has survival probability exactly one for q ≤ 5 because fewer than six failures cannot kill all six relays. For q = 10, Theorem 6 gives 1−
245 4 251 ≈ 0.99999996. 10
The adversarial threshold is therefore conservative but essential: it gives a deterministic guarantee, while random failures are typically much less damaging. Fig. 3 compares the exact random-failure formula for a worst-case pair against empirical mean survival over sampled terminal pairs.
Figure 3: Random versus adversarial relay failures for a representative n = 1009 greedy design. The vertical line marks the deterministic adversarial threshold R(S) − 1. Randomfailure survival remains high beyond this threshold because random failures are unlikely to target exactly all relays of a worst-case pair. The y-axis is intentionally compressed to distinguish probabilities that are all above 0.98.
11
6
Relay Tables and Selection Algorithms
For each nonzero offset d, define the relay-offset table Pd = {(a, b) ∈ S 2 : b − a = d}. By Theorem 1, if d = v − u and (a, b) ∈ Pd , then the corresponding shared relay is r = u − a = v − b. Thus a single table indexed by offsets serves every terminal pair by translation. Proposition 4 (Table size). The total number of stored relay-offset entries over all nonzero offsets is X |Pd | = m(m − 1). d̸=0
Proof. Each ordered pair (a, b) ∈ S 2 with a ̸= b contributes to exactly one nonzero offset d = b − a. There are m(m − 1) such ordered pairs. Corollary 5 (Relay-table preprocessing time). All tables Pd can be constructed in O(m2 ) time by enumerating the ordered pairs (a, b) ∈ S 2 and inserting each pair with a ̸= b into the table indexed by d = b − a. Algorithm 1 Deterministic surviving-relay lookup Require: n, S, precomputed tables Pd , terminals u ̸= v, failed-node bitmap F 1: d ← (v − u) mod n 2: for all (a, b) ∈ Pd in deterministic order do 3: r ← (u − a) mod n 4: if F [r] = 0 then 5: return r 6: end if 7: end for 8: return failure Theorem 7 (Correctness of Algorithm 1). If |F | ≤ f and R(S) ≥ f + 1, then Algorithm 1 returns a valid surviving relay for every u ̸= v. Proof. For d = v −u, the table Pd contains exactly the difference representations corresponding to shared relays of (u, v) by Theorem 1. Since R(S) ≥ f + 1, |Pd | ≥ f + 1. At most f of the corresponding relays can belong to F , so at least one table entry produces a relay r∈ / F . When Algorithm 1 returns such an r, the associated (a, b) satisfies u − r = a ∈ S and v − r = b ∈ S, so r → u and r → v. Proposition 5 (Lookup cost versus graph search). For terminal offset d = v−u, Algorithm 1 inspects at most λS (d) table entries. Hence its worst-case online scan length is at most max λS (d) ≤ m, d̸=0
12
and, under a traffic model in which the terminal-pair offset d is uniformly distributed over the nonzero offsets, its average scan length is 1 X m(m − 1) . λS (d) = n − 1 d̸=0 n−1 By contrast, a standard breadth-first rerouting search in a directed degree-m circulant can inspect Θ(nm) edges in the worst case. Proof. For a fixed offset d, the algorithm scans the entries of Pd , whose cardinality is λS (d). For each a ∈ S there is at most one b = a + d in S, so λS (d) ≤ m. The average identity is Proposition 4 divided by n − 1 under the stated uniform-offset assumption. Algorithm 2 Load-aware surviving-relay selection Require: n, S, tables Pd , terminals u ̸= v, failed bitmap F , relay load vector L 1: d ← (v − u) mod n; best ← ⊥ 2: for all (a, b) ∈ Pd do 3: r ← (u − a) mod n 4: if F [r] = 0 and (best = ⊥ or L[r] < L[best]) then 5: best ← r 6: end if 7: end for 8: return best Theorem 8 (Load-aware correctness). Under the same hypothesis as Theorem 5, Algorithm 2 returns a valid surviving relay. Among surviving relays listed in Pv−u , it returns one with minimum recorded load. Proof. The existence and validity of at least one surviving relay follow as in the proof of Algorithm 1. Algorithm 2 scans all surviving relays represented by Pv−u and updates best only when a strictly smaller load is found. Therefore the returned relay has minimum load among surviving candidates. Proposition 6 (Translation-invariant relay balance). Fix a nonzero offset d and write Pd = {(a1 , b1 ), . . . , (ak , bk )}. For any fixed representation j, if each of the n ordered terminal pairs (u, u + d), u ∈ Zn , issues exactly one relay request and all requests use representation j, then every relay node is selected exactly once. More generally, suppose a policy assigns, for each representation j, exactly tj complete translation sweeps over all n ordered terminal pairs with P offset d. Then every relay node is selected exactly kj=1 tj times. Proof. For representation (aj , bj ) and terminal u, the selected relay is r = u − aj . As u ranges over Zn , the map u 7→ u − aj is a bijection of Zn . Hence one full sweep over the n terminal pairs with representation j selects each relay exactly once. Repeating this sweep tj times contributes exactly tj selections to every relay. Summing over the representations P gives exactly kj=1 tj selections at every relay node. 13
The hypothesis of Proposition 6 is intentionally scoped to uniform complete sweeps over a fixed offset. Non-uniform traffic, arbitrary streaming request order, or repeated demand for a small subset of terminal pairs can concentrate load on specific relays; in that case Algorithm 2 should be combined with measured load counters or traffic-aware ordering of Pd rather than relying on symmetry alone. Example 5 (Algorithm trace). Let n = 13, S = {1, 4, 6, 9}, u = 0, and v = 5. Then d = 5 and P5 = {(1, 6), (4, 9), (9, 1)}. The corresponding relays are 12, 9, and 4. If F = {12}, Algorithm 1 skips 12 and may return 9. Indeed, 0 − 9 ≡ 4 ∈ S, 5 − 9 ≡ 9 ∈ S, so 9 → 0 and 9 → 5.
Figure 4: Worked trace of Algorithm 1. The table P5 produces three candidate relays for u = 0; the arithmetic in the relay column substitutes u = 0 explicitly. The failed relay is crossed out and the first surviving relay is selected.
7
Vectorized Greedy Generator Construction
The experiments use several generator families. The strongest threshold designs were produced by a vectorized greedy heuristic. The heuristic is not a proof of optimality; after each set is constructed, all multiplicities are recomputed exactly by the definition of λS . Suppose the current partial generator set is S with multiplicities λ(d). If a new candidate x∈ / S ∪ {0} is added, then for every nonzero d the increment is ∆x (d) = 1S (x − d) + 1S (x + d), because the new ordered pairs are (a, x) and (x, a) for a ∈ S. The greedy rule prioritizes candidates that cover the largest number of currently minimum-multiplicity offsets; ties are broken by coverage of currently zero offsets and then deterministically by the seeded ordering. A chunked vectorized implementation evaluates many candidates at once using Boolean indicator arrays. 14
Algorithm 3 Vectorized greedy generator heuristic Require: n, target degree m, random seed 1: S ← ∅, λ(d) ← 0 for all d 2: A ← Zn \ {0} 3: while |S| < m do 4: M ← mind̸=0 λ(d) 5: DM ← {d ̸= 0 : λ(d) = M } 6: D0 ← {d ̸= 0 : λ(d) = 0} 7: for all chunks X ⊆ A do 8: evaluate cM (x) = |{d ∈ DM : ∆x (d) > 0}| for all x ∈ X 9: evaluate c0 (x) = |{d ∈ D0 : ∆x (d) > 0}| for all x ∈ X 10: end for 11: choose x maximizing (cM (x), c0 (x)) with seeded tie-breaking 12: Sold ← S 13: S ← Sold ∪ {x}; A ← A \ {x} 14: update λ(x − a) and λ(a − x) for every a ∈ Sold 15: end while 16: return S Proposition 7 (Greedy update formula). For a candidate x ∈ / S and a nonzero offset d, adding x changes the multiplicity by ∆x (d) = 1S (x − d) + 1S (x + d). Proof. The only new ordered pairs involving x are (a, x) and (x, a) for a ∈ S, plus (x, x) which contributes only to offset zero. A pair (a, x) contributes to nonzero offset d exactly when x − a = d, equivalently a = x − d ∈ S. A pair (x, a) contributes to d exactly when a − x = d, equivalently a = x + d ∈ S. If x − d ≡ 0 or x + d ≡ 0, the corresponding indicator is zero under the standing network convention 0 ∈ / S; hence no self-loop generator is silently introduced. Summing the two indicators gives the formula. The vectorized greedy does not enumerate a witness proof of optimality. It is a construction heuristic whose output is validated exactly. Fig. 5 shows a typical convergence trace.
15
Figure 5: Greedy convergence example. The curve shows the current minimum nonzero multiplicity as generators are added for n = 503. The target f + 1 = 3 is reached at the degree reported in Table 2.
8
Experimental Design
The optimized experiment evaluated 526,539 circulant generator sets and wrote checkpointed CSV files after each batch. The tested sizes were n ∈ {251, 503, 1009, 2003, 5003, 10007} and the fault levels were f = 0, 1, 2, 3, 4, 5. The tested families were interval, symmetric interval, modular stride, quadratic residues, random, and greedy max-min. Random sets were sampled with 1000 trials per tested degree. Greedy was run once per tested degree and was restricted to the threshold-relevant degree range. All reported values of R(S), λ averages, and standard deviations were recomputed exactly from the final generator sets. The optimized full run completed in 3995.020 seconds and produced 1218 recovery rows.
8.1
Empirical Thresholds
Table 2 reports the best degree found for each (n, f ). These values are empirical best-found degrees among the tested families, not exact values of Df (n).
16
Table 2: Best found degreesp for f -relay-fault tolerance. LB is the counting lower bound of Corollary 2. The ratio is m/ (f + 1)n. p n f LB best m gap m/ (f + 1)n family 251 251 251 251 251 251 503 503 503 503 503 503 1009 1009 1009 1009 1009 1009 2003 2003 2003 2003 2003 2003 5003 5003 5003 5003 5003 5003 10007 10007 10007 10007 10007 10007
0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5
17 23 28 33 36 40 23 33 40 46 51 56 33 46 56 64 72 79 46 64 78 90 101 111 72 101 123 142 159 174 101 142 174 201 225 246
20 28 33 38 41 45 31 40 48 54 59 65 45 59 72 78 86 92 66 86 101 114 124 135 114 142 166 184 201 217 163 209 246 271 301 319
3 5 5 5 5 5 8 7 8 8 8 9 12 13 16 14 14 13 20 22 23 24 23 24 42 41 43 42 42 43 62 67 72 70 76 73
17
1.262 1.250 1.203 1.199 1.157 1.160 1.382 1.261 1.236 1.204 1.176 1.183 1.417 1.313 1.309 1.228 1.211 1.182 1.475 1.359 1.303 1.274 1.239 1.231 1.612 1.420 1.355 1.301 1.271 1.252 1.629 1.477 1.420 1.355 1.346 1.302
greedy greedy greedy greedy greedy greedy greedy greedy greedy greedy greedy greedy greedy greedy greedy greedy greedy greedy greedy greedy greedy greedy greedy greedy greedy greedy greedy greedy greedy greedy greedy greedy greedy greedy greedy greedy
Table 3: Exact Df (n) values and greedy calibration for small cyclic groups. The greedy column is the first degree at which the same seeded vectorized greedy pipeline reaches R(S) ≥ f + 1; the gap is greedy m − Df (n). n
f
exact Df (n)
greedy m
gap
n
f
exact Df (n)
greedy m
gap
7 7 7 7 11 11 11 11 13 13 13 13
0 1 2 3 0 1 2 3 0 1 2 3
3 4 5 6 4 5 6 7 4 6 7 8
3 4 5 6 4 6 7 7 4 6 7 8
0 0 0 0 0 1 1 0 0 0 0 0
17 17 17 17 19 19 19 19 23 23 23 23
0 1 2 3 0 1 2 3 0 1 2 3
5 7 8 9 5 7 8 9 6 8 9 11
5 7 8 9 5 7 9 10 6 8 10 11
0 0 0 0 0 0 1 1 0 0 1 0
Table 4: Composite-size spot check using the same greedy construction. The ratios remain within the same practical range as the prime-size experiment, suggesting that the construction pipeline is not restricted to prime n. n f LB greedy m ratio 256 256 256 512 512 512 1024 1024 1024
0 2 5 0 2 5 0 2 5
17 29 40 24 40 56 33 56 79
21 34 45 31 48 65 46 70 93
1.313 1.227 1.148 1.370 1.225 1.173 1.438 1.263 1.186
The ratios are not monotone in n for fixed f , and for f = 0 they grow from 1.26 to 1.63 across the tested range. This should not be interpreted as a theorem about Df (n); it is a property of the tested heuristic and degree grid.
18
p Figure 6: Degree scaling against the natural lower-bound scale (f + 1)n. Greedy sets track the lower-bound scale more closely than interval sets, while quadratic-residue designs sometimes outperform greedy at larger degrees. The horizontal axis is shown on a logarithmic scale to keep the weak interval-family points visible. The diagonal is not a theorem of achievability; it is the counting scale.
8.2
High-Redundancy Distributions
Table 5 reports representative high-redundancy designs. Average multiplicity can be much larger than the worst-case multiplicity R(S); both are relevant. The worst case gives adversarial guarantees, while the distribution shapes explain random-failure behavior. Table 5: Representative high-redundancy designs from the full run. n m family R(S) mean λ 251 503 1009 2003 5003 10007
156 random 220 quadratic residues 312 quadratic residues 439 random 694 random 981 random
19
92 89 83 77 73 71
96.72 95.98 96.26 96.04 96.15 96.08
Figure 7: Multiplicity distributions for high-redundancy designs. The gap between the mean and R(S) shows why average redundancy and worst-case redundancy must be reported separately. Each panel uses its own horizontal scale to show distribution shape.
8.3
Recovery Simulation
For the selected best designs, random relay failures were simulated over 5000 trials per row. Table 6 aggregates the survival probabilities by number of failed relays. The minimum is the worst observed simulation row, not a theoretical lower bound. Table 6: Random relay-failure recovery over 1218 simulation rows. The minimum row for every q came from the smallest threshold design n = 251, m = 20, greedy, R = 1; thus the low q = 20 minimum is a small-degree outlier rather than a systematic failure of highredundancy designs. failures q min success mean success median 1 2 3 4 5 10 20
0.9984 0.9942 0.9946 0.9908 0.9892 0.9792 0.9496
20
0.999936 0.999848 0.999803 0.999723 0.999682 0.999338 0.998581
1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000
8.4
Greedy Runtime and Construction Cost
Table 7 gives empirical worker times for the vectorized greedy heuristic. The table also explains why greedy construction should be regarded as an offline design step rather than an online routing step. Online recovery uses only the precomputed tables of Section 6. Table 7: Empirical vectorized-greedy construction cost. Worker time is summed over greedy designs for that n and is not wall-clock time. n designs max m max R max sec/design 251 503 1009 2003 5003 10007
53 59 75 80 87 89
90 126 176 247 390 552
78 72 86 81 78 73
0.09 0.47 2.45 17.29 182.48 1042.51
Table 8: Seed sensitivity of the vectorized greedy heuristic on two threshold cases. n m target f seed R(S) std. dev. 251 251 251 251 251 1009 1009 1009 1009 1009
8.5
33 33 33 33 33 72 72 72 72 72
2 2 2 2 2 2 2 2 2 2
0 1 2 3 4 0 1 2 3 4
3 3 3 3 3 3 3 3 3 3
1.179 1.080 1.245 1.332 1.270 1.498 1.444 1.446 1.550 1.459
Comparison With Difference-Basis Benchmarks
The counting bound is an unavoidable lower bound. Existing cyclic difference-basis theory √ gives general existence upper bounds for f = 0, such as the 1.5 n-scale bound in [13]. For higher multiplicity, recent preprints study g-difference bases, but we treat those results as preprint-level context rather than as peer-reviewed cyclic construction constants. Table 9 therefore separates three quantities: the counting lower bound, an external peer-reviewed f = 0 cyclic difference-basis upper bound when applicable, and the empirical relay-design threshold found by the greedy pipeline.
21
Table 9: Benchmark comparison. BG is the f = 0 cyclic difference-basis construction upper bound from [13]. For f = 1, 2, no peer-reviewed explicit cyclic g-difference-basis generator bound is used here; the benchmark column therefore reports the counting lower bound as the concrete reference point. n
f
counting LB
251 251 251 1009 1009 1009 10007 10007 10007
0 1 2 0 1 2 0 1 2
17 23 28 33 46 56 101 142 174
9
external benchmark greedy m BG ≤ 24 LB 23 LB 28 BG ≤ 48 LB 46 LB 56 BG ≤ 151 LB 142 LB 174
ratio
interpretation
20 1.26 greedy within BG scale 28 1.25 – 33 1.20 – 45 1.42 greedy within BG scale 59 1.313 – 72 1.309 – 163 1.63 algebraic benchmark smaller 209 1.48 – 246 1.42 –
Practical Interpretation for Interconnection Networks
The shared-relay model is most appropriate when a system benefits from immediate two-hop alternatives rather than global rerouting. Examples include local rendezvous, acknowledgement aggregation, duplicated control signaling, and small-message recovery in symmetric overlays or structured on-chip fabrics. Ring interconnects in commercial processors are the degree-two circulant baseline; recent NoC work also implements and evaluates routing algorithms for circulant topologies [11, 12]. A concrete deployment is a duplicated control-notification primitive on a directed circulant overlay. When a controller or source selects a terminal pair (u, v) that must both receive a short control word, it computes d = v − u and scans Pd to choose a surviving relay r. Because the model requires r → u and r → v, the selected relay can forward the duplicated control word to both terminals. If r is failed, the failed-node bitmap causes the endpoints or controller to skip the same table entry and select the next surviving relay. By Corollary 5, the preprocessing cost is O(m2 ). The memory cost is governed by Proposition 4. At the largest threshold design in Table 2, m = 319 and hence m(m − 1) = 101,442 offset-pair entries. Proposition 5 makes this latency distinction explicit: relay lookup is O(λS (d)) ≤ O(m) in the worst case and m(m − 1)/(n − 1) on average under a uniform-offset traffic model, whereas a graph-search rerouting baseline on a degree-m circulant may inspect Θ(nm) edges. Table 10 gives a concrete software measurement of this separation for four threshold designs.
22
Table 10: Software recovery microbenchmark for greedy f = 2 threshold designs with two random failed relays and 10,000 random terminal pairs. The proposed lookup uses Algorithm 1; the graph-search baseline scans candidate relays in the circulant graph from scratch. Timings are Python wall-clock microseconds. n m lookup mean lookup 99th search mean search 99th 251 503 1009 2003
33 48 72 101
0.245 0.299 0.297 0.471
0.582 0.691 0.516 2.197
3.515 7.301 14.309 25.625
13.367 27.502 58.344 100.648
The shared-relay primitive is most useful when m is small relative to n, so that Pd is sparse and the O(m) lookup cost is substantially smaller than a graph-wide search; when m = Θ(n), most offsets are covered trivially and conventional routing may be sufficient. The limitation is that the model guarantees only the existence of a two-hop relay with outgoing links to both terminals. It does not by itself solve congestion control, global packet scheduling, or multi-hop routing after arbitrary topology damage. These are deliberately separated: the paper defines and optimizes the relay primitive, which can be embedded into larger routing protocols.
10
Discussion
Shared-relay fault tolerance is equivalent to cyclic difference multiplicity, a known combinatorial condition. The equivalence becomes practically useful only after adding a network-layer interpretation: relay tables, failure semantics, selection rules, memory costs, balance guarantees, and empirical generator design. This separation protects the paper from rediscovering difference bases while giving the equivalence operational meaning for circulant interconnection networks. The empirical results show three trends. First, simple interval-like generator sets are poor worst-case shared-relay designs because they leave many offsets uncovered. Second, vectorized greedy sets can reach R(S) = f + 1 within a moderate constant factor of the counting lower bound for all tested n and f ≤ 5. Third, random failure performance is much stronger than adversarial guarantees, with mean survival above 0.998 even at 20 random failures and above 0.999 for q ≤ 10, but the adversarial guarantee remains the correct safety definition for worst-case relay failures. Several limitations remain. First, the greedy construction is a heuristic and should not be interpreted as an exact computation of Df (n) outside the small cases exhaustively verified in Table 3. Second, we prove membership of the design decision problem in NP, but we do not claim an NP-hardness theorem or a worst-case approximation ratio for Algorithm 3. Third, for f ≥ 1, no peer-reviewed explicit cyclic g-difference-basis construction is used here to provide a concrete numerical comparison. Fourth, the current systems evidence is a software-level recovery microbenchmark, not a full packet-level congestion or hardware-cycle simulation.
23
11
Conclusion
This paper developed a fault-tolerant shared-relay communication framework for directed circulant interconnection networks. The core equivalence to cyclic difference multiplicity was stated explicitly and used as a tool rather than claimed as a new combinatorial object. On top of that equivalence, the paper defined network design parameters Df (n) and R(n, m), proved worst-case and random-failure recovery guarantees, proved a structural failure theorem for interval circulants, developed relay lookup and load-aware selection algorithms, quantified table size and preprocessing, calibrated exact Df (n) values for small groups, measured relay lookup against a graph-search baseline, gave worked examples, and evaluated more than half a million generator sets. The results support the view that shared-relay multiplicity is a useful local robustness metric for circulant networks and that generator choice strongly affects worst-case relay-fault tolerance.
A
Reproducibility Notes
The optimized experiment uses checkpointed CSV output. Layer 1 writes exact metrics and generator sets after each completed batch. Layer 2 reads only the selected compact designs for recovery simulation. The reported greedy construction is a heuristic, but every reported R(S) and multiplicity statistic is recomputed exactly from the final generator set. The artifact files include the generator sets, degree summaries, recovery summaries, selected histograms, run settings, and figure scripts. The optimized full run reported here was executed on a Windows workstation with 56 logical CPU workers available; the production script capped design workers at 24 and recovery workers at 8, using Python 3.x and NumPy for vectorized difference counting.
Acknowledgment The authors thank the Department of Computer Science, Faculty of Science, Kuwait University, for its support. The authors also thank the reviewers and colleagues whose comments helped clarify the distinction between the underlying difference-basis theory and the networklayer contribution of this work. This research received no specific grant from any funding agency in the public, commercial, or not-for-profit sectors.
References [1] J.-C. Bermond, F. Comellas, and D. F. Hsu, “Distributed loop computer networks: A survey,” Journal of Parallel and Distributed Computing, vol. 24, no. 1, pp. 2–10, 1995. [2] F. T. Boesch and R. Tindell, “Circulants and their connectivities,” Journal of Graph Theory, vol. 8, no. 4, pp. 487–499, 1984. [3] S.-C. Liaw, G. J. Chang, and C. Y. Tang, “Fault-tolerant routing in circulant networks and cycle prefix networks,” Networks, vol. 31, no. 2, pp. 127–136, 1998. 24
[4] J.-M. Xu, Topological Structure and Analysis of Interconnection Networks. Dordrecht, The Netherlands: Kluwer, 2001. [5] J. Duato, S. Yalamanchili, and L. Ni, Interconnection Networks: An Engineering Approach. San Francisco, CA, USA: Morgan Kaufmann, 2003. [6] R. M. Gray, “Toeplitz and circulant matrices: A review,” Foundations and Trends in Communications and Information Theory, vol. 2, no. 3, pp. 155–239, 2005. [7] D. Kalman and J. E. White, “Polynomial equations and circulant matrices,” The American Mathematical Monthly, vol. 108, no. 9, pp. 821–840, 2001. [8] F. K. Hwang, “A survey on multi-loop networks,” Theoretical Computer Science, vol. 299, no. 1–3, pp. 107–121, 2003. [9] E. A. Monakhova, “A survey on undirected circulant graphs,” Discrete Mathematics, Algorithms and Applications, vol. 4, no. 1, Art. no. 1250002, 2012. [10] K. Mukhopadhyaya and B. P. Sinha, “Fault-tolerant routing in distributed loop networks,” IEEE Transactions on Computers, vol. 44, no. 12, pp. 1452–1456, 1995. [11] 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. e03183, 2020. [12] 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. [13] T. Banakh and V. Gavrylkiv, “Difference bases in cyclic groups,” Algebra and Discrete Mathematics, vol. 28, no. 2, pp. 195–214, 2019. [14] E. Schmutz and M. Tait, “Cardinalities of g-difference bases,” arXiv:2501.11736, 2025. [15] S. Li and C. H. Yip, “Generalized additive bases and difference bases for Cartesian product of finite abelian groups,” arXiv:2509.24034, 2025. [16] Intel Corporation, “Ring Interconnect,” 12th Generation Intel Core Processors Datasheet, Volume 1, 2022. [17] B. Arimilli et al., “The PERCS high-performance interconnect,” in Proc. IEEE Symp. High Performance Interconnects (HOTI), 2010, pp. 75–82. [18] W. Klotz and T. Sander, “Some properties of unitary Cayley graphs,” Electronic Journal of Combinatorics, vol. 14, no. 1, 2007.
25