The<i>g</i>-extra conditional diagnosability and sequential<i>t/k</i>-diagnosability of hypercubes

Abstract

The conditional diagnosis is a very important measure of the reliability and the fault-tolerance of networks. The ‘condition’ means that no faulty set contains all neighbours of any node. Under this assumption, for any system G, every component of G−F has more than 1 node, where F is the faulty set of G. The g-extra conditional diagnosability is defined under the assumption that every component of G−F has more than g (≥1) nodes. ‘A system with at most t faulty nodes is defined as sequentially t-diagnosable if at least one faulty node can be repaired, so that the testing can be continued using the repaired node to eventually diagnose all faulty nodes’ [E.P. Duarte Jr., R.P. Ziwich, and L.C.P. Albini, A survey of comparison-based system-level diagnosis, ACM Comput. Surv. 43(3) (2011), article 22]. To increase the degree of the sequential t-diagnosability of a system, sequential t/k-diagnosis strategy is proposed in this paper. It is allowed that there are at most k misdiagnosed nodes. In this paper, we determine the g-extra conditional diagnosability of hypercubes and propose sequential t/k-diagnosis algorithms for hypercubes with low time complexities under the Preparata, Metze, and Chien (PMC) model and the MM* model which is a special case of the Maeng and Malek (MM) model.