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

Roverli P. Ziwich, Elias P. Duarte Jr.
10° Workshop de Testes e Tolerância a Falhas (WTF'2009), pp. 76-89,
João Pessoa, PB, Brazil, Proc. of the WFT/LADC'2009, Aug, 2009.  [pdf]



Resumo

O diagnóstico baseado em comparações determina o estado das unidades do sistema a partir da comparação do resultados de tarefas produzidos por pares de unidades. Qualquer diferença na comparação indica que uma ou ambas as unidades estão falhas. O diagnóstico completo do sistema é baseado no resultado de todas as comparações. Este trabalho descreve uma nova solução para a identificação de unidades falhas em sistemas complexos. Estes sistemas são dos mais diversos tipos, incluindo hardware, software, além de redes de interconexão de computadores e processadores. Os algoritmos existentes para a realização do diagnóstico baseado em comparações em sistemas gerais envolvem, em alguma fase, técnicas de diagnóstico tradicional. A estratégia proposta neste trabalho resolve o diagnóstico utilizando exclusivamente a síndrome de comparações, sem necessidade de convertê-la para outro modelo. Um esboço da prova de corretude do algoritmo proposto também é apresentado.


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.


Referências

[1]   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.

[2]   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.

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

[4]   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.

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

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

[7]   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.

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

[9]   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.

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

[11] 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.

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

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