Optimal Diagnosable Systems on Cayley Graphs

Toru ARAKI  Yukio SHIBATA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E85-A   No.2   pp.455-462
Publication Date: 2002/02/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
Keyword: 
fault diagnosis,  PMC models,  highly structured systems,  Cayley graphs,  multiprocessor systems,  

Full Text: PDF>>
Buy this Article




Summary: 
In this paper, we investigate self diagnosable systems on multi-processor systems, known as one-step t-diagnosable systems introduced by Preparata et al. Kohda has proposed "highly structured system" to design diagnosable systems such that faulty processors are diagnosed efficiently. On the other hand, it is known that Cayley graphs have been investigated as good models for architectures of large-scale parallel processor systems. We investigate some conditions for Cayley graphs to be topologies for optimal highly structured diagnosable systems, and present several examples of optimal diagnosable systems represented by Cayley graphs.