The (t, k)-Diagnosability of Balanced Hypercube under the PMC Model

摘要

The network's diagnosability implies its self-diagnostic capability. Compared with classical sequential diagnosis that has been widely used to identify faulty nodes, the (t,k)-diagnosis is considered as an improvement of sequential diagnosis, where t ≥ k. To be more specific, the (t, k)-diagnosis can identify and replace at least k faulty nodes in each iteration until all t faulty nodes are found. Meanwhile, compared with the other hypercube graphs, the balanced hypercube (denoted BH_n) has many good properties, such as a better fault-tolerant embedding capability and a smaller diameter. In this paper, we first propose a body discover algorithm (named BD) of BH_n, where a body consists of node sets that meet specific conditions. Based on bodies found by BD, we verify that the BH_n is (t, k)-diagnosable. Then we prove that the (t,k)-diagnosability of BH_n is (2~(n-1),2n) under the PMC model.