The Diagnosability And The Strong Local Diagnosability Of K-ary N-cubes With Missing Edges

In many fields of science and engineering computing,large-scale computation is needed,which is far beyond the computing power of microprocessors.Therefore,massively parallel computer system emerges as the times require and becomes the mainstream of high-performance computing.With the increasing of the scale of massively parallel computer system,there are more and more processors and physical connections in the system,which leads to the inevitable failure of processors and physical connections.In order to maintain the reliability of the parallel computer system,the faulty vertices in the system should be identified and replaced in a timely manner.The maximum number of fault processors that the system can identify itself is called the diagnosability of the system.It is an important parameter to measure the fault diagnosis ability of computer system.Due to the good topological properties,k-ary n-cubes have been used as the interconnection network topologies in many multiprocessor computer systems.At present,most of the researches on the fault diagnosis of k-ary n-cubes only consider the cases that the vertices fail to work,that is,there exists no edge faults in k-ary n-cubes.However,in practice,edge faults often occurs in k-ary n-cubes.Therefore,we discuss the diagnosability and strong local diagnosability of k-ary n-cubes with missing edges in this paper.First,we investigate the diagnosability of k-ary n-cubes with missing edges under the PMC model and BGM model,and obtain that:(1)The diagnosability of k-ary n-cubes G with missing edges under PMC model equals its minimum degree δ(G)when n≥3,δ(G)≥5;(2)The diagnosability of the k-ary n-cubes G with missing edges under PMC model equals its minimum degree δ(G)when n ≥ 2,k≥ 4,δ(G)≥ 3;(3)The diagnosability of the k-ary n-cubes G with missing edges under BGM model equals its minimum degree δ(G)when n≥2,k≥3,δ(G)≥3.Second,we study the strong local diagnosability of k-ary n-cubes with a missing edge in the PMC model.Let G be a k-ary n-cubes with missing edges.By discussing the relationship between the residual degree of vertex and the number of missing edges in k-ary n-cubes,we get three conclusions as follows:(1)when the number of missing edges of G is not more than 2n-3,the local diagnosability of every vertex equals its residual degree;(2)when the number of missing edges of G is not more than 7(2n-3)and the minimum degree of G is not less than 3,the local diagnosability of every vertex equals its residual degree;(3)when the minimum degree of G is greater than 3,the local diagnosability of every vertex equals its residual degree.