Uma estratégia de testes isócrona para diagnóstico hierárquico distribuído

Abstract

Resumo: Diagnóstico em nível de sistema permite que todos os componentes de um sistema distribuído tolerante a falhas determinem quais outros componentes estão falhos e quais estão sem-falha. O período de tempo no qual os nodos que executam um determinado algoritmo de diagnóstico levam para completar o diagnóstico de todo o sistema é chamado de latência do algoritmo. Este trabalho apresenta um novo algoritmo distribuído para diagnóstico em nível de sistemas, o qual possui uma latência, no pior caso de O(logN) rodadas de testes para sistemas de N nodos. Algoritmos de diagnóstico hierárquico distribuído apresentados anteriormente, tais como Hi-ADSD e Hi-ADSD with Detours, possuem uma latência no pior caso, de O(log2N) rodadas de testes. O novo algoritmo, Iso Hi-ADSD, é baseado no algoritmo Hi-ADSD, agrupando os nodos em clusters para propósito de testes. Entretanto, o novo algoritmo emprega uma estratégia de testes isócrona na qual todos os nodos sem-falha executam testes em clusters de mesmo tamanho a, cada rodada de testes. Esta estratégia é baseada em dois princípios: um nodo testado deve testar o cluster de seu testador na mesma rodada de testes; um nodo somente aceita testes de acordo com uma prioridade de ordem léxica. Assume-se que uma rodada, de testes é grande o suficiente para um nodo sem-falha testar e determinar o estado de até N/2 nodos. Todos os nodos sem-falha conhecem o início de cada rodada de testes. Provas formais do processo de tornar os testes isócronos e do pior caso da latência são apresentadas. São apresentados também resultados experimentais obtidos através de simulação.

Abstract: System-level diagnosis allows the components of a fault-tolerant distributed system to determine which components of the system are faulty and which are fault-free. The time it takes for nodes running the algorithm to diagnose a new event is called the algorithm's latency. This work introduces a new distributed system-level diagnosis algorithm which presents a worst-case latency of O(logN) testing rounds, for a system of N nodes. Some previous hierarchical distributed system-level diagnosis algorithms, Hi-ADSD and Hi-ADSD with Detours, presented a worst-case latency of O(log2N) testing rounds. The new algorithm is based on Hi-ADSD, grouping nodes in progressively larger logical clusters for the purpose of testing. However, the new algorithm employs an isochronous testing strategy in which all fault-free nodes execute tests on clusters of the same size each testing round. This strategy is based on two main principles: a tested node must test its tester in the same testing round; a node only accepts tests according to a lexical priority order. It is assumed that a testing round is large enough for a fault-free node to test and determine the state of up to N/2 nodes. Furthermore, all fault free nodes know the beginning of a testing round. Formal proofs showing the process of tests becoming isochronous and the worst-case latency, are presented. Experimental results are also show through simulation.