Diagnosability of crossed cubes under the comparison diagnosis model

Diagnosability of a multiprocessor system is one important study topic in the parallel processing area. As a hypercube variant, the crossed cube has many attractive properties. The diameter, wide diameter and fault diameter of it are all approximately half of those of the hypercube. The power that t...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on parallel and distributed systems 2002-10, Vol.13 (10), p.1099-1104
Main Author: Fan, Jianxi
Format: Article
Language:English
Subjects:
Algorithms
Computer simulation
Cubes
Diagnosis
Fault diagnosis
Faults
Hypercubes
Maintenance
Multiprocessing systems
Parallel processing
Polynomials
Power system modeling
System testing
Topology
Trees
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Diagnosability of a multiprocessor system is one important study topic in the parallel processing area. As a hypercube variant, the crossed cube has many attractive properties. The diameter, wide diameter and fault diameter of it are all approximately half of those of the hypercube. The power that the crossed cube simulates trees and cycles is stronger than the hypercube. Because of these advantages of the crossed cube, it has attracted much attention from researchers. We show that the n-dimensional crossed cube is n-diagnosable under a major diagnosis model-the comparison diagnosis model proposed by Malek (1980) and Maeng and Malek (1981) if n/spl ges/4. According to this, the polynomial algorithm presented by Sengupta and Dahbura (1992) may be used to diagnose the n-dimensional crossed cube, provided that the number of the faulty nodes in the n-dimensional crossed cube does not exceed n. The conclusion of this paper also indicates that the diagnosability of the n-dimensional crossed cube is the same as that of the n-dimensional hypercube when n>5 and better than that of the n-dimensional hypercube when n=4.
ISSN:1045-9219
1558-2183
DOI:10.1109/TPDS.2002.1041887