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
CHWA, KY
HAKIMI, SL
[J]. 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

← 1 2 →