Reliability And Fault Diagnosis Of K-ary N-cube

It is well-known that the underlying topology of an interconnection network ismodeled by an undirected connected graph G=(V, E), where V is the set of pro-cessors and E is the set of communication links in the network. The connectivity isan important measurements for fault tolerance and reliability of the interconnectionnetwork In some extent, it can correctly refect the fault tolerance ability of an in-terconnection network with a few fault processors. Nevertheless, it underestimatesthe fault resilience of the large interconnection networks. Thus, in considering theshortcoming of traditional connectivity measure, Boesch and Esfahanian generalizedthe super connectivity by imposing conditions on the set of fault connected compo-nent. Later, base on the super connectivity, the h-extra connectivity is introducedby Fa`brega and Fiol.With the growing number of the processors in a multiprocessor system, someprocessors in such a multiprocessor system may fail. Thus it is crucial to locate thefaulty processors therein efciently. Lai et al. introduced conditional diagnosabilityby restricting that for each processor u in a network, all the processors that aredirectly connected to u are not all faulty at the same time.The k-ary n-cube network is an important interconnection network structure ofparallel computing systems due to its many desirable properties, e.g., when k=2,the network collapses to the well-known hypercube. After studying some propertiesof the k-ary n-cube，this paper obtains that:1) when k=3, the1-extra connectivity and2-extra connectivity are4n3and6n7respectively, under the PMC model and MM*model, the conditionaldiagnosability is8n11and6n7respectively, and the degree of diagnosabilityis4n3under the pessimistic strategy;2) when k≥4, the1-extra connectivity and2-extra connectivity are4n2and6n5respectively, the conditional diagnosability is8n7and6n5underthe PMC model and MM*model respectively, and the degree of diagnosability is4n2under the pessimistic strategy.