Research On Two Fault Diagnosability And Diagnosis Algorithms Of Interconnection Networks

The interconnection networks have a very important influence on the overall performance of high-performance computer systems.Hypercubes,exchange hypercubes,star graphs,hierarchical star networks,(n,k)-star graphs and(n,k)-bubble-sort graphs are widely studied interconnection networks of computer systems.The conditional diagnosability is an important parameter to measure the diagnosability of interconnection networks.The Rg-conditional diagnosability is a new extension of conditional diagnosability,which restricts every vertex containing at least g fault-free neighbors.The researches show that it can more accurately measure the diagnosability of interconnection networks under specific fault models.The local diagnosis can be regarded as a local strategy toward the diagnosis of networks,which puts more emphasis on identifying the fault state of a given processor.The conditional local diagnosability and g-goodneighbor local diagnosability are generalizations of local diagnosability,they can measure the diagnosability of a single vertex more accurately.This paper studies the Rg-conditional diagnosability of the hypercube-like networks,the relationship between the Rg-conditional diagnosability and Rg-conditional connectivity of general networks,the conditional local diagnosability of regular networks and related algorithms,and the g-good-neighbor local diagnosability of star graphs.These studies can provide a theoretical basis for the diagnosability analysis and fault diagnosis algorithm design of parallel computer systems.In this paper,we firstly study the Rg-conditional diagnosability of the hypercube-like networks under the PMC model,and present its upper and lower bounds under some reasonable conditions.Applying our results,an improved lower bound of Rg-conditional diagnosability of hypercubes and a pair of upper and lower bounds of the Rg-conditional diagnosability of exchanged hypercubes are given.Next,we discuss the relationships between the Rg-conditional diagnosability tRg(G)of a graph G and its Rg-conditional connectivity κRg(G)under the PMC and MM*models.We establish the Rg-conditional diagnosability tRg(G)=κR2g+1(G)+g under some reasonable conditions,except for the R1conditional diagnosability of G under the MM*model.Moreover,we show under the MM*model,tR1(G)=κRz(G)with similar conditions.Applying our results,the Rg-conditional diagnosability of(n,k)-star graphs and(n,k)bubble-sort graphs are determined.Finally,we study the local diagnosability of regular networks under MM*model,and prove that a sufficient condition for a regular network to be conditionally locally t-diagnosable at a given node under the MM*model.As its application,we deduce the conditional diagnosability of hierarchical star networks.We also design a conditional local fault diagnosis algorithm A*under the MM*model.When a regular network contains a balanced three-tiered tree T(ν,α,α-1,β)rooted at ν,and the number of fault vertices in the network does not exceed(2α+β-3),Algorithm A*can accurately identify the fault or fault-free status of vertex ν and its time complexity is o(α2β2).Compared with existing algorithms,our algorithm allows more fault vertices to arise in a network.Moreover,The g-good-neighborhood local diagnosability of star graphs under PMC model is also obtained.