Conditional diagnosability of a class of matching composition networks under the comparison model

Fault diagnosis of interconnection networks is an important consideration in the design and maintenance of multiprocessor systems. Herein, we study fault diagnosis, which is the identification of faulty processors in high speed parallel processing systems. Conditional diagnosability, proposed by Lai et al. [22], assumes that no fault set can contain all the neighbors of any processor in a system; this is a well-accepted and general measure of the diagnosis ability of an interconnection network of multiprocessor systems. The diagnosability and conditional diagnosability of many interconnection networks have been studied using various diagnosis models. In this paper we study the conditional diagnosability of matching composition networks under the comparison model (MM* model). In [31] Yang determined a set of sufficient conditions for a network G to be conditionally (3n−3−C(G))-diagnosable. Our main contribution in this paper is to extend Yang's result by determining a larger class of networks that are conditionally (3n−3−C(G))-diagnosable. Yang's result [31] and earlier results for the hypercube, the crossed cube, the twisted cube and the Möbius cube [18,32,33] all become corollaries of our main result. Thus this paper extends the state of the art in the area of conditional diagnosability of multiprocessor systems.