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 identify.In a graph G,the connectivity of G,denoted by??G?,is the number,such that at least??G?vertices have to be removed to disconnect G.??G?is no more than the minimum vertex degree of the graph.In this case,F`abrega et al.proposed the g-extra connectivity,which is of great interest.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.In this thesis,we explore some properties of some interconnection networks and get the following results.?1?The 1,2,3-extra connectivity of the bubble-sort star graph BS_nare 4n-8?n?4?,6n-15?n?5?and 8n-23?n?5?,respectively.The conditional diagnosability of the bubble-sort star graphs under the PMC and the MM model are 8n-21?n?5?and6n-15?n?6?,respectively.?2?The conditional diagnosability of the round matching composition network G=?G₁,G₂,···,G_r;M^??under the PMC and the MM model are 4k+1 and 3k+1?k?4?,respectively.Applying the results,we determine the conditional diagnosability of the k-ary n-cubes and the recursive circulant graphs under the PMC and the MM model,respectively.?3?The 1,2-extra connectivity of the?n,k?-bubble-sort graph B_n,kare n+k-3 and n+2k-5,respectively,where n?5,3?k?n-2.The conditional diagnosability of the?n,k?-bubble-sort graphs under the MM model is n+2k-5,where n?5,3?k?n-2.?4?The 1,2,3-extra connectivity of the S P_ngraph are 2n-4?n?3?,3n-7?n?5?and 4n-10?n?6?,respectively.The conditional diagnosability of the S P_ngraphs under the MM model is 3n-7?n?5?.Applying the results,we determine the 1,2,3-extra connectivity and the conditional diagnosability of the star graphs and the pancake graphs under the MM model,respectively.