Paper Info
Title
Diagnosis of t/(t +1)-Diagnosable Systems
Abstract
A classic PMC (Preparata, Metze, and Chien) multiprocessor system [F. P. Preparata, G. Metze, and R. T. Chien, IEEE Trans. Electr. Comput., EC-16 (1967), pp. 848--854] composed of $n$ units is said to be $t/(t+1)$ diagnosable [A. D. Friedman, A new measure of digital system diagnosis, in Dig. 1975 Int. Symp. Fault-Tolerant Comput., 1975, pp. 167--170] if, given a syndrome (complete collection of test results), the set of faulty units can be isolated to within a set of at most $t+1$ units, assuming that at most $t$ units in the system are faulty. This paper presents a methodology for determining when a unit $v$ can belong to an allowable fault set of cardinality at most $t$. Based on this methodology, for a given syndrome in a $t/(t+1)$-diagnosable system, the authors establish a necessary and sufficient condition for a vertex $v$ to belong to an allowable fault set of cardinality at most $t$ and certain properties of $t/(t+1)$-diagnosable systems. This condition leads to an $O(n^{3.5}) t/(t+1)$-diagnosis algorithm. This $t/(t+1)$-diagnosis algorithm complements the $t/(t+1)$-diagnosability algorithm of Sullivan [The complexity of system-level fault diagnosis and diagnosability, Ph. D. thesis, Yale University, New Haven, CT, 1986].
Year
DOI
Venue
1994
10.1137/S0097539790187539
SIAM Journal on Computing
Keywords
Field
DocType
fault-tolerant comput,multiprocessor system,allowable fault,g. metze,diagnosable systems,diagnosability algorithm,diagnosable system,diagnosis algorithm,system-level fault diagnosis,f. p. preparata,digital system diagnosis,upper bound,vertex cover,fault isolation
Discrete mathematics,Graph algorithms,Graph,Combinatorics,Vertex (geometry),Fault detection and isolation,Cardinality,Multiprocessing,System diagnosis,Mathematics
Journal
Volume
Issue
ISSN
23
5
0097-5397
Citations 
PageRank 
References 
16
0.86
5
Authors
3
Name
Order
Citations
PageRank
Anindya Das121931.78
Krishnaiyan Thulasiraman231531.10
V. K. Agarwal336044.82