Relating Diagnosability, Strong Diagnosability and Conditional Diagnosability of Strong Networks

An interconnection network´s diagnosability is an important measure of its self-diagnostic capability. Based on the classical notion of diagnosability, strong diagnosability and conditional diagnosability were proposed later to better reflect the networks´ self-diagnostic capability under more realistic assumptions. In this paper, we study a class of interconnection networks called strong networks, which are n-regular, (n - 1)-connected, and with cn-number no more than n - 3. We build a relationship among the three diagnosability measures for strong networks. Under both PMC and MM* models, given a strong network G with diagnosability t, we prove that G is strongly t-diagnosable if and only if G´s conditional diagnosability is greater than t. A simple check can show that almost all well-known regular interconnection networks are strong networks. The significance of this paper´s result is that it reveals an important relationship between strong and conditional diagnosabilities, and the proof of strong diagnosability for many interconnection networks under MM* or PMC model is not necessary if their conditional diagnosability can be shown to be strictly larger than their diagnosability.