Premium
Optimal adaptive fault diagnosis for simple multiprocessor systems
Author(s) -
Kranakis Evangelos,
Pelc Andrzej,
Spatharis Anthony
Publication year - 1999
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199910)34:3<206::aid-net5>3.0.co;2-f
Subject(s) - multiprocessing , computer science , fault (geology) , simple (philosophy) , computerized adaptive testing , parallel computing , torus , algorithm , mathematics , statistics , geometry , seismology , geology , psychometrics , philosophy , epistemology
We studied adaptive system ‐ level fault diagnosis for multiprocessor systems. Processors can test each other and future tests can be selected on the basis of previous test results. Fault‐free testers give always correct test results, while faulty testers are completely unreliable. The aim of diagnosis is to determine correctly the fault status of all processors. We present adaptive diagnosis algorithms for systems modeled by trees , rings , and tori . These algorithms use the smallest possible number of tests in each case. Our results also imply optimal diagnosis for more general systems, assuming a small number of faults. The cost of adaptive diagnosis were found to be significantly smaller than that of classical ( one ‐ step ) diagnosis. © 1999 John Wiley & Sons, Inc. Networks 34: 206–214, 1999