COMPLEXITY OF FAULT-DIAGNOSIS IN COMPARISON MODELS

被引：38
作者：
BLOUGH, DM
PELC, A
机构：
[1] UNIV CALIF IRVINE,INFORMAT & COMP SCI,IRVINE,CA 92717
[2] UNIV QUEBEC,DEPT INFORMAT,HULL J8X 3X7,QUEBEC,CANADA
来源：
IEEE TRANSACTIONS ON COMPUTERS | 1992年 / 41卷 / 03期
关键词：
COMPARISON TESTING; COMPLEXITY; FAULTY PROCESSORS; OPTIMAL DIAGNOSIS; PROBABILISTIC MODEL; SYNDROME;
D O I：
10.1109/12.127443
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
In this paper, we consider a comparison-based probabilistic model for multiprocessor fault diagnosis. We study the problem of optimal diagnosis, which is to correctly identify the status (faulty/fault-free) of units in the system, with maximum probability. For some parameter values, this probabilistic model is well approximated by the asymmetric comparison model introduced by Malek. For arbitrary systems it is shown that optimal diagnosis in the probabilistic model and in Malek's model is NP-hard. However, we construct efficient diagnosis algorithms in the asymmetric comparison model for a class of systems corresponding to bipartite graphs which includes hypercubes, grids, and forests. Furthermore, for ring systems, we present a linear-time algorithm to perform optimal diagnosis in the probabilistic model.
引用
收藏
页码：318 / 324
页数：7
相关论文
共 15 条
[1]  
BLOUGH D, 1989, 19TH INT IEEE S FAUL, P62
[2]  
Blough D. M., 1988, Eighteenth International Symposium on Fault-Tolerant Computing. Digest of Papers. FTCS-18 (Cat. No.88CH2543-7), P260, DOI 10.1109/FTCS.1988.5329
[3]  
BLOUNT ML, 1977, FTCS, V7, P72
[4]  
BONDY JA, 1976, GRAPH THEORY APPLICA
[5]   SCHEMES FOR FAULT-TOLERANT COMPUTING - A COMPARISON OF MODULARLY REDUNDANT AND T-DIAGNOSABLE SYSTEMS [J].
CHWA, KY ;
HAKIMI, SL .
INFORMATION AND CONTROL, 1981, 49 (03) :212-238
[6]  
DAHBURA AT, 1987, IEEE T COMPUT, V36, P373, DOI 10.1109/TC.1987.1676912
[7]  
FUJIWARA H, 1978, IEEE T COMPUT, V27, P881, DOI 10.1109/TC.1978.1674966
[8]  
FUJIWARA H, 1978, IEEE T COMPUT, V27, P280, DOI 10.1109/TC.1978.1675087
[9]  
Garey M.R., 1979, COMPUTERS INTRACTABI, V174
[10]  
Hopcroft J. E., 1973, SIAM Journal on Computing, V2, P225, DOI 10.1137/0202019
12