Diagnosabilities of hypercubes under the pessimistic one-step diagnosis strategy

The capabilities of a system-diagnosis technique based on mutual testing are discussed. The technique is applied to hypercube computer systems. A one-step diagnosis of hypercubes that involves only one testing phase, in which processors test each other, is described. Two kinds of one-step diagnosis are presented: the precise one-step diagnosis and the pessimistic one-step diagnosis. Results indicate that the degree of diagnosability of the n-dimensional hypercube (for short, n-cube), where n⩾4, increases from n to 2n-2 as the diagnosis strategy changes from the precise one-step strategy to the pessimistic one-step diagnosis strategy. If the fault bound, the upper bound on the possible number of faulty processors, is kept to the same number n in both cases of diagnosis, then the pessimistic strategy requires fewer testing links per processor than the precise strategy. An algorithm for selecting the bidirectional links in an n-cube for use as testing links is also presented