A novel approach to comparison-based diagnosis for hypercube-like systems

Abstract

Interconnection network has been an active research area for parallel and distributed computer systems. The diagnosability is one of the important issues in the reliability of interconnection networks. In this paper, a novel idea on system diagnosis called local diagnosability is presented. The concept of local diagnosability is strongly related to the traditional global one. For this local sense, the status of every particular processor can be correctly identified. A sufficient condition is also proposed to determine the local diagnosability of a given processor. Following this local sense, we prove that the diagnosability of an n-dimensional hypercube-like network HLn is n for n >= 5, and show that in HLn with up to n - 2 faulty links, the local diagnosability of each processor equals to the connection links incident with it.