Istituto di Informatica e Telematica     
Santi P. On the Diagnosability of Regular Systems. In: JOURNAL OF ALGORITHMS (03629J0), vol. 45 (2) pp. 126 - 143. Elsevier, 2002.
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.
DOI: 10.1016/S0196-6774(02)00250-X
Subject System-level diagnosis, PMC model, Isoperimetric inequalities, Sequential diagnosis, Diagnosability, Regular systems

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional