A Systematic Algorithm for Identifying Faults on Hypercube-Like Networks Under the Comparison Model

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 considern-dimensional hypercube-like networks forn≥ 5. We propose an efficient fault diagnosis algorithm forn-dimensional hypercube-like networks under the MM comparison model by exploiting the Hamiltonian and extended-star properties. Applying our algorithm, the faulty processors inn-dimensional hypercubes,n-dimensional crossed cubes,n-dimensional twisted cubes, andn-dimensional Möbius cubes can all be diagnosed in linear time provided the number of faulty processors is not more than the dimensionn.