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

• 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 6n−176n−17 or fewer nodes, Sn2∖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 8n−258n−25 or fewer nodes, Sn2∖F, excluding a subset of at most three nodes, contains one large connected component.
• We show that the classic diagnosability of Sn2 (n≥2n≥2) under the PMC model is 2n−32n−3.
• We also establish that the conditional diagnosability and the strong diagnosability of Sn2 are 8n−238n−23 and 2n−32n−3 under the PMC model.

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+1t+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 Sn2), a well-known interconnection network model for multiprocessor systems, under the PMC (Preparata, Metze, and Chien) model. We show that the conditional diagnosability of Sn2(n≥4)(n≥4) is 8n−238n−23, which is about four times of its traditional diagnosability. As a byproduct, the strong diagnosability of Sn2 is also obtained.