Uma Nova Estratégia para o Diagnóstico de Falhas Baseado em Comparações

• Roverli Pereira Ziwich UFPR
• Elias Procópio Duarte Jr. UFPR

DOI: https://doi.org/10.5753/wtf.2009.23135

Abstract

Comparison-based diagnosis is based on the comparison of tasks outputs produced by pairs of units. If the comparison results in a mismatch one or both units are faulty. The complete system diagnosis is performed based on the results of all comparisons. This work describes a new strategy to identify faulty units in hardware and software based systems. Previously published comparison-based diagnosis algorithms for general systems involve, at some phase, some technique inherited from traditional diagnosis models and algorithms. The strategy proposed in this work is based on the comparison syndrome alone and does not require any conversion to other models. An outline of the algorithm correctness proof is also presented.

References

H. Wang, D. M. Blough, and L. Alkalaj, “Analysis and Experimental Evaluation of Comparison-Based System-Level Diagnosis for Multiprocessor Systems,” Twenty-Fourth Intl. Symp. on Fault-Tolerant Computing, pp. 55–64, June 1994.

S. Rangarajan, D. Fussell, and M. Malek, “Built-in Testing of Integrated Circuits Wafers,” IEEE Transactions on Computers., vol. 39, pp. 195–205, Feb. 1990.

D. Fussell, M. Malek, and S. Rangarajan, Wafer-Scale Testing/Design for Testability, ch. 9, pp. 413–472. Kluwer, 1989.

F. Preparata, G. Metze, and R. T. Chien, “On the Connection Assignment Problem of Diagnosable Systems,” IEEE Transactions on Computers., vol. 16, pp. 848–854, 1968.

G. Masson, D. Blough, and G. Sullivan, System Diagnosis. Prentice-Hall, 1996.

M. Malek, “A Comparison Connection Assignment for Diagnosis of Multiprocessor Systems,” Proc. 7th International Symp. Computer Architecture, pp. 31–36, 1980.

K. Y. Chwa and S. L. Hakimi, “Schemes for Fault-Tolerant Computing: A Comparison of Modularly Redundant and t-Diagnosable Systems,” Information and Control., vol. 49, pp. 212–238, 1981.

J. Maeng and M. Malek, “A Comparison Connection Assignment for Self-Diagnosis of Multiprocessor Systems,” Digest 11th International Symp. Fault Tolerant Computing, pp. 173–175, 1981.

A. Sengupta and A. T. Dahbura, “On Self-Diagnosable Multiprocessor Systems: Diagnosis by Comparison Approach,” IEEE Transactions on Computers., vol. 41, pp. 1386–1396, Nov. 1992.

X. Yang and Y. Y. Tang, “Efficient Fault Identification of Diagnosable Systems under the Comparison Model,” IEEE Transactions on Computers., vol. 56, pp. 1612–1618, Dec. 2007.

S. Micali and V. V. Vazirani, “An O(√(|V|)|E|) Algorithm for Maximum Matching in General Graphs,” In Proc. 16th Annu. Symp. Foundations of Comput. Science, pp. 17–27, Oct. 1980.

A. T. Dahbura and G. M. Masson, “An O(n^2.5) Fault Identification Algorithm for Diagnosable Systems,” IEEE Transactions on Computers., vol. C-33, pp. 486–492, June 1984.

G. Sullivan, “An O(t³ + |E|) Fault Identification Algorithm for Diagnosable Systems,” IEEE Transactions on Computers., vol. 37, pp. 388–397, Apr. 1988.