Search papers, labs, and topics across Lattice.
This paper investigates fault-tolerant communication in directed circulant interconnection networks by mapping the degree-redundancy landscape for a two-hop shared-relay primitive. The authors establish a framework that quantifies the worst-case shared-relay multiplicity \( R(n,m) \) and introduces parameters such as \( D_f(n) \) to analyze relay survivability under various fault conditions. Key findings reveal that optimized generator designs significantly enhance fault tolerance, achieving \( f \)-relay-fault tolerance close to the theoretical lower bound, while conventional designs may fail even at higher degrees.
Optimized generator choices can boost relay survivability by up to 1.63 times the theoretical lower bound in fault-tolerant circulant networks.
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 $D_f(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.
