Constant-time repair for dense Gaussian and EJ networks

Bader Albader's new paper presents constant-time certificate selectors for local broadcast repair in dense Gaussian and Eisenstein-Jacobi (EJ) networks. These algebraic interconnection networks have compact coordinate balls, fixed degree, and simple modular addressing. In fault-free networks, a source-centered coordinate-reduction tree provides a non-redundant one-to-all broadcast. However, processor faults can split the tree into multiple healthy components. Traditional search-based repair methods require a linear scan of the network to select a repair plan. Albader's certificate selectors operate in O(1) time and O(1) memory, consulting only the fault coordinates to classify the relative fault geometry and choose a coordinate-reduction orientation. The method returns a bounded ordered set of component-crossing repair edges.

For dense Gaussian networks G_k, every source-free fault set with |F| ≤ 2 is repaired with depth at most k+2 and exactly c-1 external component-crossing edges. For dense EJ networks H_t, one-fault repairs stay within depth t+1, and two-fault repairs within depth t+2, also with exactly c-1 external edges. Exhaustive strict validation confirmed the Gaussian selector over 146,156 one- and two-fault cases for k=5 to 12, and the EJ selector over 52,395 cases for t=2 to 8, with zero failures in connectivity, acyclicity, exact repair count, or depth bound. This breakthrough enables near-instant fault recovery in dense network topologies, critical for high-performance computing and distributed systems.