Fault Tolerance And Diagnostic Analysis Of A Class Of Cayley Graphs

In large parallel computing and communication systems,processors are connected by communication links according to some interconnection networks,where the processors and communication links correspond to the vertices and edges in the networks respectively.In the large-scale interconnection networks,it can not avoid faulty vertex and faulty edge occurred,thus the research of the fault tolerance and diagnosis for networks is of crucial importance.In this paper,the fault tolerance and diagnosis of a class of Cayley graphs arestudied by deterministic methods.In this paper,we first introduce some basic knowledges on graphs,some parameters to measure the fault tolerance and diagnosis of interconnection networks and their research status.Then we studyseveral important measurement parameters of bubble sortnetworks and arrangement graphs.The following is the main content of this paper:In the first chapter,we briefly introduce the research background and research status of this paper,some basic concepts of graph theory,reliability and diagnosability of interconnection networks.In the second chapter,we first prove that both the k-restrictedvertexconnectivity and k-restricted edgeconnectivity of the bubble sort networks are 2k(n-k-1)for k ≤ n/2.Then we study theg-good-neighbor conditional diagnosability and h-edge tolerable diagnosability of the bubble sort networks under the PMC model and MM*model.In the third chapter,we study the fault tolerance and diagnosis of arrangement graphs,and determine the g-restricted vertexconnectivity of An,2,the 2-restricted edgeconnectivity of An,k,and the traditional diagnosis of An,2 under the PMC model and MM*model.In the fourth chapter,we give a conclusion and show the problems that can be further studied.In a word,we study the fault tolerance and diagnosis of two kinds of networks,and theresults provide theoretical support for the promotion and application of the above-mentioned interconnection networks.