Um Algoritmo Distribuído para Detecção e Localização de Falhas em Redes tipo Hipercubo

• Saulo Rodrigues do Nascimento UNICAMP
• Marco Aurélio Amaral Henriques UNICAMP

DOI: https://doi.org/10.5753/sbac-pad.1999.19782

Resumo

Este trabalho propõe um algoritmo distribuído para detecção e localização de enlaces e nós falhos em redes tipo hipercubo quando estes, em conjunto, não excedem (n-1), sendo n a dimensão do hipercubo. Tal algoritmo é executado de forma paralela em todos os nós não-falhos, utilizando trocas de mensagens entre vizinhos. Cada nó do hipercubo mantém em memória informação das condições de falha de sua vizinhança. São necessários três estágios de trocas de mensagens entre vizinhos para que todos os nós se informem da presença ou não de algum enlace ou nó vizinho defeituoso. O custo total da operação é da ordem de O(n²). A eficiência e a correção do algoritmo foram verificados através de diversos testes realizados em hipercubos de 8 a 64 nós nos quais falhas foram geradas aleatoriamente.

Palavras-chave: Tolerância a falhas, hipercubo, detecção de falhas, redes de interconexão, diagnóstico, multiprocessadores, multicomputadores, algoritmos distribuídos

Referências

Lee, Tze Chiang; Hayes, John P. A Fault-Tolerant Communication Scheme for Hypercubes Computers. IEEE Transactions on Computers, Vol. 41 , No. 10, Oct. 1992.

Bruck, Jehoshua. An Optimal Broadcasting in Faulty Hypercubes. Discrete Applied Mathematics 53, 3-13. 1994.

Wu, Jie. Unicasting in Faulty Hypercubes Using Safety Levels. IEEE Transactions on Computers, Vol. 46, No. 2, pp. 241-247, Feb. 1995.

Wu, Jie. Safery-Levels - An Efficient Mechanism for Achieving Reliable Broadcasting in Hypercubes. IEEE Transactions on Computers, Vol. 44, No. 5, May 1995.

Leu, Yuh-Rong; Kuo, Sy-Yen. A fault Tolerant Tree Communication Scheme for Hypercube Systems. IEEE Transactions on Computers, Vol. 45, No. 6, Jun. 1996.

Wu, Jie. Optimal Broadcasting in Hypercubes with Link Faults Using Limited Global Information. Journal of Systems Architecture 42, 367-380, 1996.

Armstrong, J. R.; Gray, F. G. Fault Diagnosis in a Boolean n-Cube Array of Microprocessors. IEEE Transactions on Computers, Vol. C-30, No. 8, Aug. 1981.

Chcn, Hsing-Lung; Tzcng, Nian-Feng. Subcube Determination in Faulry Hypercubes. IEEE Transactions on Computers, Vol. 46, No. 8, Aug. 1997.

Rennels, D. A. On Implementing Fault-Tolerance in Binary Hypercubes. Proc. 16'h Int'l Symp. FaultTolerant Computing, pp. 344-349, Jul. 1996.

Huerta, Eduardo J. ; Henriques, Marco A. A. Uma Introdução a JOIN: Um Sistema para o Processamento Massivamente Paralelo na Internet. Relatório Técnico DCA-RT 02198, FEEC/UNICAMP, Mar. 1998.

NCUBE Corporation, n-Cube-2 Processor Manual. NCUBE Corporation, 1990.

Hillis, W. D. The Connection Machine. Cambridge, Mass.: MIT Press, 1985.

Banerjee, Prithviraj; Rahmeh, Joe T.; Stunkel, Craig; Nair, V. S., Roy, Kaushik; Balasubramanian, Vilay; Abraham, Jacob A. Algorithm-Based Fault Tolerance on a Hypercube Multiprocessor. IEEE Transactions on Computers, Vol. 39, No. 9, Sep. 1990.

Kuhl, J. G.; Reddy, S. M. Fault Diagnosis in Fully Distributed Systems. Proc. 11th Int'l Symp. Fault-Tolerant Computing, pp. 100-105, Jun. 1981.

Dilger, E.; Ammann, E. System Level Self-Diagnosis in n-Cube Connected Multiprocessor Networks. Proc. 14th Int'l Symp. Fault-Tolerant Computing, Kissimmee, FL, pp. 184-189, Jun. 1984.

Iyer, R. K.; Rossetti, D. J. Pennanent CPU Errors and System Activity: Measurement and Modeling. Proc. Real-Time Syst. Symp., 1983.

Rennels, D. A. Fault Tolerant Computing - Concepts and Examples. IEEE Transactions on Computers, Vol. C-33, pp. 1116-1129, Dec. 1984.