Uma Estratégia de Testes Logarítmica para o Algoritmo Hi-ADSD
Resumo
O algoritmo Hierarchical Adaptive Distributed System-level Diagnosis (Hi-ADSD) é um algoritmo de diagnóstico distribuído que cria uma topologia virtual baseada em um hipercubo. O hipercubo é uma estrutura escalável por definição, apresentando características topológicas importantes como: simetria, diâmetro logarítmico e boas propriedades para tolerância a falhas. A latência do algoritmo quando executado em um sistema com N nodos é de no máximo log2^2 N rodadas de teste. Entretanto, o número de testes executados no pior caso é quadrático. Este trabalho apresenta uma nova estratégia de testes para o algoritmo Hi-ADSD que garante que são executados no máximo N log2 N testes a cada log2 N rodadas. A latência máxima é mantida em log2^2 N rodadas de teste. O algoritmo é adaptado para a nova estratégia de testes. Além disso, foi adotado o uso de timestamps para permitir que cada nodo obtenha informações de diagnóstico a partir de diversos outros nodos, consequentemente reduzindo a latência média. O novo algoritmo é especificado, suas provas formais são demonstradas e resultados experimentais obtidos por simulações são apresentados e comparados com o Hi-ADSD.
Referências
Duarte Jr., E., Ziwich, R., and Albini, L. (2011). A survey of comparison-based system-level diagnosis. ACM Computing Surveys.
Duarte Jr., E. P., Albini, L., Brawerman, A., and Guedes, A. (2009). A hierarquical distributed fault diagnosis algorithm based on clusters with detours. In Network Operations and Management Symposium, 2009. LANOMS 2009. Latin American, pages 1–6.
Duarte Jr., E. P. and Nanya, T. (1998). A Hierarquical Adaptive Distributed System-Level Diagnosis Algotithm. IEEE Transactions on Computers., 47(1):34–45.
Hakimi, S. L. and Nakajima, K. (1984). On Adaptive System Diagnosis. IEEE Transactions on Computers., C-33(3):234–240.
Hosseini, S. H., Kuhl, J. G., and Reddy, S. M. (1984). A Diagnosis Algorithm for Distributed Computing Systems with Dynamic Failure and Repair. IEEE Transactions on Computers., C-33(3):223–233.
LaForge, L., Korver, K., and Fadali, M. (2003). What designers of bus and network architectures should know about hypercubes. Computers, IEEE Transactions on, 52(4):525–544.
MacDougall, M. (1987). Simulating computer systems: techniques and tools. MIT Press, Cambridge, MA, USA.
Masson, G., Blough, D., and Sullivan, G. (1996). Fault-tolerant computer system design. chapter System diagnosis, pages 478–536. Prentice-Hall, Inc., Upper Saddle River, NJ, USA.
Preparata, F., Metze, G., and Chien, R. T. (1967). On the Connection Assignment Problem of Diagnosable Systems. IEEE Transactions on Computers., 16:848–854.
