Uma Nova Estratégia para o Diagnóstico de Falhas Baseado em Comparações
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.
Referências
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(n2.5) Fault Identification Algorithm for Diagnosable Systems,” IEEE Transactions on Computers., vol. C-33, pp. 486–492, June 1984.
G. Sullivan, “An O(t3 + |E|) Fault Identification Algorithm for Diagnosable Systems,” IEEE Transactions on Computers., vol. 37, pp. 388–397, Apr. 1988.
