PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Caruso A., Chessa S., Maestrini P. Worst-case diagnosis completeness in regular graphs under the PMC model. In: Ieee Transactions on Computers, vol. 56 (7) pp. 917 - 924. IEEE, 2007.
 
 
Abstract
(English)
System-level diagnosis aims at the identification of faulty units in a system by the analysis of the system syndrome, that is, the outcomes of a set of interunit tests. For any given syndrome, it is possible to produce a correct (although possibly incomplete) diagnosis of the system if the number of faults is below a syndrome-dependent bound and the degree of diagnosis completeness, that is, the number of correctly diagnosed units, is also dependent on the actual syndrome . The worst-case diagnosis completeness is a syndrome-independent bound that represents the minimum number of units that the diagnosis algorithm correctly diagnoses for any syndrome. This paper provides a lower bound to the worst-case diagnosis completeness for regular graphs for which vertexisoperimetric inequalities are known and it shows how this bound can be applied to toroidal grids. These results prove a previous hypothesis about the influence of two topological parameters of the diagnostic graph, that is, the bisection width and the diameter, on the degree of diagnosis completeness
DOI: 10.1109/TC.2007.1052
Subject Fault tolerance
Fault diagnosis
System-level diagnosis
Parallel architectures
Graph Theory
Isoperimeter
B.8 PERFORMANCE AND RELIABILITY


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