Dense Gaussian and Eisenstein–Jacobi (EJ) networks are algebraic interconnection networks with compact coordinate balls, fixed degree, and simple modular addressing. A source-centered coordinate-reduction tree gives a non-redundant one-to-all broadcast in the fault-free network, but processor faults can split the tree into multiple healthy components. Search-based local repair reconnects those components after scanning the network. Unlike search-based repair methods that require a linear scan of the network to select the repair plan, the certificate selectors introduced here operate in O(1) time and O(1) memory, consulting only the fault coordinates. This paper develops this stronger formulation for the one- and twofault regime: a constant-time certificate selector. Given only the faulty coordinates, the selector classifies the relative fault geometry, chooses a coordinate-reduction orientation, and returns a bounded ordered set of component-crossing repair edges. For dense Gaussian networks Gk, every source-free fault set with |F| ≤ 2 is repaired with depth at most k+2 and with exactly c−1 external component-crossing edges for the selected fault-pruned orientation. For dense EJ networks Ht, every one-fault placement is repaired within depth t + 1, and every two-fault placement is repaired within depth t + 2, again with exactly c − 1 external repair edges. The repair-plan decision uses explicit constantsize case tables, algebraic quotient-neighbor tests, and constantsize local edge lists; materializing the full repaired parent map remains Θ(N), which is unavoidable if all parent assignments are required. Exhaustive strict validation confirms the Gaussian selector over 146,156 one- and two-fault cases for k = 5, . . . , 12 and the EJ selector over 52,395 cases for t = 2, . . . , 8, with zero failures in connectivity, acyclicity, exact repair count, or depth bound.
Bader AlBader (Sun,) studied this question.