The G-conditional Diagnosability Of Hypercubes

Interconnection network is the connection mode between processors in massively parallel computer system,which can be represented by a simple undirected connected graph.The vertices in the graph represent the processors of the system,and the edges represent the connections between the processors in the system.Based on topology,hypercubes has become one of the most popular interconnection networks because of its excellent topological properties.The uninterrupted high-speed operation and the increase of the number of processors in the computer system greatly increase the probability of the failure of the system.In order to ensure the normal operation of the system,the fault elements have to be diagnosed and replaced.The diagnosability is a important parameters that measuring the self-diagnostic ability of the system.The traditional diagnosability allows the adjacent points of each node to fail at the same time,which is almost impossible in practical applications.In order to improve the defect of traditional diagnosability,Lai and other restricted the adjacent points of each node in the system have at least one non-fault,and a conditional diagnosability is proposed.Further,we propose g-conditional diagnosability,which means that the maximum number of faults that the system can diagnose at one time when the adjacent points of each node in the system have at least g non-fault.It is easy to see,when g=1,the g-conditional diagnosability is conditional diagnosability.What the article studies is g-conditional diagnosability of g=2,that is,2-conditional diagnosability.Conditional t-diagnosable refers to the case where the adjacent points of each node has at least one non-fault,as long as the number of faults does not exceed t,the system can diagnose all the fault elements,that is,t is the upper bound of the conditional diagnosability.In this paper,we study the 2-conditional diagnosability of hypercubes Q_n under the PMC model and obtained that when n≥ 7,any two 2-conditional failure sets F₁ and F₂ in hypercubes satisfact F₁ ∩F₂ is a 4-good-neighbor cut,the 2-conditional diagnosability of hypercubes Q_n is 16n-57 under PMC model;removing the conditions added above,we also show that when n≥61,the 2-conditional diagnosability of hypercubes Q_n is 16n-57 under PMC model.Secondly,we also study the 2-conditional diagnosability of hypercubes Q_n under the MM*model and obtained that when n≥ 7,any two 2-conditional failure sets F₁ and F₂ in hypercubes Q_n satisfact F₁∩F₂ is a 4-good-neighbor cut,the 2-conditional diagnosability of hypercubes Q_n is 16n-57 under MM*model;removing the conditions added above,we also show that when n≥61,the 2-conditional diagnosability of hypercubes Q_n is 16n-57 under MM*model.Finally,the conditional t-diagnosable of hypercubes G with fault edge under PMC model is studied in this paper.that is,the upper bound of conditional diagnosability.We obtain that hypercubes G with fault edges of the minimum degree is r,press that G0i and G1i is a subset of the ith-dimensional decomposition,Z is any one subgraph of not isomorphic with K1,k-1 and order is at least 4 and N（Z）is the conditional failure set,where r≥7.Ifδ（Z ∩G0i）>1,×（Z ∩G1l）≥ 1,G is conditional t-diagnosable under the PMC model.