Abstract:

Network diagnosis is one of the most exciting topics in graph theory and network science,which affects the reliability and security of multiprocessor systems.With the rapid growth of the scale of the multiprocessor system,the applicability of the global fault diagnosis mode of the system is reduced.Accordingly,the local fault diagnosis benefits from the lower requirements for the network topology,which can process the network in blocks,greatly improving the diagnosis efficiency,having a stronger applicability,and becoming a new research direction.Under the latest Symmetric PMC(SPMC) model,this paper studies the relevant properties of network node diagnosis(local diagnosis),proposes a new topology structure(extended tree structure),obtains the judgment conditions for diagnosable nodes,the relationship between nodes diagnosis and system diagnosis,gives the judgment theorem whether nodes are poor on the extended tree structure,and gives out the detailed proof.According to this theorem,one novel network local fault diagnosis algorithm ST₂_B-FDA with the expanded tree structure is proposed.To validate the effectiveness of this algorithm,this paper applies the Hypercube network for simulation.The time complexity of the algorithm is O(NlogN),which is much lower than that of some traditional fault diagnosis algorithms.This algorithm can effectively reduce the diagnosis cost and greatly improve the diagnosis efficiency.In addition,the proposed algorithm is simple in principle,easy to implement and apply,and can also be used as one of the diagnosis methods for large-scale regular network systems.

Key words: system fault diagnosis, SPMC model, nodes diagnosis, expanded tree structure, diagnosis algorithm