The g-extra conditional diagnosability and sequential t/k-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(\ge 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.

Keywords:

• system-level diagnosis
• conditional diagnosability
• fault tolerance
• diagnosis algorithms
• hypercubes

AMS Subject Classification:

• 68M15

Acknowledgments

The authors would like to thank the anonymous reviewers for their helpful comments that improve the quality of this paper.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by the Qualified Personnel Foundation (tyut-rc201388a) and the Research Team Foundation (2014TD046) of Taiyuan University of Technology.