Conditional diagnosability and strong diagnosability of Split-Star Networks under the PMC model

• DOI: 10.1016/j.tcs.2014.10.046
• Publication Date: 2014-11-04T01:03:45Z
• Authors: Limei Lin; Li Xu; Shuming Zhou
• Keywords: 0102 computer and information sciences; 01 natural sciences

An interconnection network's diagnosability is an important measure of its self-diagnostic capability. The classical problems of fault diagnosis are explored widely. The conditional diagnosability is proposed by Lai et al. as a new measure of diagnosability, which can better measure the diagnosability of regular interconnection networks. The conditional diagnosability is an important indicator of the robustness of a multiprocessor system in presence of failed processors. Furthermore, a multiprocessor system is strongly t-diagnos-able, if it is t-diagnosable and can achieve diagnosability t + 1 except for the case where a node's neighbors are all faulty. The conditional diagnosability and strong diagnosability were proposed later to better reflect the networks' self-diagnostic capability under more realistic assumptions. In this paper, we determine the conditional diagnosability of an n-dimensional Split-Star Network (denoted as S n 2 ), a well-known interconnection network model for multiprocessor systems, under the PMC (Preparata, Metze, and Chien) model. We show that the conditional diagnosability of S n 2 ( n ? 4 ) is 8 n - 23 , which is about four times of its traditional diagnosability. As a byproduct, the strong diagnosability of S n 2 is also obtained. We investigate the combinatorial properties and fault-tolerant properties of the Split-Star Network.We show that as long as a fault-set F has 6 n - 17 or fewer nodes, S n 2 ? F , excluding a subset of at most two nodes, contains one large connected component.We show that as long as a fault-set F has 8 n - 25 or fewer nodes, S n 2 ? F , excluding a subset of at most three nodes, contains one large connected component.We show that the classic diagnosability of S n 2 ( n ? 2 ) under the PMC model is 2 n - 3 .We also establish that the conditional diagnosability and the strong diagnosability of S n 2 are 8 n - 23 and 2 n - 3 under the PMC model.