Fault Tolerance And Diagnosis Of Some Interconnection Networks

A multiprocessor system is often modeled as an interconnection network,which may contain thousands or even more processors.The topology of an interconnection network is an undirected,connected and simple graph,where vertex and edge repre-sent the processor and the link between two processors,respectively.As a significant increase in the number of processors,the processor failure is inevitable.Hence,fault tolerance and fault diagnosis of interconnection networks have become increasingly important.The conditional faulty set is a special faulty set that does not contain all of neighbors of any vertex in a network.The conditional diagnosability is a metric that can give the maximum number of conditional faulty set that the system is guaranteed to i-dentify.The g-good-neighbor conditional diagnosability is a metric that every fault-free vertex should have at least g fault-free neighbors.For the purpose of self-diagnosis of a system,some different models have been proposed.Among them,the PMC model and the MM*model are widely used.Fault-tolerant and diagnosing capabilities are important indicators of performance of interconnection networks.In this thesis,we explore the fault tolerance and diagnos-ability of some interconnection networks and get the following results.(1)We study the strong matching preclusion problem for burnt pancake graphs BPn.As a result,we find the strong matching preclusion number for the burnt pancake graphs BPn and show that every optimal strong matching preclusion set of burnt pancake graphs BPn is trivial for n ? 3.(2)We show that the n-dimensional twisted hypercube Hn has a fault-free Hamil-tonian cycle if the number of faulty edges and/or vertices is no more than n-2,and it has a fault-free Hamiltonian path between any pair of non-faulty vertices if the number of faulty edges and/or vertices is no more than n-3.(3)We first determine the Rg-vertex-connectivity of n-dimensional twisted hyper-cube Hn,then establish the g-good neighbor conditional diagnosability of n-dimensional twisted hypercube Hn under the PMC model and MM*model,respectively.(4)We first determine the Rg-vertex-connectivity of locally exchanged twisted cubes LeTQ(s,t),and then establish the g-good neighbor conditional diagnosability of locally exchanged twisted cubes LeTQ(s,t)under the PMC model and MM*model,respectively.