A new diagnosis algorithm for regular interconnected structures

We present a new diagnosis algorithm (NDA) for regular interconnected structures. The diagnosis algorithm has time complexity $O(kn)$ when applied to $k$-regular systems of $n$ units. It provides a correct diagnosis, although incomplete. The diagnosis is correct if the number of faulty units is not above a specified bound $T_sigma$, asserted by the algorithm itself. The correctness and completeness of ALG is studied through simulations on toroidal grids and hypercubes. Simulation results show that ALG provides a correct diagnosis even when the number of faults is very high (near half of the system size). The comparison between algorithm ALG and other diagnostic algorithms shows that ALG provides a better diagnosis, i.e., it has an higher degree of completeness than other diagnostic algorithms.