loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
2004 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN'04)
Optimal Adaptive Fault Diagnosis of Cubic Hamiltonian Graphs
Hong Kong, SAR, China
May 10-May 12
ISBN: 0-7695-2135-5
Toru Araki, Iwate University, Japan
We study the problem of adaptive fault diagnosis for multiprocessor systems modeled by cubic hamiltonian graphs. Each node in a system is either faulty or fault-free, and the aim of fault diagnosis is to identify correctly faulty/fault-free status of all nodes. In order to achieve it, each node tests their neighbors and output the results of tests. If the test node is fault-free, it always outputs correct test results, but if the test node is faulty, the result of the test cannot be trusted.
We give a sufficient condition for a cubic hamiltonian graph to be adaptively diagnosed in 3 testing rounds, provided that each node participates in at most one test of each round. It is the optimal number of testing rounds. The class of these graphs that satisfy this condition contains several important networks.
Citation:
Toru Araki, "Optimal Adaptive Fault Diagnosis of Cubic Hamiltonian Graphs," ispan, pp.162, 2004 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.