Istituto di Scienza e Tecnologie dell'Informazione     
Caruso A. m., Chessa S., Maestrini P., Santi P. Diagnosability of regular systems. In: Journal of Algorithms, vol. 45 (2) pp. 126 - 143. Elsevier Science Inc, 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σ over the set of all the admissible syndromes. In turn, tσ is determined by evaluating the cardinality of the smallest 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.
Subject System-level diagnosis
PMC model
Isoperimetric inequalities
Sequential diagnosis
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