Distributed diagnosis algorithms for regular interconnected structures

1 July 1992

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers

Vol. 41 (7) , 899-906
https://doi.org/10.1109/12.256447

Abstract

A distributed diagnosis algorithm to locate faulty processing elements in large-scale regular interconnected structures based on the concepts of system-level diagnosis is developed. This algorithm can either operate in a systolic manner or may be executed on a supervisory processor to locate the faulty processors. The computational complexity of the algorithm is linear when run on a supervisory processor and constant when run in parallel systolic manner. The implementation complexity and diagnosis capability of the algorithm are also analyzed without restricting the fault set size. The probability of correct diagnosis is shown to be very high even in the presence of large fault sets.<>

Keywords

This publication has 15 references indexed in Scilit:

Distributed diagnosis algorithms for regular interconnected structures
IEEE Transactions on Computers, 1992
t-TDA-diagnosable systems
IEEE Transactions on Computers, 1989
On the complexity of single fault set diagnosability and diagnosis problems
IEEE Transactions on Computers, 1989
A Generalized Theory for System Level Diagnosis
IEEE Transactions on Computers, 1987
An 0(n^2.5) Fault Identification Algorithm for Diagnosable Systems
IEEE Transactions on Computers, 1984
Greedy Diagnosis of Hybrid Fault Situations
IEEE Transactions on Computers, 1983
Diagnosis of Systems with Asymmetric Invalidation
IEEE Transactions on Computers, 1981
A fault diagnosis algorithm for asymmetric modular architectures
IEEE Transactions on Computers, 1981
Universal System Diagnosis Algorithms
IEEE Transactions on Computers, 1979
On the Connection Assignment Problem of Diagnosable Systems
IEEE Transactions on Electronic Computers, 1967