Fault-Tolerant Shared-Relay Communication in Circulant Interconnection 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 worstcase 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, loadbalance scope, certified upper-bound interpretation of heuristic designs, exact small-n calibration, a software lookup-versussearch 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.