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 |

1) Download Document PDF |

Open access Restricted Private