On the Diagnosability of Regular Systems

A novel approach aimed at evaluating the diagnosability of regular systems under the PMC model is introduced. The diagnosability is defined as the ability to provide a correct diagnosis, although possibly incomplete. This concept is somehow intermediate between one-step diagnosability and sequential diagnosability. A lower bound to diagnosability is determined by lower bounding the minimum of a ''syndrome-dependent'' bound $t_\sigma$ over the set of all the admissible syndromes. In turn, $t_\sigma$ is determined by evaluating the cardinality of the smal\-lest consistent fault set containing an aggregate of maximum cardinality. The new approach, which applies to any regular system, relies on the ''edge-isoperimetric inequalities'' of connected components of units declaring each other non-faulty. This approach has been used to derive tight lower bounds to the diagnosability of toroidal grids and hypercubes, which improve the existing bounds for the same structures.