For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
An Optimal Adaptive Diagnosis of Butterfly Networks
Aya OKASHITA Toru ARAKI Yukio SHIBATA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2003/05/01
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
system-level diagnosis, PMC model, adaptive diagnosis, t-diagnosable system, butterfly network,
Full Text: PDF>>
System-level diagnosis is a very important technique for identifying faulty processors in a system with a large number of processors. Processors can test other processors, and then output the test results. The aim of diagnosis is to determine correctly the faulty/fault-free status of all processors. The adaptive diagnosis have been studied in order to perform diagnosis more efficiently. In this paper, we present adaptive diagnosis algorithms for a system modeled by butterfly networks. Our algorithms identify all faulty nodes in butterfly networks with the optimal number of tests. Then, we design another algorithm for diagnosis with very small constant number of rounds.