An Optimal Adaptive Diagnosis of Butterfly Networks

Aya OKASHITA  Toru ARAKI  Yukio SHIBATA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E86-A   No.5   pp.1008-1018
Publication Date: 2003/05/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
system-level diagnosis,  PMC model,  adaptive diagnosis,  t-diagnosable system,  butterfly network,  

Full Text: PDF>>
Buy this Article




Summary: 
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.