A (4n − 9)/3 diagnosis algorithm for generalised cube networks

Abstract

The goal of the t/k-diagnosis is to isolate all faulty processors (nodes) in a multiprocessor system to within a set of nodes in which at most k nodes are correct, provided the number of faulty nodes does not exceed t. As compared to the classical precise diagnosis strategy, the t/k-diagnosis strategy can significantly improve the self-diagnosing capability of multiprocessor system. The generalised cube network (GCN), or equivalently the BC graphs, is a regular topology, which provides a unified view of the hypercube and some of its variants. This paper addressed the t/k-diagnosis of GCNs. By exploring the relationship between the size of a largest connected component of the 0-test subgraph of a faulty GCN and the distribution of the faulty nodes over the network, an time (4n − 9)/3 diagnosis algorithm on an n-dimensional GCN is presented, where N = 2 ⁿ is the total number of the nodes of the network being diagnosed. To our knowledge, this is the first time to give a t/k-diagnosis algorithm for GCNs and .

Keywords:

• multiprocessor system
• system-level diagnosis
• t/k-diagnosis
• diagnosis algorithm
• generalised cube network