Document - Worst-case diagnosis completeness in regular graphs under the PMC model

2007

Journal article Open Access

Worst-case diagnosis completeness in regular graphs under the PMC model

Caruso A, Chessa S, Maestrini P

system-level diagnosi isoperimeter Hardware and Architecture parallel architecture Parallel architectures fault diagnosi Fault diagnosis Computational Theory and Mathematics Fault tolerance System-level diagnosis Graph Theory Theoretical Computer Science B.8 Performance and Reliability Software

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

Source: I.E.E.E. TRANSACTIONS ON COMPUTERS (PRINT), vol. 56 (issue 7), pp. 917-924

Metrics

Back to previous page

Cite as

BibTeX entry

@article{oai:it.cnr:prodotti:44031,
	title = {Worst-case diagnosis completeness in regular graphs under the PMC model},
	author = {Caruso A and Chessa S and Maestrini P},
	doi = {10.1109/tc.2007.1052},
	year = {2007}
}