Minimal Deadlock-Free Routing for Degree-Six Triangular-Lattice Meshes and Tori with Two Forbidden Turns Zibo Diao∗ IIIS Tsinghua University [email protected]
Rongxi Sun∗ IIIS Tsinghua University [email protected]
arXiv:2609.09746v1 [cs.AR] 9 Sep 2026
Abstract Degree-six triangular-lattice interconnection networks offer substantial minimal-path diversity, but their additional directions complicate deadlock-free routing under wormhole flow control. We study a finite hexagon-shaped mesh and its periodic torus quotient in a common six-direction coordinate system. For the finite mesh, we construct a minimal partially adaptive routing relation that uses one virtual channel and forbids only two directed turns. For the torus, we prove that every source–destination pair has a unique closest lattice lift, but that the same two-turn physical routing relation still has a cyclic one-VC resource CDG for every n ≥ 3. We eliminate this residual periodic dependency by combining two virtual channels with Hamiltonian coordinates and group-specific datelines. Each same-group segment crosses its dateline at most once, which permits a global rank on VC-labelled channel resources. We prove minimal all-pairs connectivity for both physical routing relations and acyclicity of the complete resource CDG for the proposed one-VC mesh and two-VC torus constructions. For a single static bidirectional link failure known before a routing epoch, we further rotate the turn rule toward the failed orientation and replace a failed hop by a same-group two-hop triangle bypass. This restricted extension preserves all-pairs connectivity and the original VC counts, with at most one additional hop relative to the healthy shortest-path distance.
1
Introduction
Scalable many-core and accelerator systems increasingly rely on structured interconnection networks in place of global buses and ad hoc point-to-point wiring (Benini & Micheli, 2002; Dally & Towles, 2004). Routing in such networks must balance short paths, adaptivity under nonuniform traffic, and freedom from protocol deadlock. Under wormhole flow control, correctness depends not only on the existence of a path for each source–destination pair, but also on whether the union of all permitted paths creates cyclic resource dependencies (Dally & Seitz, 1987). Most classical routing theory is developed for orthogonal meshes and k-ary n-cubes. The turn model removes selected direction changes to break channel-dependency cycles while preserving partial adaptivity (Glass & Ni, 1994). Virtual channels provide a complementary mechanism by splitting a physical channel into independently allocated resource classes (Dally, 1992; Dally & Aoki, 1993). A degree-six triangular lattice has different elementary cycles and shortest-path sectors, and its periodic quotient additionally contains non-contractible channel cycles. These differences require routing rules and correctness arguments tailored to the topology. This paper gives a unified treatment of a finite degree-six mesh and its periodic torus. Our contributions are: • We formalize both topologies in one six-direction integer coordinate system, characterize lattice geodesics by adjacent-direction sectors, and prove that every torus source–destination pair has a unique closest lattice lift. • We construct a one-VC mesh routing relation that forbids only d0 → d5 and d2 → d3 while preserving minimal all-pairs connectivity and partial adaptivity, and prove complete-CDG acyclicity using a linear potential. ∗
These authors contributed equally to this work.
1
• For the corresponding torus physical routing relation, we show that one VC still leaves a directed Hamiltonian resource cycle for n ≥ 3. We then cut the cyclic dependency order with two VCs and Hamiltonian datelines and prove complete resource-CDG acyclicity by a global rank function. • We give a theoretical extension for one static, globally known bidirectional link failure. An orientation-specific rotation of the turn rule and a controlled two-hop triangle bypass preserve all-pairs connectivity, add at most one hop relative to a healthy shortest route, and retain the one-VC mesh and two-VC torus deadlock guarantees. • We implement the proposed topologies and routing relations in gem5/Garnet, validate the routing relations with an independent CDG checker, and evaluate routing performance, restricted-sector pressure, torus dateline VC behavior, and scaling. The main text specifies the routing relations and states the formal results. Complete proofs are deferred to the appendix, and Sections 5–6 describe the implementation and experimental results.
2
Related Work
Deadlock, virtual channels, and adaptive routing. Dally and Seitz introduced the channeldependency graph formulation for wormhole routing (Dally & Seitz, 1987). Virtual-channel flow control separates resource classes on a physical link and can be used to embed a cyclic physical topology into an acyclic resource order (Dally, 1992). Dally and Aoki developed adaptive deadlock-free schemes based on VC classes and direction reversals (Dally & Aoki, 1993), while Duato’s theory permits a cyclic adaptive subnetwork when a suitable deadlock-free escape subnetwork exists (Duato, 1993). In contrast, the guarantees in this paper use the stronger certificate that the complete resource CDG of each proposed routing relation is acyclic. Turn-restricted and fault-tolerant routing. The turn model prohibits selected direction changes to break dependency cycles while retaining multiple legal paths (Glass & Ni, 1994). Our mesh construction applies this principle to the six shortest-path sectors of a triangular lattice. The torus construction additionally addresses the periodic, non-contractible dependencies that survive the two turn restrictions used here. Fault-tolerant wormhole routing has also been studied for faulty orthogonal meshes (Glass & Ni, 1993); in particular, odd-even turn restrictions have been adapted to provide deadlock-free routing around 2D-mesh faults (Wu, 2003). Our fault result is deliberately narrower: it treats one statically known link and preserves the analytic resource ordering of the healthy triangular-lattice construction. Degree-six meshes. Hexagonal-network terminology is not uniform: it may describe a degree-three honeycomb, a ring- or hierarchy-based network, or the degree-six triangular lattice studied here. Physicaldesign work on hexagonal processor tiles established the implementation and locality benefits of a sixneighbor on-chip array (Xiao & Baas, 2012), while other studies considered hierarchical hexagon topologies and routing heuristics (Baleski et al., 2015; Cheng et al., 2020). More directly related to our mesh, Gu et al. adapted turn-model routing to a corner-addressed hexagonal network and obtained minimal partially adaptive algorithms (Gu et al., 2006). Albader et al. gave Eisenstein–Jacobi coordinates and shortest-path communication algorithms for hexagonal meshes (Albader et al., 2012). Moriam and Fettweis subsequently used a channel-dependency matrix to synthesize VC-free, fault-tolerant turn-restricted algorithms for a diagonally augmented mesh NoC (Moriam & Fettweis, 2016). These works motivate the topology and the turn-model approach, but they do not give the particular two-turn, one-VC routing relation and complete analytic CDG certificate proved here. Closest hexagonal-torus routing work. Shamaei et al. proposed the closest prior construction for a hexagonal torus family: a minimal, fully adaptive algorithm that partitions shortest paths into six message types and assigns three VC classes according to message type and whether a route uses a wraparound link (Shamaei et al., 2013). Appendix F gives the coordinate identification for the H4 instance used in our finite counterexample. Under the routing and VC-assignment rules stated in that paper, our reconstruction contains a same-type, same-VC directed resource cycle. Proposition 2.1 states the witness, and Appendix F lists every packet and an automated check. This contradicts the claimed complete-CDG acyclicity under those stated rules; by itself it does not establish that a reachable wormhole deadlock exists for the fully adaptive routing function. Unlike that three-VC proposal, our positive result intentionally gives up full adaptivity, uses two VCs, and proves that the complete resource CDG is acyclic by a global rank function. 2
2.1
Reassessing the prior three-VC scheme
Let H4 denote the n = 4 torus instance of Shamaei et al. (2013), represented in our coordinates by the representative set V4 and periods T1 = (4, 3) and T2 = (−3, 7). Write (c, q) for directed physical channel c in VC class q. Proposition 2.1 (A permitted cycle in the published three-VC CDG). Under the routing and VCassignment rules stated by Shamaei et al. (2013), the resource CDG of H4 contains the directed cycle (c0 , 1) → (c1 , 1) → · · · → (c6 , 1) → (c0 , 1),
(1)
where the projected channels follow c
c
c
c
c
c
c
0 1 2 3 (3, 0) −→ (0, −3) −→ (1, −3) −→ (2, −3) −→ (3, −3) 4 5 6 −→ (3, −2) −→ (3, −1) −→ (3, 0).
(2)
Every dependency in equation 1 is induced by a minimal wraparound Type-1 route allowed by the published fully adaptive routing function. Appendix F gives the proof and clarifies the scope of this result. In particular, Proposition 2.1 contradicts the paper’s complete-CDG acyclicity conclusion and is not excluded by its Theorem 2 argument, but we do not infer packet-level deadlock reachability from a CDG cycle alone.
3
Network Model and Preliminaries
3.1
Six-direction coordinates and the finite mesh
Nodes of the infinite triangular lattice are integer pairs v = (x, y) ∈ Z2 . Its six directed unit steps, listed counterclockwise, are d0 = (1, 0), d1 = (0, 1), d2 = (−1, 1), (3) d3 = (−1, 0), d4 = (0, −1), d5 = (1, −1). Indices are interpreted modulo six, and di+3 = −di . Define the hexagonal norm by ∥(x, y)∥H = max{|x|, |y|, |x + y|}.
(4)
Lemma 3.1 (Adjacent-direction decomposition). For every ∆ ∈ Z2 , there exist adjacent directions di , di+1 and integers a, b ≥ 0 such that ∆ = adi + bdi+1 ,
a + b = ∥∆∥H .
(5)
Lemma 3.2 (Triangular-lattice distance). For all s, t ∈ Z2 , the shortest-path distance in the infinite triangular lattice is dH (s, t) = ∥t − s∥H . (6) Lemma 3.3 (Direction set of a lattice geodesic). Every shortest path in the infinite triangular lattice uses steps from at most two adjacent directions. Equivalently, the direction word of every lattice geodesic is contained in one adjacent-direction sector. Proofs of Lemmas 3.1–3.3 are given in Appendix A. For later reference, define the six closed direction sectors Si = {adi + bdi+1 : a, b ≥ 0},
Si◦ = {adi + bdi+1 : a, b > 0}.
(7)
The strict interior Si◦ excludes the two boundary rays. The four sectors S0 , S1 , S3 , S4 are within-group sectors, while S2 and S5 are cross-group sectors for the direction groups introduced in Section 4. For continuity with the experimental labels, Section 6 refers to these two classes as internal and boundary sectors, respectively. For a size parameter n ≥ 2, let R = n − 1 and define the finite mesh Mn = (Vn , En ) by Vn = {(x, y) ∈ Z2 : ∥(x, y)∥H ≤ R}. 3
(8)
Figure 1: Coordinate system and minimal paths in a finite degree-six triangular-lattice mesh with n = 4 (R = 3). The highlighted routes are two distinct six-hop minimal paths from s = (−3, 0) to t = (1, 2). Whenever u, u + di ∈ Vn , the graph contains a directed channel in each direction between the two nodes. Its node count is n−1 X r = 3n2 − 3n + 1. (9) |Vn | = 1 + 6 r=1
Figure 1 illustrates the directed link orientations, the finite boundary, and the minimal-path diversity represented by Lemma 3.1. 3.2
The periodic torus
Define the period vectors
T1 = (n, n − 1), T2 = (−(n − 1), 2n − 1), and the period lattice Λn = {aT1 + bT2 : a, b ∈ Z}. The torus is the quotient Tn = Z2 /Λn .
(10) (11)
Coordinates p and p + λ represent the same physical node for all λ ∈ Λn . Since N = | det(T1 , T2 )| = 3n2 − 3n + 1,
(12)
the quotient contains N nodes. A directed torus channel is [u] → [u + di ], where brackets denote an equivalence class. Its distance is dTn ([s], [t]) = min ∥t − s + λ∥H . λ∈Λn
(13)
Lemma 3.4 (Complete representative set). The N nodes in Vn form a complete, nonredundant set of representatives for Z2 /Λn . Corollary 3.5 (Torus diameter). The diameter of Tn is n − 1. Corollary 3.6 (Unique closest lift). For every ordered pair [s], [t] ∈ Tn , with their canonical representatives s, t ∈ Vn , there is a unique λ⋆ (s, t) ∈ Λn such that dTn ([s], [t]) = ∥t − s + λ⋆ (s, t)∥H . 4
(14)
Figure 2: Planar lifting of a minimal route in the n = 4 torus. The solid central hexagon depicts the representative node set Vn , and the dashed copies are its translates under T1 and T2 . The continuous boundaries are visualization aids; quotient representatives are the discrete nodes in Vn . The destination t and its marked translates represent the same torus node. Routing from s = (3, 0) to the unique closest lift t∗ = t + T1 = (1, 3) gives a three-hop lattice geodesic whose projection is a minimal wraparound route from [s] to [t]. Proofs of Lemma 3.4 and Corollaries 3.5–3.6 are given in Appendix C. We retain the set notation Λ⋆ (s, t) := arg min ∥t − s + λ∥H = {λ⋆ (s, t)}
(15)
λ∈Λn
when convenient. Thus every minimal torus route has the same destination lift t + λ⋆ (s, t); its remaining freedom is only the ordering of minimal direction steps within that lift. The geometric boundary crossing in Figure 2 illustrates wraparound connectivity. It is distinct from the Hamiltonian dateline defined in Section 4.2. 3.3
Routing relations and channel dependencies
For a directed path P = (u0 , . . . , um ), let cj : uj → uj+1 denote its jth physical channel. Each channel carries a direction label dij ; the corresponding direction word is di0 di1 · · · dim−1 . We say that P contains the directed turn di → dk when di dk occurs as a consecutive subword. A path-based routing relation R assigns to every ordered source–destination pair (s, t) a set R(s, t) of permitted directed paths. It is minimal if every permitted path has shortest-path length, and all-pairs connected if R(s, t) ̸= ∅ for every ordered pair. It is partially adaptive if it is all-pairs connected and there exist s, t and a permitted route prefix for which at least two distinct next channels extend the prefix to paths in R(s, t). At each hop, an implementation may choose any output that extends the current prefix to a path in the relevant routing relation. The choice may be random or may use local congestion information. A 5
deterministic implementation may instead apply a fixed priority order; the correctness results apply to every such policy because they are proved for the union of all permitted paths. We assume standard wormhole flow control, no U-turns, and a finite set of VCs on each directed physical channel. A resource is a pair (c, q) consisting of a directed physical channel c and VC index q. A VC-labelled path has a resource word (c0 , q0 ), (c1 , q1 ), . . . , (cm−1 , qm−1 ).
(16)
The complete resource channel-dependency graph has one vertex for every resource used by a permitted path and contains the directed edge (cj , qj ) −→ (cj+1 , qj+1 ) (17) whenever the two resources occur consecutively in the resource word of some permitted path. Longer hold-and-wait dependency chains are represented by directed paths in this graph. We use the standard acyclicity certificate: a VC-labelled routing relation whose complete resource CDG is acyclic is deadlockfree (Dally & Seitz, 1987).
4
Deadlock-Free Routing
Partition the directions into the two half-plane groups U = {d0 , d1 , d2 },
L = {d3 , d4 , d5 }.
(18)
d 2 → d3 .
(19)
Both constructions prohibit the directed turns d0 → d5 ,
By Lemma 3.3, every minimal direction word is confined to one adjacent-direction sector. Within this class of minimal words, avoiding the two turns in equation 19 is equivalent to the group word belonging to the language L∗ U∗ . 4.1
Mesh routing with two forbidden turns and one VC
For s, t ∈ Vn , define RM (s, t) = {P : P is an s–t path of length dH (s, t), P contains neither prohibited turn in equation 19}.
(20)
All channels in every P ∈ RM (s, t) use the single available VC. Operationally, the router may choose a minimal output only when the resulting prefix remains extendible to a path in RM (s, t). Thus the choice may be randomized at every hop or selected using local congestion. In the cross-group sector S5 = {d5 , d0 }, all d5 hops precede all d0 hops; in S2 = {d2 , d3 }, all d3 hops precede all d2 hops. The four within-group sectors retain every interleaving of their two minimal directions. Theorem 4.1 (Mesh routing). For every n ≥ 2, RM is minimal, all-pairs connected, partially adaptive, and deadlock-free using one VC. If t − s = adi + bdi+1 ∈ Si◦ , then RM (s, t) retains all a+b direction a interleavings when Si is a within-group sector, whereas it retains only the unique L-before-U word when Si is a cross-group sector. On a sector boundary ray, the minimal direction word is unique. The complete proof, including minimal all-pairs connectivity inside the finite boundary, is given in Appendix B. 4.2
Torus routing with two forbidden turns and two VCs
For quotient nodes [s], [t] ∈ Tn , let s, t ∈ Vn denote their canonical representatives and let λ⋆ (s, t) be the unique closest lift vector from Corollary 3.6. Define the physical torus routing relation RT ([s], [t]) = {π(P ) : P is a lattice geodesic from s to t + λ⋆ (s, t), and P contains neither prohibited turn in equation 19},
(21)
where π denotes projection to the quotient. The displacement t − s + λ⋆ (s, t) admits an adjacent-direction decomposition from Lemma 3.1. If both coefficients are positive, the route uses those two directions; on a 6
sector ray only one direction has positive count. At each hop, any legal direction may be chosen provided that the resulting prefix remains extendible to a path in RT . Let N = 3n2 − 3n + 1,
k = 3n − 1,
(22)
and define quotient coordinates with residues in {0, . . . , N − 1}: HU (x, y) = x + ky
(mod N ),
HL (x, y) = −x − ky
(mod N ).
(23)
Their direction increments are U L
first direction ∆HU (d0 ) = 1 ∆HL (d3 ) = 1
second direction ∆HU (d1 ) = k ∆HL (d4 ) = k
third direction ∆HU (d2 ) = k − 1 ∆HL (d5 ) = k − 1
(24)
Lemma 4.2 (Hamiltonian coordinates). The maps HU , HL : Tn → ZN are well-defined bijections. In particular, repeated d0 channels follow the cyclic order induced by HU , and repeated d3 channels follow the cyclic order induced by HL . Proposition 4.3 (Residual one-VC cycle on the torus). For every n ≥ 3, if every hop permitted by RT is assigned the same VC, the complete resource CDG is cyclic. In particular, with cr : [rd0 ] → [(r + 1)d0 ] for r ∈ ZN , it contains (c0 , 0) → (c1 , 0) → · · · → (cN −1 , 0) → (c0 , 0). (25) Proofs of Lemma 4.2 and Proposition 4.3 are given in Appendices C and D, respectively. Proposition 4.3 does not claim that two VCs are necessary for every possible torus routing relation; it shows only that assigning one VC to every hop permitted by RT yields a cyclic complete resource CDG. For G ∈ {L, U}, let
HG =
HL , G = L, HU , G = U.
(26)
A channel cj : [uj ] → [uj+1 ] in group G is a dateline channel if HG (uj+1 ) < HG (uj ). For a lifted geodesic P = (u0 , . . . , um ) whose projection lies in RT ([s], [t]), let cj : [uj ] → [uj+1 ] denote the projected physical channel. Define its per-hop VC mapping V(P, j) ∈ {0, 1} as follows. At the beginning of every maximal same-group segment, initialize crossed= 0. For the jth channel in that segment, 0, crossed = 0 and cj is not a dateline channel, (27) V(P, j) = 1, crossed = 0 and cj is a dateline channel, 1, crossed = 1. After assigning a dateline channel, set crossed= 1. A route can change groups only from L to U; at that boundary the state is reset before assigning the first U channel. Hence the reset may induce a dependency from (L, VC1 ) to (U, VC0 ). Equation 27 lifts the physical relation RT to the VC-labelled resource relation b T ([s], [t]) = { (c0 , V(P, 0)), . . . , (cm−1 , V(P, m − 1)) : R P is a lattice geodesic with π(P ) ∈ RT ([s], [t])}.
(28)
Per-packet implementation. The routing state consists of the unique closest lift, the remaining hop counts, the current direction group, and the bit crossed: 1. At injection, compute and fix λ⋆ (s, t); choose an adjacent-direction decomposition of its displacement and initialize the remaining hop counts, ignoring any zero-count direction. 2. At each hop, form the legal minimal candidate set from directions with positive remaining counts whose choice leaves the prefix extendible to a path in RT . Equivalently, in a cross-group sector the U direction is unavailable while a lower-group hop remains. 3. Select a candidate randomly, by local congestion, or by a fixed priority, then decrement its remaining count. 7
4. Assign its VC by equation 27; update crossed, and reset it before the first channel after an L → U group transition. The closest lift is fixed at injection, and the only dynamic state used specifically by the VC phase rule is the one-bit crossed flag. Theorem 4.4 (Torus routing). For every n ≥ 2, the physical relation RT is minimal and all-pairs b T has an acyclic complete resource CDG and is therefore connected. The two-VC resource relation R ⋆ deadlock-free. If t − s + λ (s, t) = adi + bdi+1 ∈ Si◦ , then RT retains all a+b direction interleavings when a Si is a within-group sector, whereas it retains only the unique L-before-U word when Si is a cross-group sector. On a sector boundary ray, the minimal direction word is unique. Moreover, RT is partially adaptive if and only if n ≥ 3. The complete proof is given in Appendix D. b T has the form 0∗ 1∗ or 0∗ 1∗ 0∗ 1∗ . Corollary 4.5 (Per-packet VC transition bound). Every VC word in R Consequently, a packet changes VC class at most three times along its route. This bound follows from the L∗ U∗ group order and the single-dateline property of each maximal samegroup segment; a short derivation is included in Appendix D. 4.3
Restricted single-link fault extension
We consider one failed bidirectional physical link e = {A, A+dj }, where j ∈ {0, 1, 2} selects its undirected orientation. In the torus, the endpoints and channels are interpreted in the quotient. The failure is static, is globally known before a new routing epoch begins, and is the only failed component. All routers use the same fault-aware configuration; packets routed under an older configuration are not present in that epoch. Orient the two direction groups toward the failed link by defining Uj = {dj−1 , dj , dj+1 },
Lj = {dj+2 , dj+3 , dj+4 },
(29)
dj−1 → dj−2 .
(30)
and prohibit dj+1 → dj+2 , (j)
Indices remain modulo six. Let RX , for X ∈ {M, T}, denote the corresponding rotated healthy routing relation: it is defined exactly as RM or RT , respectively, with equation 30 replacing equation 19. (j)
For P ∈ RX , let Be (P ) be the set obtained by leaving P unchanged when it avoids e, and otherwise replacing its failed directed hop by every geometrically available substitution dj ⇝ dj−1 dj+1 dj+3 ⇝ dj+2 dj+4
or dj+1 dj−1 , or dj+4 dj+2 .
(31)
A mesh substitution is available only when its intermediate node lies in Vn ; both substitutions are available on the torus. Define the physical fault-aware relation by [ (j) Be (P ), X ∈ {M, T}. (32) RX,e (s, t) = (j)
P ∈RX (s,t)
Thus both bypass orders remain available whenever both are geometric paths. Once the first bypass channel is selected, the second is fixed by equation 31; this controlled substitution is part of the routing relation rather than an arbitrary nonminimal detour. 1−j For the torus, let R60 (x, y) = (−y, x + y) and Qj = R60 . The rotated group coordinates are
HU,j = HU ◦ Qj ,
HL,j = HL ◦ Qj .
(33)
Dateline channels and per-hop VC assignments are defined by Equations 26–27, with U, L and HU , HL b (j) denote the replaced by their rotated versions. The state is reset only at an Lj → Uj transition. Let R T,e resulting VC-labelled relation. 8
Proposition 4.6 (Restricted single-link fault extension). For every n ≥ 2 and every single static bidi(j) (j) rectional link failure described above, the physical relations RM,e and RT,e are all-pairs connected. Every permitted route has length at most one hop greater than the corresponding healthy shortest-path distance. (j) b (j) is acyclic The complete one-VC resource CDG of RM,e is acyclic, and the complete resource CDG of R T,e using two VCs. Hence the finite mesh and periodic torus remain deadlock-free with the same respective VC counts under this restricted fault model. The complete proof of Proposition 4.6 is given in Appendix E.
5
Implementation
We implemented both topologies and routing relations in gem5 v23.0.0.1 using Garnet standalone synthetic traffic. The HexMesh topology instantiates the vertex set Vn from equation 8, with 3n2 − 3n + 1 routers and bidirectional links in the six directions d0 , . . . , d5 . The HexTorus topology uses the same representatives Vn and adds the quotient links induced by the period vectors T1 = (n, n − 1) and T2 = (−(n − 1), 2n − 1). The mesh router implements the one-VC relation RM : it forms the minimal candidate set for the remaining displacement and removes any candidate that would introduce either prohibited turn d0 → d5 or d2 → d3 . The torus router first selects a closest destination lift from Λ⋆ (s, t), decomposes the lifted displacement into adjacent minimal directions, and applies the same L∗ U∗ turn restriction. For each torus hop, the VC allocator evaluates the Hamiltonian coordinate of the current group, assigns VC1 on and after a dateline crossing in that same-group segment, and resets the phase before the first U-group hop after an L-to-U group transition. Thus the implementation realizes the per-hop VC mapping in equation 27; using a single packet-level VC would not be equivalent to the algorithm proved in Theorem 4.4. On top of the legal minimal candidate set, we compare three selection policies. Fixed uses a deterministic direction priority. Random chooses uniformly among the legal candidates. Credit chooses the candidate whose downstream output has the largest available credit count. These policies affect performance only; deadlock freedom comes from the routing relation and the torus VC assignment. We also implemented an independent channel-dependency-graph checker that does not import gem5. It constructs the complete resource CDG for the mesh and torus relations, including the torus dateline VC rule, and checks acyclicity for the tested finite sizes. The simulator records the usual Garnet latency and throughput statistics as well as Hex-specific counters for direction hops, legal candidate counts, credit rechoices, torus VC0 and VC1 hops, dateline crossings, group resets, VC stalls, and dateline VC stalls.
6
Evaluation
6.1
Methodology
Table 1 summarizes the experiments. Unless otherwise stated, each point is averaged over seeds 1, 2, 3 and each run executes for 10,000 network-tester cycles. Uniform experiments use an all-node pair-list generator rather than gem5’s built-in uniform-random traffic, so that all routers are active sources and the same traffic machinery is used across mesh and torus. We report average packet latency, accepted packet throughput, zero-load latency at the lowest injection rate, maximum observed accepted throughput, hop count, VC1 hop fraction, dateline crossings, and VC stall counters. All formal result directories were checked for nonempty statistics, normal simulator exit, finite latency and throughput, and absence of fatal, panic, assertion, or deadlock messages. 9
Table 2: Routing performance summary for all-node uniform pair-list traffic at n = 8. Topology
Selection
ZLL
Avg. hops
Max thr.
Lat. at max thr.
Mesh Mesh Mesh Torus Torus Torus
Fixed Random Credit Fixed Random Credit
20.36 20.42 20.42 16.72 16.72 16.71
6.81 6.92 6.92 5.00 5.02 5.02
0.1836 0.1801 0.2456 0.1671 0.1532 0.1744
234.8 218.2 241.4 50.8 141.0 64.0
Table 1: Experimental protocol. Experiment
Fixed settings
Comparison
Runs
Routing performance Conventional baseline Sector pressure
HexMesh/HexTorus, n = 8
234
VC behavior
HexTorus, n = 8
Scaling
HexMesh/HexTorus, n = 4, 8, 12
fixed, random, and credit selection under all-node uniform pair-list traffic deterministic XY routing under the same all-node uniform pair-list traffic boundary-sector versus internal-sector traffic with matched distance distributions uniform versus dateline-heavy traffic; VC0/VC1 usage and dateline stalls fixed versus credit selection; zero-load latency and saturation throughput
13 × 13 Mesh_XY, 169 nodes HexMesh/HexTorus, n = 8
39 864 270 468
The sector traffic generator occasionally relaxes two Mesh boundary sources when the strict boundarysector and distance constraints leave no candidate pair for that source. This affects a negligible number of pairs and does not indicate a routing or simulator error. 6.2
Routing performance
Figure 3 compares the three candidate selection policies at n = 8. At low injection rates, HexTorus has lower packet latency than HexMesh: the zero-load latency is about 16.7 cycles for torus and about 20.4 cycles for mesh. This follows the shorter average torus distance under the quotient geometry. At high load, the credit policy substantially improves mesh throughput. Mesh fixed and mesh random peak at accepted packet throughputs of 0.1836 and 0.1801, respectively, while mesh credit reaches 0.2456, a 1.34× improvement over fixed. Torus credit provides a smaller gain, increasing the maximum accepted throughput from 0.1671 for fixed to 0.1744. Thus the remaining minimal adaptivity in the proposed relation is practically useful, especially in the finite mesh. Torus does not universally dominate throughput under this traffic even though it has lower zero-load latency; the shorter paths also concentrate contention differently under all-node uniform pair-list injection. Table 2 gives the corresponding summary values. The latency-at-maximum-throughput column is intentionally reported because the highest accepted throughput is often already in the onset of congestion; it should not be read as a low-latency operating point. Mesh random Torus random
Mesh fixed Torus fixed
Mesh credit Torus credit
Accepted packet throughput
Mean packet latency (cycles)
Mesh fixed Torus fixed
103
102
0
0.1
0.2
0.3
0.4 0.5 0.6 Injection rate
0.7
0.8
0.9
1
Mesh random Torus random
Mesh credit Torus credit
0.2
0.1
0 0
0.1
0.2
0.3
0.4 0.5 0.6 Injection rate
0.7
0.8
Figure 3: Routing performance under all-node pair-list uniform traffic at n = 8.
10
0.9
1
Table 3: Conventional 13 × 13 Mesh_XY baseline compared with the credit-selected hex topologies.
6.3
Topology
ZLL
Avg. hops
Max thr.
Thr. vs. Mesh_XY
ZLL reduction
Mesh_XY HexMesh credit HexTorus credit
24.12 20.42 16.71
8.72 6.92 5.02
0.1853 0.2456 0.1744
1.00× 1.33× 0.94×
1.00× 1.18× 1.44×
Comparison with conventional 2D mesh XY routing
To anchor the speedup claims against a conventional NoC baseline, we also evaluate gem5’s standard 13 × 13 Mesh_XY topology with deterministic XY routing. This baseline uses 169 routers, matching the n = 8 HexMesh/HexTorus experiments, and reuses the same all-node uniform pair-list traffic files. The directory count remains 256 only to preserve the power-of-two destination encoding required by the pairlist Garnet standalone traffic generator; the active sources and destinations are the same 169 node ids used by the hex experiments. The conventional mesh has higher zero-load latency than both hex topologies. Its zero-load latency is 24.12 cycles and its average hop count is 8.72, compared with 20.42 cycles and 6.92 hops for HexMesh credit, and 16.71 cycles and 5.02 hops for HexTorus credit. Thus the hex mesh reduces zero-load latency by 1.18× relative to the conventional 2D mesh, while the hex torus reduces it by 1.44×. For throughput, the strongest result is against the finite mesh: HexMesh credit reaches a maximum accepted packet throughput of 0.2456, versus 0.1853 for conventional Mesh_XY, a 1.33× improvement. HexTorus credit peaks at 0.1744 under this traffic, slightly below the conventional mesh peak, although it keeps substantially lower latency at low and moderate injection rates. This reinforces the distinction between path-length benefit and high-load throughput: the torus shortens routes, but its wraparound paths can concentrate contention under this all-node pair-list workload. This comparison is matched by node count and traffic workload, rather than by router radix, physical link count, wiring budget, or area, and should therefore be interpreted as a topology- and routing-level comparison rather than a physical-design-normalized speedup. HexMesh credit
Mesh_XY
HexTorus credit
Accepted packet throughput
Mean packet latency (cycles)
Mesh_XY
103
102
0
0.1
0.2
0.3
0.4 0.5 0.6 Injection rate
0.7
0.8
0.9
1
HexMesh credit
HexTorus credit
0.2
0.1
0 0
0.1
0.2
0.3
0.4 0.5 0.6 Injection rate
0.7
0.8
0.9
1
Figure 4: Comparison against a conventional 13 × 13 Mesh_XY baseline under the same all-node pair-list traffic.
6.4
Pressure in the restricted sectors
The proofs in Sections 4.1 and 4.2 show that the two boundary sectors affected by the forbidden turns retain only the unique group-monotone direction word, whereas the internal sectors retain all minimal interleavings. To isolate this structural cost, the sector experiment compares boundary-sector and internal-sector traffic while matching the distance distribution. Figure 5 reports the boundary/internal latency ratio for representative high-load rates. Ratios above one indicate that boundary-sector traffic has higher latency than internal-sector traffic. The ratio is often above one under high load, especially for torus fixed and credit and for mesh credit. The trend is not perfectly monotone and random selection has more variability, but the experiment supports the structural expectation that the cost of the two-turn restriction is concentrated in the sectors where path diversity is intentionally reduced. Table 4 summarizes the throughput side of the same experiment. For fixed and credit selection, internal-sector traffic reaches higher maximum throughput than boundary-sector traffic on both topologies. The random rows are less regular, which is consistent with randomized candidate choice adding run-to-run variation on top of the sector structure. 11
Table 4: Sector-pressure summary at n = 8. Boundary and internal traffic use matched distance distributions. Selection
Boundary ZLL
Internal ZLL
Boundary max thr.
Internal max thr.
Mesh Mesh Mesh Torus Torus Torus
Fixed Random Credit Fixed Random Credit
15.72 15.57 15.57 15.62 15.60 15.60
15.73 15.61 15.61 15.53 15.71 15.71
0.2282 0.2276 0.2276 0.1808 0.1800 0.1800
0.2362 0.2199 0.2568 0.2109 0.1639 0.2042
Boundary/Internal latency ratio
Topology
Mesh fixed Mesh credit Torus fixed Torus credit
2.5
2
1.5
1
0.5
0.1
0.2
0.3
0.4 Injection rate
0.5
0.6
0.7
Figure 5: Boundary-sector pressure relative to internal-sector traffic.
6.5
Torus dateline VC behavior
Figure 6 evaluates whether the Hamiltonian dateline state machine is exercised in simulation. Under all-node uniform traffic, VC1 accounts for about 0.28 of torus channel hops with credit selection. Under dateline-heavy traffic, the VC1 hop fraction rises to about 0.76–0.78. Dateline VC stalls also increase by more than an order of magnitude. These counters show that the torus experiments are not merely using two VCs as a static buffer pool; they are exercising the per-hop phase transition specified in equation 27. All runs in this set complete without deadlock. Table 5 gives both the traffic-level summary and representative per-rate VC counters for credit selection. Dateline-heavy traffic has about 3.1 more zero-load cycles than uniform traffic and a higher average hop count, reflecting the longer wraparoundoriented paths used to stress the dateline rule. At rate 0.4, dateline-heavy traffic has roughly 3.4× the VC1 hop fraction and about 34× the dateline VC stalls of uniform traffic. The VC-behavior experiment uses a restricted injection-rate range, so its maximum observed throughput is not the global saturation throughput reported in Section 6.2. Uniform
Dateline-heavy
Uniform
Dateline-heavy
1 Dateline VC stalls
VC1 hop fraction
106
0.8 0.6 0.4 0.2
105
104
103
0
5 · 10−2
0.1
0.15
0.2
0.25
0.3
0.35
0.4
5 · 10−2
0.1
0.15
0.2
0.25
Injection rate
Injection rate
Figure 6: Torus dateline VC behavior with credit selection.
12
0.3
0.35
0.4
Table 5: Torus VC behavior at n = 8. The first block summarizes traffic-level performance; the second block reports credit-selection VC counters at selected rates.
6.6
Traffic
Selection
ZLL
Avg. hops
Max obs. thr.
Lat. at max thr.
Uniform Uniform Uniform Dateline-heavy Dateline-heavy Dateline-heavy
Fixed Random Credit Fixed Random Credit
16.72 16.72 16.71 19.81 19.80 19.78
5.00 5.02 5.02 6.55 6.53 6.54
0.1381 0.1414 0.1445 0.1464 0.1409 0.1534
54.6 67.1 56.2 525.9 641.0 455.2
Traffic
Rate
Latency
Throughput
VC1 frac.
DL VC stalls
Uniform Uniform Uniform Dateline-heavy Dateline-heavy Dateline-heavy
0.04 0.20 0.40 0.04 0.20 0.40
16.97 19.63 56.18 20.38 145.23 455.20
0.0200 0.0996 0.1445 0.0200 0.0952 0.1534
0.278 0.279 0.288 0.762 0.768 0.777
792 30,432 42,531 4,309 539,903 1,437,240
Scaling
Figure 7 reports scaling from n = 4 to n = 12 with 13 injection rates and three seeds per point. Zero-load latency increases with n, as expected from the growing average minimal distance. Mesh latency grows from about 13.0 cycles at n = 4 to 20.4 cycles at n = 8 and 27.6–27.7 cycles at n = 12. Torus latency grows from about 11.25 cycles to 16.7 cycles and then to about 22.1 cycles. Thus the torus keeps a lower zero-load latency at every evaluated size. Maximum accepted throughput decreases as the topology grows. Mesh fixed peaks at 0.3836, 0.1836, and 0.1417 for n = 4, 8, 12, while mesh credit peaks at 0.4025, 0.2456, and 0.1477. Torus fixed peaks at 0.4002, 0.1671, and 0.1019, and torus credit peaks at 0.4012, 0.1744, and 0.1040. The results support the expected geometry-driven latency trend and show that credit selection helps mesh throughput more than torus throughput under this traffic. Table 6 gives the same trend in tabular form. Each row contains 39 samples: 13 injection rates and three seeds. The n = 12 results therefore use the same statistical structure as the smaller sizes rather than a one-off smoke test. Mesh credit
Torus fixed
Torus credit
Mesh fixed
Max accepted throughput
Zero-load latency (cycles)
Mesh fixed
25
20
15
10 4
8 n
Mesh credit
Torus fixed
Torus credit
0.4
0.3
0.2
0.1
12
4
8 n
Figure 7: Scaling result for n = 4, 8, 12. Table 6: Scaling summary. Each row aggregates 13 injection rates and three seeds. Topology
Selection
n
ZLL
Avg. hops
Max thr.
Mesh Mesh Mesh Mesh Mesh Mesh Torus Torus Torus Torus Torus Torus
Fixed Fixed Fixed Credit Credit Credit Fixed Fixed Fixed Credit Credit Credit
4 8 12 4 8 12 4 8 12 4 8 12
13.02 20.36 27.70 12.98 20.42 27.63 11.26 16.72 22.07 11.25 16.71 22.07
3.22 6.81 10.52 3.21 6.92 10.44 2.36 5.00 7.66 2.32 5.02 7.67
0.3836 0.1836 0.1417 0.4025 0.2456 0.1477 0.4002 0.1671 0.1019 0.4012 0.1744 0.1040
13
12
7
Discussion and Limitations
The two algorithms share the same geometric turn restriction but use different global ordering mechanisms. In the finite mesh, the linear potential Φ(x, y) = x + 2y is well-defined and strictly monotone within each direction group. This potential does not descend to a well-defined strict order on the periodic quotient: the torus contains directed non-contractible channel cycles, and no single-valued function on quotient nodes can increase strictly around a directed cycle. Proposition 4.3 makes this obstruction explicit for the one-VC version of our torus physical relation. The Hamiltonian coordinates instead provide cyclic orders, and the two VC phases cut those orders into an acyclic resource ranking. The main minimal-routing guarantees rely on wormhole routing with reliable bidirectional links, no Uturns, and the specific period lattice in equation 10. Proposition 4.6 establishes a separate exception for one static, globally known bidirectional link failure: only the prescribed same-group triangle substitutions are added, and the resulting routes are bounded relative to the healthy shortest-path distance rather than claimed to remain minimal. This result does not cover multiple link failures, node failures, arbitrary nonminimal detours, multicast dependencies, or dynamic topology changes. In particular, it does not establish acyclicity for the union of old and new routing configurations during an in-flight reconfiguration; such settings require a quiescent transition, a new CDG proof, or a separate deadlock-free escape subnetwork such as those studied in more general adaptive-routing theory (Duato, 1993). The torus router must also support per-hop VC allocation and the reset VC1 → VC0 when the direction group increases; an implementation that fixes one VC for an entire packet does not realize the proposed algorithm. The evaluation is intentionally focused on the routing relation and its VC mechanism rather than on full-system application behavior. We use Garnet synthetic traffic and do not report application traces, power, area, timing closure, or router critical-path measurements. The evaluation covers all-node uniform routing performance, a conventional 2D-mesh baseline, boundary-sector pressure, dateline-heavy torus traffic, and scaling to n = 12, but it does not cover hotspot traffic or application-driven burstiness. The torus results should also be interpreted carefully: lower zero-load latency follows from shorter average paths, but high-load throughput depends on how traffic maps onto the quotient links and can be lower than the finite mesh under the tested all-node pair-list workload. The single-link fault extension in Proposition 4.6 is a theoretical result; this paper does not add fault-injection performance experiments. A further theoretical question is whether a different construction can preserve comparable minimal adaptivity with fewer turn restrictions or fewer VC resources. Proposition 4.3 shows that the single-VC resource labelling of our particular torus physical relation RT has a cyclic complete CDG for n ≥ 3, while Theorem 4.4 establishes that two VCs are sufficient for the Hamiltonian-dateline construction. We do not claim that two VCs are necessary for every minimal routing relation or under alternative flowcontrol mechanisms. The simulator results confirm that the proposed two-VC rule is implementable and exercised by dateline-heavy traffic, but they do not prove such a general necessity result.
8
Conclusion
We presented a unified coordinate model and two deadlock-free minimal routing constructions for degreesix triangular-lattice networks. The finite mesh uses one VC and two directed turn prohibitions; its complete resource CDG is ordered by a linear potential. For the periodic torus, every source–destination pair has a unique closest lift, yet assigning a single VC to the same two-turn physical relation yields a cyclic resource CDG for every n ≥ 3. Two VC phases and Hamiltonian datelines cut this residual periodic cycle into a strict global resource rank. Both physical routing relations preserve minimal all-pairs connectivity. The mesh relation is partially adaptive for every n ≥ 2, while the torus relation is partially adaptive exactly when n ≥ 3. We implemented the routing relations in gem5/Garnet, verified them with an independent CDG checker, and evaluated routing performance, restricted sector pressure, dateline VC behavior, and scaling. The measurements support the main design expectations: the torus has lower zero-load latency, congestion-aware selection can exploit the retained mesh adaptivity under load, boundary-sector traffic exposes the cost of the two forbidden turns, and dateline-heavy traffic exercises the torus VC state machine. The same geometric framework also admits the restricted static single-link extension of Proposition 4.6: a rotated turn configuration and local triangle bypass preserve connectivity and deadlock freedom with at most one additional hop. General multiple-fault and dynamic-fault routing remain open. 14
AI use statement Generative AI tools were used to assist with language editing, LaTeX organization, literature discovery, preliminary consistency checks, and experiment-script development. The authors are responsible for verifying every citation, mathematical statement, proof, implementation, and experimental result in this manuscript. No experimental measurements or empirical claims in this draft were generated or fabricated by an AI system. Ethics statement This work studies network routing algorithms and does not involve human participants, personal data, or deployment of a decision-making system. We are not aware of direct ethical risks beyond the general need to report proofs, implementation details, and experimental results accurately. Reproducibility statement All topology definitions, routing rules, VC transitions, and theorem assumptions are stated in Sections 3– 4. Complete proofs are included in the appendix. The implementation includes an independent CDG checker, traffic-pair generators, experiment runners, result checkers, and summary scripts for the simulation configuration described in Section 6.
References Bader Albader, Bella Bose, and Mary Flahive. Efficient communication algorithms in hexagonal mesh interconnection networks. IEEE Transactions on Parallel and Distributed Systems, 23(1):69–77, 2012. doi: 10.1109/TPDS.2011.112. Ljupcho Baleski, Dragi Kimovski, and Ninoslav Marina. Hexagon interconnection network topology. In 2015 7th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), pp. 259–264, 2015. doi: 10.1109/ICUMT.2015.7382439. Luca Benini and Giovanni De Micheli. Networks on chips: A new SoC paradigm. Computer, 35(1):70–78, 2002. doi: 10.1109/2.976921. Yuh-Jiuh Cheng, Bor-Tauo Chen, and Wen-Lin Cheng. Design and performance evaluation of hexagonal topology networks with novel routing algorithms. In 2020 21st Asia-Pacific Network Operations and Management Symposium, pp. 310–313, 2020. William J. Dally. Virtual-channel flow control. IEEE Transactions on Parallel and Distributed Systems, 3(2):194–205, 1992. doi: 10.1109/71.127260. William J. Dally and Hiromichi Aoki. Deadlock-free adaptive routing in multicomputer networks using virtual channels. IEEE Transactions on Parallel and Distributed Systems, 4(4):466–475, 1993. doi: 10.1109/71.219761. William J. Dally and Charles L. Seitz. Deadlock-free message routing in multiprocessor interconnection networks. IEEE Transactions on Computers, C-36(5):547–553, 1987. doi: 10.1109/TC.1987.1676939. William J. Dally and Brian Towles. Principles and Practices of Interconnection Networks. Morgan Kaufmann, 2004. ISBN 978-0-12-200751-4. José Duato. A new theory of deadlock-free adaptive routing in wormhole networks. IEEE Transactions on Parallel and Distributed Systems, 4(12):1320–1331, 1993. doi: 10.1109/71.250114. Christopher J. Glass and Lionel M. Ni. Fault-tolerant wormhole routing in meshes. In FTCS-23: The Twenty-Third International Symposium on Fault-Tolerant Computing, pp. 240–249, 1993. doi: 10.1109/ FTCS.1993.627327. Christopher J. Glass and Lionel M. Ni. The turn model for adaptive routing. Journal of the ACM, 41 (5):874–902, 1994. doi: 10.1145/185675.185682. 15
Huaxi Gu, Jie Zhang, Zengji Liu, and Xiaoxing Tu. Routing in hexagonal networks under a corner-based addressing scheme. IEICE Transactions on Information and Systems, E89-D(5):1755–1758, 2006. doi: 10.1093/ietisy/e89-d.5.1755. Sadia Moriam and Gerhard P. Fettweis. Fault tolerant deadlock-free adaptive routing algorithms for hexagonal networks-on-chip. In 2016 Euromicro Conference on Digital System Design (DSD), pp. 131–137, 2016. doi: 10.1109/DSD.2016.71. Arash Shamaei, Bella Bose, and Mary Flahive. Adaptive routing in hexagonal torus interconnection networks. In 2013 IEEE High Performance Extreme Computing Conference (HPEC), pp. 1–6, 2013. Jie Wu. A fault-tolerant and deadlock-free routing protocol in 2D meshes based on odd-even turn model. IEEE Transactions on Computers, 52(9):1154–1169, 2003. doi: 10.1109/TC.2003.1228511. Zhibin Xiao and Bevan M. Baas. A hexagonal shaped processor and interconnect topology for tightlytiled many-core architecture. In Proceedings of the 20th IEEE/IFIP International Conference on VLSI and System-on-Chip, pp. 153–158, 2012.
16
A
Basic Triangular-Lattice Facts
Proof of Lemma 3.1. The six closed cones generated by adjacent directions cover Z2 ; neighboring cones meet only along their boundary rays, and their interiors are pairwise disjoint. In each cone, the required coefficients are sector conditions (a, b) a+b (d0 , d1 ) x ≥ 0, y ≥ 0 (x, y) x+y (d1 , d2 ) x ≤ 0, x + y ≥ 0 (x + y, −x) y (d2 , d3 ) y ≥ 0, x + y ≤ 0 (y, −x − y) −x (34) (d3 , d4 ) x ≤ 0, y ≤ 0 (−x, −y) −x − y −y (d4 , d5 ) x ≥ 0, x + y ≤ 0 (−x − y, x) (d5 , d0 ) y ≤ 0, x + y ≥ 0 (−y, x + y) x where the ordered pair (a, b) multiplies the two directions in the first column. The conditions in every row make both coefficients nonnegative. Direct substitution gives (x, y) = adi + bdi+1 , and the final column equals max{|x|, |y|, |x + y|} under the corresponding sector conditions. Boundary points may belong to two adjacent cones, but either representation satisfies the claim. Proof of Lemma 3.2. Every direction in equation 3 has hexagonal norm one. The triangle inequality therefore implies that every lattice path from s to t has length at least ∥t − s∥H . By Lemma 3.1, the displacement t − s has a representation by a + b = ∥t − s∥H unit steps. This representation gives a path attaining the lower bound, so the distance equals ∥t − s∥H . Proof of Lemma 3.3. Suppose a path contains two nonadjacent directions. Up to rotation and reversal of the cyclic direction order, the two directions have circular separation two or three. For every i (indices modulo six), di + di+2 = di+1 , di + di+3 = 0. (35) Thus two steps whose directions have separation two can be replaced by one unit step with the same net displacement, while two opposite steps can be deleted. Separation four is the rotated form of separation two. Since a path endpoint depends only on the sum of its step vectors, either replacement produces a strictly shorter lattice walk with the same endpoints. A geodesic therefore cannot contain a nonadjacent pair of directions. Any pairwise-adjacent subset of the six-cycle of directions has size at most two, which proves the claim.
B Proof of the Mesh Routing Theorem Proof of Theorem 4.1. Minimal all-pairs connectivity. Let s, t ∈ Vn and ∆ = t − s. By Lemma 3.1, write ∆ = adi + bdi+1 , a, b ≥ 0, a + b = ∥∆∥H . (36) If the sector is neither {d5 , d0 } nor {d2 , d3 }, every interleaving of the a + b steps avoids both turns in equation 19. In sector {d5 , d0 }, the word da5 db0 avoids d0 → d5 . In sector {d2 , d3 }, the word db3 da2 avoids d2 → d3 . Every such word has lattice length ∥∆∥H by Lemma 3.2. Since every mesh path is also a lattice path, no path inside the mesh can be shorter. It remains to verify that the constructed path stays in the finite mesh. The vertex set is the intersection of the three strips −R ≤ x ≤ R, −R ≤ y ≤ R, −R ≤ x + y ≤ R. (37) Along a path formed from two adjacent directions, each of x, y, and x + y is monotone or constant. Hence every intermediate value lies between its values at s and t, both of which satisfy equation 37. Every intermediate node therefore belongs to Vn . Thus RM (s, t) ̸= ∅ for every ordered pair, and every path in RM is minimal by definition. Retained adaptivity. Suppose first that ∆ = adi + bdi+1 ∈ Si◦ , so a, b > 0. In a within-group sector, every ordering of a copies of one direction and b copies of the other is permitted, giving a+b direction a words. In a cross-group sector, a word that places an upper-group step before a later lower-group step must contain the corresponding adjacent transition d0 → d5 or d2 → d3 somewhere in the word. Hence only the L-before-U word is permitted. If a = 0 or b = 0, the displacement lies on a sector boundary ray 17
and its minimal direction word is unique. For n ≥ 2, the displacement from (−1, 0) to (0, 1) has the two permitted shortest direction words d0 d1 and d1 d0 . Both first channels are legal at their common source, so RM is partially adaptive according to the definition in Section 3. Deadlock freedom. Consider any path in RM . Because its length is dH (s, t), it is also a geodesic of the infinite triangular lattice. Lemma 3.3 therefore confines its direction word to one adjacent-direction sector. A within-group sector lies wholly in group L or wholly in group U. In the two cross-group sectors, the prohibited turns force the lower-group directions to precede the upper-group directions. Consequently every permitted path has group sequence L∗ U∗ , and every edge of the complete one-VC CDG is either within one group or directed from L to U. A CDG cycle containing both groups would require an edge from U back to L, which does not exist. It remains to exclude a cycle contained in a single group. Define Φ(x, y) = x+2y. Its direction increments are ∆Φ(d0 ) = 1, ∆Φ(d1 ) = 2, ∆Φ(d2 ) = 1, (38) ∆Φ(d3 ) = −1, ∆Φ(d4 ) = −2, ∆Φ(d5 ) = −1. For a dependency c → c′ within group U, the tail of c′ is the head of c, so its potential is strictly larger than the tail potential of c. Along a dependency chain wholly in U, these tail potentials therefore strictly increase. They strictly decrease along every chain wholly in L. Neither chain can close. Hence the complete one-VC resource CDG of RM is acyclic, and RM is deadlock-free.
C
Geometry of the Periodic Torus
Let R60 (x, y) = (−y, x + y). This map cyclically permutes the directions, preserves the hexagonal norm, and satisfies R60 (T1 ) = T2 and R60 (T2 ) = T2 − T1 . Consequently, Λn is invariant under rotations by 60◦ . Lemma C.1 (Minimum period length). Every nonzero λ ∈ Λn satisfies ∥λ∥H ≥ 2n − 1. Proof. Rotate λ into the sector x ≥ 0, y ≥ 0, where ∥(x, y)∥H = x + y =: s. The rotation leaves Λn invariant. Direct calculation from equation 10 shows that x + ky is an integer multiple of N for every (x, y) ∈ Λn . For a nonzero vector in this sector, x + ky > 0. Suppose for contradiction that s ≤ 2n − 2. Since 0 ≤ y ≤ s, 0 < x + ky = s + (3n − 2)y ≤ (3n − 1)s ≤ (3n − 1)(2n − 2) < 2N.
(39)
Hence x + ky = N and
(40) s = N − (3n − 2)y. If y ≤ n − 2, then s ≥ N − (3n − 2)(n − 2) = 5n − 3 > 2n − 2. If y = n − 1, then s = 2n − 1. If y ≥ n, then s ≤ N − n(3n − 2) = 1 − n < 0. Every case contradicts 0 ≤ y ≤ s ≤ 2n − 2. Therefore s ≥ 2n − 1. Proof of Lemma 3.4. If two distinct points of Vn represented the same quotient node, their difference would be a nonzero period vector. By the triangle inequality, that difference would have norm at most 2(n − 1), contrary to Lemma C.1. Thus the points in Vn represent distinct quotient nodes. By equation 9, |Vn | = 3n2 − 3n + 1 = N , while equation 12 shows that the quotient also has N nodes. Hence Vn is a complete, nonredundant representative set. Proof of Corollary 3.5. Lemma 3.4 implies that every quotient displacement has a representative in Vn , whose norm is at most n − 1. Therefore diam(Tn ) ≤ n − 1. For the reverse inequality, let v = (n − 1, 0), whose norm is n − 1. For every nonzero λ ∈ Λn , the reverse triangle inequality and Lemma C.1 give ∥v + λ∥H ≥ ∥λ∥H − ∥v∥H ≥ (2n − 1) − (n − 1) = n.
(41)
Thus v itself is the unique closest representative of its quotient class, and its distance from [0] is n − 1. Hence diam(Tn ) ≥ n − 1, proving equality. Proof of Corollary 3.6. Existence follows because the period lattice is discrete and the hexagonal norm is proper on Z2 , so the minimum in equation 13 is attained. Suppose two distinct λ1 , λ2 ∈ Λn both attain it. Let ∆j = t − s + λj , j ∈ {1, 2}. 18
By Corollary 3.5, ∥∆1 ∥H = ∥∆2 ∥H = dTn ([s], [t]) ≤ n − 1. Hence ∥λ1 − λ2 ∥H = ∥∆1 − ∆2 ∥H ≤ ∥∆1 ∥H + ∥∆2 ∥H ≤ 2n − 2.
(42)
But λ1 − λ2 is a nonzero period vector, contradicting Lemma C.1, which gives norm at least 2n − 1. Therefore the closest lift is unique. Proof of Lemma 4.2. Direct calculation gives HU (T1 ) = n + k(n − 1) = N,
HU (T2 ) = −(n − 1) + k(2n − 1) = 2N.
(43)
Thus HU is invariant modulo N under every period translate and is well-defined on Tn . For every residue r ∈ ZN , the quotient node [rd0 ] satisfies HU ([rd0 ]) = r because HU (d0 ) = 1. Hence HU is surjective. The domain Tn and codomain ZN both contain N elements, so HU is a bijection. Since HL = −HU (mod N ), HL is also a bijection. Finally, d0 increments HU by one and d3 increments HL by one; repeated channels in either direction therefore visit all quotient nodes in the corresponding cyclic Hamiltonian order.
D
Proof of the Torus Routing Theorem
Proof of Proposition 4.3. For r ∈ ZN , let cr : [rd0 ] −→ [(r + 1)d0 ]. By Lemma 4.2, the nodes [rd0 ] for r ∈ ZN are all distinct and occur in the cyclic order of HU , so c0 , . . . , cN −1 form a directed physical Hamiltonian cycle. For each r, consider the ordered quotient pair ([rd0 ], [(r + 2)d0 ]). Let sr , tr ∈ Vn be its canonical representatives. Since the quotient displacement is represented by 2d0 , there is a period vector λr such that tr − sr + λr = 2d0 . For every nonzero µ ∈ Λn , Lemma C.1 and the reverse triangle inequality give, for n ≥ 3, ∥2d0 + µ∥H ≥ ∥µ∥H − ∥2d0 ∥H ≥ (2n − 1) − 2 ≥ 3. (44) Thus 2d0 is the unique closest lifted displacement for this ordered pair. The two-hop direction word d0 d0 is therefore a retained route in RT . It contains cr immediately followed by cr+1 , so under a one-VC assignment it contributes (cr , 0) → (cr+1 , 0). Taking all r ∈ ZN yields the directed cycle equation 25. Proof of Theorem 4.4. Minimal all-pairs connectivity. For an ordered pair ([s], [t]), let s, t ∈ Vn be their canonical representatives and let λ⋆ = λ⋆ (s, t). By Corollary 3.6, this is the unique closest lift vector. Lemma 3.1 gives t − s + λ⋆ = adi + bdi+1 ,
a, b ≥ 0,
a + b = dTn ([s], [t]).
(45)
In the cross-group sector S5 = {d5 , d0 }, the ordering da5 db0 avoids both prohibited turns. In the cross-group sector S2 = {d2 , d3 }, the ordering db3 da2 does so. Every interleaving is permitted in the four within-group
sectors. Projection preserves both endpoint and number of hops, so at least one permitted shortest route exists for every ordered quotient pair. Thus RT is minimal and all-pairs connected. More generally, every retained lifted geodesic uses at most two adjacent directions by Lemma 3.3. If a, b > 0, all a+b interleavings are retained in a within-group sector, whereas a cross-group sector admits a only the unique L-before-U word. If a = 0 or b = 0, the displacement lies on a sector boundary ray and the minimal direction word is unique. Partial adaptivity. For n ≥ 3, take s = (0, 0) and t = d0 + d1 = (1, 1) ∈ Vn . The displacement has norm two. For every nonzero λ ∈ Λn , Lemma C.1 and the reverse triangle inequality give ∥t + λ∥H ≥ ∥λ∥H − ∥t∥H ≥ (2n − 1) − 2 ≥ 3.
(46)
Thus t is the unique closest lift. Both shortest direction words d0 d1 and d1 d0 belong to RT and offer distinct first channels, proving partial adaptivity for every n ≥ 3. For n = 2, Corollary 3.5 gives diameter one, so every nontrivial minimal route has exactly one hop. Moreover, two distinct outgoing directions cannot reach the same quotient neighbor: otherwise di − dj for i ̸= j would be a nonzero period vector of hexagonal norm at most two, contradicting Lemma C.1, 19
which gives the lower bound three. Hence each destination has a unique minimal next channel, so RT is not partially adaptive for n = 2. Therefore RT is partially adaptive if and only if n ≥ 3. Single-dateline property. Lemma 4.2 makes HG well-defined on quotient nodes. Consider a maximal same-group segment with channels c0 , . . . , cm−1 . By equation 24, every hop has a positive integer increment sj ∈ {1, k − 1, k} in the corresponding unwrapped Hamiltonian coordinate. Because the entire minimal route has at most n − 1 hops by Corollary 3.5, 0<
m−1 X
sj ≤ mk ≤ (n − 1)k = (n − 1)(3n − 1) = N − n < N.
(47)
j=0
Reducing the strictly increasing unwrapped coordinate modulo N can therefore pass from N − 1 to 0 at most once. Hence every maximal same-group segment contains at most one dateline channel, and the state crossed in equation 27 changes from zero to one at most once within that segment. The same geodesic characterization determines the group order. Every retained path is confined to one adjacent-direction sector. A within-group sector lies wholly in one group, and either cross-group sector is forced by equation 19 to traverse its L directions before its U directions. Thus every resource-CDG edge is either intra-group or directed from L to U. b T . Let Acyclicity of the complete resource CDG. Define a rank only on resources that occur in R c : [u] → [v] be a used channel in group G ∈ {L, U}, let h = HG (u) ∈ {0, . . . , N − 1}, and set ℓ(L) = 0 and ℓ(U) = 1. Define q = 0, h, (48) r(c, q) = 2N ℓ(G) + h, q = 1 and c is a dateline channel for G, N + h, q = 1 and c is not a dateline channel for G. This is a function of the resource (c, q) alone. A dateline channel always receives VC1 under equation 27; a non-dateline channel can receive VC1 only after the unique dateline crossing of that same-group segment. We verify that every CDG edge strictly increases equation 48. By the definition in equation 17, it is enough to consider consecutive resources. Within a fixed group, let s ∈ {1, k − 1, k} be the positive unwrapped increment from the tail coordinate of the first channel to the tail coordinate of the next channel. 1. Before the dateline, both resources use VC0 and no modular wrap occurs, so the next tail coordinate is h + s > h and the rank increases. 2. If the second resource is the dateline channel, its tail is still the next pre-wrap coordinate h+s > h. The VC changes from VC0 to VC1 , but both rank cases use that pre-wrap tail coordinate, so the rank increases. 3. If the first resource is the dateline channel and a subsequent channel exists, write the dateline tail coordinate as h and its positive increment as s. Its head, and hence the next channel tail, has modular coordinate h + s − N . The next resource is a non-dateline VC1 resource with rank contribution N + (h + s − N ) = h + s > h. 4. After the dateline, no second modular wrap is possible by equation 47. Consecutive non-dateline VC1 resources both carry the offset N , while their modular tail coordinates increase by s > 0; hence the rank again increases. Finally, every used resource in group L has rank at most 2N − 1, whereas every used resource in group U has rank at least 2N . Therefore every cross-group dependency—including a reset from VC1 in L to either VC on the first U channel—strictly increases the rank. b T strictly increases the integer-valued rank equation 48. A Every edge of the complete resource CDG of R directed cycle would require the rank to return to its starting value after a sequence of strict increases, a b T is deadlock-free using two VCs. contradiction. Hence the complete resource CDG is acyclic, and R 20
Proof of Corollary 4.5. Every route has group word in L∗ U∗ , so it contains at most two maximal samegroup segments. By the single-dateline property, the VC word within each such segment has the form 0∗ 1∗ . Concatenating the one or two segment words gives 0∗ 1∗ or 0∗ 1∗ 0∗ 1∗ , which contains at most three VC-class transitions.
E Proof of the Restricted Single-Link Fault Extension We first record the rotational covariance used throughout the proof. Recall the map R60 (x, y) = (−y, x+y) from Appendix C, and define 1−j Qj = R60 . (49) Lemma E.1 (Rotation covariance). The map R60 preserves Vn and induces an automorphism of Tn . Moreover, Qj maps Uj to U, maps Lj to L, and maps the two turns in equation 30 to the two turns (j) (j) in equation 19. Consequently, the rotated healthy relations RM and RT are minimal and all-pairs connected. Proof. Direct calculation gives R60 (di ) = di+1 for every i and ∥R60 (x, y)∥H = max{|y|, |x + y|, |x|} = ∥(x, y)∥H .
(50)
Hence R60 preserves the vertex set Vn . For the torus, R60 (T2 ) = T2 − T1 ,
R60 (T1 ) = T2 ,
(51)
so R60 (Λn ) = Λn and the map descends to a quotient automorphism. Because Qj (dj+r ) = d1+r , it sends the three directions dj−1 , dj , dj+1 to d0 , d1 , d2 and sends the opposite three directions to d3 , d4 , d5 . It also sends dj+1 → dj+2 to d2 → d3 and sends dj−1 → dj−2 to d0 → d5 . Thus each rotated healthy relation is the image of its original relation under a graph automorphism. The minimal all-pairs connectivity conclusions follow from Theorems 4.1 and 4.4. Lemma E.2 (Existence of a local triangle bypass). Let e = {A, A + dj } be a physical link of Mn or Tn , with n ≥ 2. On the torus, both two-hop substitutions for either direction of e in equation 31 exist. In the finite mesh, at least one of the two substitutions exists for either direction. Proof. The torus contains the quotient channel induced by every lattice step, so both intermediate quotient nodes and all four corresponding flank channels exist. For the mesh, Lemma E.1 reduces the claim to j = 1. Write A = (x, y),
(52)
B = A + d1 = (x, y + 1),
and let R = n − 1 ≥ 1. The two candidate intermediate nodes are C0 = A + d0 = (x + 1, y),
C2 = A + d2 = (x − 1, y + 1).
(53)
For C0 , the inequalities |y| ≤ R and |x + y + 1| ≤ R follow from A, B ∈ Vn . Its only remaining condition is |x + 1| ≤ R, which can fail only when x = R. For C2 , the inequalities |y + 1| ≤ R and |x + y| ≤ R again follow from A, B ∈ Vn . Its only remaining condition is |x − 1| ≤ R, which can fail only when x = −R. Since R ≥ 1, the two failures cannot occur simultaneously. Therefore at least one of C0 , C2 lies in Vn . The forward paths through these nodes have direction words d0 d2 and d2 d0 because d0 + d2 = d1 . Reversing them gives d5 d3 and d3 d5 , and d3 + d5 = d4 . Thus the same available intermediate node also supplies the reverse bypass. Rotating back proves the claim for every j ∈ {0, 1, 2}. (j)
Lemma E.3 (Properties of the fault transformation). For every P ∈ RX (s, t), X ∈ {M, T}, the set Be (P ) is nonempty. Every route Pe ∈ Be (P ) avoids the failed link, satisfies |Pe | ≤ |P | + 1, and has group word in L∗j U∗j . 21
(54)
Proof. By Lemma E.1, P is a shortest path in the healthy graph and is therefore simple. In particular, it traverses the physical link e at most once. If it avoids e, then Be (P ) = {P } and all claims follow immediately. Otherwise, Lemma E.2 provides at least one available substitution. The vector identities dj−1 + dj+1 = dj ,
dj+2 + dj+4 = dj+3
(55)
show that every substitution has the same endpoints as the failed hop. Its two directions differ from the failed direction and its reverse, so the resulting route avoids e. Exactly one hop is replaced by two, which gives equality in equation 54 for an affected route. No U-turn is introduced: a healthy geodesic containing dj uses only dj and at most one adjacent direction, while neither bypass flank is opposite to a direction in either adjacent sector. The reverse case is symmetric. The substituted route is also a path rather than a route with a repeated vertex. If a repetition were introduced, the repeated portion would be a closed subwalk. It cannot have length one because the graphs have no self-loops, and it cannot have length two because the transformed direction word has no U-turn. Removing a closed portion of length at least three from a route of length |P | + 1 would produce a healthy s–t walk shorter than |P |, contradicting the minimality of P . The rotated turn restrictions give P a group word in L∗j U∗j . A dj hop belongs to Uj and is replaced by two Uj hops, while a dj+3 hop belongs to Lj and is replaced by two Lj hops. The substitution therefore preserves the group word language. Proof of Proposition 4.6. Connectivity and path length. Fix an ordered source–destination pair. By Lemma E.1, its rotated healthy relation contains a shortest path P . Lemma E.3 makes Be (P ) nonempty, and every member is a valid route in the faulted graph. Thus both fault-aware relations are all-pairs connected. The healthy path has length dH (s, t) in the mesh and dTn ([s], [t]) in the torus. Equation 54 gives the stated additive one-hop bound for every permitted fault-aware route. This is a bound relative to the healthy shortest-path distance, not a claim that every fault-aware route is shortest in the faulted graph. Mesh deadlock freedom. Let Φ(x, y) = x + 2y be the potential used in the proof of Theorem 4.1, and define Φj (v) = Φ(Qj v). (56) The map Qj sends the ordered directions of Uj to d0 , d1 , d2 , whose Φ increments are 1, 2, 1, and sends the ordered directions of Lj to d3 , d4 , d5 , whose increments are −1, −2, −1. Consequently, Φj strictly increases along every Uj channel and strictly decreases along every Lj channel, including all channels inserted by either bypass order. By Lemma E.3, every fault-aware group word belongs to L∗j U∗j . Hence every edge of the complete one-VC CDG is either within one group or directed from Lj to Uj . A directed CDG cycle using both groups would require a dependency from Uj back to Lj , which does not exist. A cycle wholly within Uj would force Φj to increase strictly around a closed dependency chain, and a cycle wholly within Lj would force it to decrease strictly. Both are impossible. The mesh complete resource CDG is therefore acyclic using one VC. Rotated torus coordinates. For G ∈ {Lj , Uj }, write HL,j , G = Lj , HG,j = HU,j , G = Uj .
(57)
Lemma E.1 makes Qj a quotient automorphism, so the maps in equation 33 are well-defined bijections because HU and HL are well-defined bijections. Their positive unwrapped direction increments are first direction middle direction third direction Uj ∆HU,j (dj−1 ) = 1 ∆HU,j (dj ) = k ∆HU,j (dj+1 ) = k − 1 (58) Lj ∆HL,j (dj+2 ) = 1 ∆HL,j (dj+3 ) = k ∆HL,j (dj+4 ) = k − 1. Preservation of the single-dateline property. In either group, replacing a middle-direction hop by either order of the two flank directions preserves its exact unwrapped advance: 1 + (k − 1) = (k − 1) + 1 = k. 22
(59)
The substitution does not change group boundaries. Each maximal same-group segment of a fault-aware route therefore corresponds to a segment of its healthy parent route and has exactly the same total unwrapped Hamiltonian advance. After rotation, the healthy bound in equation 47 remains 0 < S ≤ (n − 1)k = N − n < N.
(60)
Although an affected physical route has one additional hop, its value of S is unchanged. Since every individual increment in equation 58 is positive, reducing the unwrapped coordinate modulo N still produces at most one wrap in each maximal same-group segment. Thus the rotated per-hop VC rule is well-defined and changes from its pre-dateline to post-dateline phase at most once per segment. Torus resource-CDG acyclicity. Let c : [u] → [v] be a channel used by the fault-aware relation in group G, let h = HG,j (u) ∈ {0, . . . , N − 1}, and set ℓj (Lj ) = 0 and ℓj (Uj ) = 1. Define q = 0, h, rj (c, q) = 2N ℓj (G) + h, q = 1 and c is a dateline channel for G, N + h, q = 1 and c is non-dateline.
(61)
This rank depends only on the resource (c, q). Consider consecutive resources within one group, and let s ∈ {1, k − 1, k} be the positive increment of the first channel. Before the dateline, a VC0 → VC0 dependency changes the tail coordinate from h to h + s without wrap and strictly increases the rank. If the second resource is the dateline channel, its tail coordinate is again h + s > h; assigning it VC1 uses the dateline case of equation 61 and still increases the rank. If the first resource is the dateline channel, the next tail coordinate is h + s − N , and the next non-dateline VC1 resource has contribution N +(h+ s− N ) = h+ s > h. After that crossing, Equation 60 excludes a second wrap, so two consecutive non-dateline VC1 resources retain the N offset while their tail coordinates increase by s. These cases include the new bypass turns because the argument uses only their group membership and the positive increment of the first channel. Finally, every used Lj resource has rank at most 2N − 1, whereas every used Uj resource has rank at least 2N . Lemma E.3 permits only Lj → Uj cross-group dependencies, so each such dependency strictly increases the rank even when the VC state is reset. Every edge of the complete resource CDG therefore strictly increases equation 61. A directed cycle is impossible, and the torus fault-aware relation is deadlock-free using two VCs.
The proposition is limited to a single static bidirectional link failure under a globally consistent routing epoch. With multiple failed links, a triangle bypass may itself be unavailable; a node failure removes several incident channels; and an in-flight configuration change permits dependencies from both the old and new relations. None of those enlarged resource relations is covered by the proof above.
F Reassessment of the Three-VC Scheme of Shamaei et al. This appendix verifies Proposition 2.1 under the routing and VC-assignment rules stated by Shamaei et al. (2013). A Type-1 route may take an arbitrary ordering of a steps in ω 0 and b steps in ω 1 ; a message is classified as wraparound when it traverses at least one wraparound link; and every hop of a wraparound Type-1 message uses VC class 1. Under the identification ω 0 = d0 and ω 1 = d1 , the generator 4 + 3ω yields the period vectors T1 = (4, 3) and T2 = (−3, 7) used to represent their H4 instance in our coordinates. Table 7 gives one complete route witnessing each edge of the cycle in equation 1. A superscript W marks a projected hop that crosses the chosen fundamental-domain boundary; unmarked hops are regular. Coordinates are canonical representatives in V4 . 23
Figure 8: Unfolded visualization of the resource cycle in Proposition 2.1. The red polyline is not a single seven-hop packet route. Segment ci is a resource held by witness packet Pi while that packet requests ci+1 (indices modulo seven). The two endpoints differ by T1 and therefore project to the same torus node. Table 7: Minimal wraparound Type-1 routes witnessing the seven edges of equation 1.
Packet
Dependency
P0 P1 P2 P3 P4 P5 P6
c0 → c1 c1 → c2 c2 → c3 c3 → c4 c4 → c5 c5 → c6 c6 → c0
Complete projected route W
(3, 0) −→ (0, −3) → (1, −3) W (−3, 3) −→ (0, −3) → (1, −3) → (2, −3) W (1, −3) → (2, −3) → (3, −3) −→ (−3, 1) W (−1, 3) −→ (2, −3) → (3, −3) → (3, −2) W (3, −3) → (3, −2) → (3, −1) −→ (−3, 3) W (3, −2) → (3, −1) → (3, 0) −→ (0, −3) W (3, −1) → (3, 0) −→ (0, −3)
Length 2 3 3 3 3 3 2
Verification of Proposition 2.1. Interpret the projected channels in Table 7 modulo Λ4 = ⟨T1 , T2 ⟩,
T1 = (4, 3),
T2 = (−3, 7).
(62)
Every listed hop is then in direction d0 or d1 , so every witness is a Type-1 route. Each row contains at least one marked wraparound hop; under the published VC table, every resource used by that packet is therefore in VC class 1. It remains to verify minimality without relying on the claimed acyclicity result. Lift each projected route to the infinite lattice using its d0 /d1 direction word, and let ∆i be its lifted source-to-destination displacement. Because ∆i = ai d0 + bi d1 with ai , bi ≥ 0, Lemmas 3.1 and 3.2 give ∥∆i ∥H = ai + bi = Li , 24
Li ∈ {2, 3},
(63)
where Li is the listed route length. Lemma C.1 with n = 4 gives ∥µ∥H ≥ 7 for every nonzero µ ∈ Λ4 . Hence, for every alternative destination lift, ∥∆i + µ∥H ≥ ∥µ∥H − ∥∆i ∥H ≥ 7 − Li > Li .
(64)
Thus the displayed lift is the unique closest lift and every witness route is minimal on the H4 quotient represented above. For each i, the complete route Pi contains channel ci immediately followed by ci+1 , with indices modulo seven. Since both resources use VC class 1, Pi induces the CDG edge (ci , 1) → (ci+1 , 1). Taking all seven witness packets yields the closed directed resource cycle equation 1. The argument above establishes only the statement of Proposition 2.1. Theorem 2 of the prior paper reasons from the length 2n − 1 of a complete same-type geometric cycle relative to the network diameter n − 1. That observation does not exclude a resource-CDG cycle assembled from distinct minimal packets, each contributing only one adjacent resource dependency. The witnesses in Table 7 have length at most the H4 diameter of three hops, yet their union contains the seven-resource cycle in equation 1. Therefore the stated argument is insufficient to establish acyclicity of the complete resource CDG. This conclusion is deliberately limited. For a fully adaptive routing function, a cycle in the union CDG is not by itself a construction of a reachable wormhole deadlock: packets may retain alternative outputs or an escape structure not represented by one selected witness route. The result therefore contradicts the published complete-CDG acyclicity claim, but it does not by itself prove that the full three-VC routing algorithm can reach a packet-level deadlock.
25