Fault Tolerance Analysis Of Alternating Group Network

It is well-known that the interconnection network is the base of information society and the communication algorithm is the key of information exchange. Seeking network topologies with good properties such as symmetry is indispensable to realize all kinds of effective communication, algorithms and protocols. Since S.B. Akers and B. Krishnamurthy advocated using Cayley graph (group graph) as the models of symmetric interconnection networks, some versatile designers and experts in graph theory introduce and research on a sequence of topologies, such as Hypercube, Star graph, Butterfly Network, Honeycomb Network and so on. As an impossible substitute of Star Graph, alternating group graph was proposed by J.S. Jwo, S.Lankshmivaraham and S.K.D. Dhall in 1993. They defined alternating group network AG_n. Youhu Ji proposed a new kind of alternating group network AN_n. Compared with AG_n, the degree of every node is less than AG_n (about one half of AG_n) and the diameter is equal to AG_n. We centre on the following problems based on the optimal algorithms proposed by Baoxing Chen:(1) We constructed the n-1 vertex disjoint paths between any two vertices of AN_n, bounded the length l of these paths, and derived the wide diameter:D(AN_n)+1≤d_n-1(AN_n)≤D(AN_n) + 2. At the same time, the connectivity of AN_n isn-1.(2) It has been half an century since the study of the fault tolerance about the multi-processor system. Many results were obtained about the diagnostic strategy, diagnostic models and diagnostic algorithms. Preparata, Metze and Chien proposed the t-diagnostic and the diagnostic model was called PMC model. Then the compared diagnostic model was proposed by Preparata, Metze and Chien. In this paper, we derived the diagnostic degree of AN_n under the PMC model and compared diagnostic model about the different diagnostic strategies.(3) System level fault diagnosis is proposed following the global diagnosis ability of a system while ignored some local systematic details. It is possible to the the number of all faulty nodes in some part of the system G may be more than t even if the diagnosabity of the system is t. So the local diagnosability states more connection status around it. We study the local diagnosability of alternating group network and the strong diagnosability problems.