A Systematic Algorithm for Identifying Faults on Hypercube-Like Networks Under the Comparison Model
Author:
- 23 February 2012
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Reliability
- Vol. 61 (2) , 452-459
Abstract
There is a growing demand for fault diagnosis to increase the reliability of systems. Diagnosis by comparison is a realistic approach to the fault diagnosis of multiprocessor systems. In this paper, we consider n-dimensional hypercube-like networks for n ≥ 5. We propose an efficient fault diagnosis algorithm for n-dimensional hypercube-like networks under the MM comparison model by exploiting the Hamiltonian and extended-star properties. Applying our algorithm, the faulty processors in n-dimensional hypercubes, n-dimensional crossed cubes, n-dimensional twisted cubes, and n-dimensional Möbius cubes can all be diagnosed in linear time provided the number of faulty processors is not more than the dimension n.Keywords
This publication has 31 references indexed in Scilit:
- Efficient unicast in bijective connection networks with the restricted faulty node setInformation Sciences, 2011
- Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elementsTheoretical Computer Science, 2007
- The t/k-diagnosability of the BC graphsIEEE Transactions on Computers, 2005
- Diagnosability of t-connected networks and product networks under the comparison diagnosis modelIEEE Transactions on Computers, 2004
- The diagnosability of the matching composition network under the comparison diagnosis modelIEEE Transactions on Computers, 2004
- The Mobius cubesIEEE Transactions on Computers, 1995
- The crossed cube architecture for parallel computationIEEE Transactions on Parallel and Distributed Systems, 1992
- A variation on the hypercube with lower diameterIEEE Transactions on Computers, 1991
- The twisted N-cube with application to multiprocessingIEEE Transactions on Computers, 1991
- Topological properties of hypercubesIEEE Transactions on Computers, 1988