((t,k))-diagnosis, which is a generalization of sequential diagnosis, requires that at least (k) faulty processors should be identified and repaired in each iteration provided there are at most (t) faulty processors, where (t\ge k). In this paper, we propose a unified approach for computing the ((t,k))-diagnosability of numerous multiprocessor systems (graphs) under the Preparata, Metze, and Chien's model, including hypercubes, crossed cubes, twisted cubes, locally twisted cubes, multiply-twisted cubes, generalized twisted cubes, recursive circulants, Möbius cubes, Mcubes, star graphs, bubble-sort graphs, pancake graphs, and burnt pancake graphs. Our approach first sketches the common properties of the above classes of graphs, and defines a superclass of graphs, called (m)-dimensional component-composition graphs, to cover them. We then show that the (m)-dimensional component-composition graph (G) for (m ≥ 4) is ((Ω (h),κ (G)))-diagnosable, where h= and (κ (G)) and (V(G)) denote the node connectivity and the number of nodes in (G), respectively. Based on this result, the ((t,k))-diagnosability of the above multiprocessor systems can be computed efficiently.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Hardware and Architecture
- Computational Theory and Mathematics