Strong Diagnosis And Local Diagnosis Of Interconnection Networks

The fault diagnosis is the process of identifying faulty processors in a system through testing. Diagnosability is an important parameter to measure the fault tolerance ability of interconnection network. In this dissertation, we show the fundamental theory and methods to study the strong diagnosability and local diagnosability of topological structure of interconnection networks. We apply them to the hypercubes and the star graph. The main contribution of this dissertation can be summarized as follows:After introducing the basic theory of the strong t-diagnosability for networks, we prove that the star graph has the strong t-diagnosability property, which means that the diagnosability of star graph can reach t+1 by restricting that all the neighboring vertices of any non-faulty vertices can not fail at the same time.Guo-Hang Hsu et al. introduced the local diagnosis for networks. This thesis applies the theory to study the local diagnosability at a given node in networks. We prove that the folded hypercube has the strong local diagnosability and the graph keeps the strong property even if it has up to n ? 1 faulty edges.Assuming that each vertex of a faulty BC graph is incident with at least two fault-free edges, we prove that the graph keeps the strong property even if it has up to 3( n - 2) - 1 faulty edges.After showing some properties of the generic star-pyramid graph, we prove that the graph keeps the strong property no matter how many edges are faulty under the condition that each vertex is incident with at least four fault-free edges.