algorithms for finding diagnosability level and t-diagnosis in a network of processors
In this paper, using a digraph model we present both exact and suboptimum algorithms for finding the maximum level of diagnosis capability offered by a given network of processors. The exact algorithm is based on the Chwa-Hakimi characterization for t-diagnosability and the suboptimum method uses an algorithm for maximum matching in bipartite graphs. Finally, using the notion of syndrome information set, an O(t 3 ) algorithm is presented for t-diagnosis in a large D(N,t,X) system of interconnected processors. Syndrome processing is assumed to be done in a separate fault-free processor.
t-diagnosis fault-tolerant arrays distributing processing