Detecção distribuída de alterações em sistemas com conteúdo replicado utilizando diagnóstico baseado em comparações
Resumo
Resumo: Este trabalho apresenta um novo modelo genérico de diagnóstico hierárquico adaptativo distribuído e baseado em comparações e um novo algoritmo, chamado Hi-Dif, que se baseia neste modelo. O algoritmo permite a detecção de alterações em sistemas com conteúdo replicado distribuído em uma rede como, por exemplo, a Internet. Um nodo sem-falha executando o algoritmo Hi-Dif, testa outro nodo do sistema para classificar seu estado. O modelo classifica os nodos do sistema em conjuntos de acordo com o resultado dos testes. Um teste é realizado através do envio de uma tarefa para um par de nodos do sistema. Após o recebimento das duas saídas da execução destas tarefas, o testador compara estas saídas e, se a comparação indicar igualdade, os nodos são classificados no mesmo conjunto. Por outro lado, se a comparação das saídas indicar diferença, os nodos são classificados em conjuntos distintos, de acordo com o resultado da tarefa. Um dos conjuntos contém os nodos sem-falha do sistema. Uma diferença fundamental do modelo proposto para outros modelos publicados anteriormente é que a comparação por um nodo sem-falha, sobre as saídas produzidas por dois nodos falhos, pode resultar em igualdade. Considerando um sistema com N nodos, prova-se que o algoritmo Hi-Dif possui latência igual a log2N rodadas de testes; o número máximo de testes requeridos pelo algoritmo é de O(N2) no pior caso; e, que o algoritmo é (N–1)-diagnosticável. Resultados experimentais obtidos através de simulações e através de implementação do algoritmo aplicado à Web são apresentados. Abstract: This work presents a new comparison-based distributed system-level diagnosis generic model and a new algorithm, called Hi-Dif, based on this model. The algorithm allows the detection of modifications in systems with replicated data distributed on networks like the Internet. Fault-free nodes running Hi-Dif, execute tests on other nodes. Based on test results tested nodes are classified in sets. A test consists of a task that is sent to two system nodes. After the tasks are executed, the task outputs is sent back to the tester. The outputs are then compared; if the comparison produces a match, the two nodes are classified in the same set. On the other hand, if the comparison results in a mismatch, the two nodes are classified in different sets, according to their tasks results. One of the sets always contain all fault-free nodes. One fundamental difference of the proposed model to previously published models is that this model allows the task outputs of two faulty nodes to be equal to each other. Considering a system of N nodes, it is proved that the algorithm has latency equal to log2N testing rounds; the maximun number of tests required for the algorithm is O(N2) in the worst case; and, the algorithm is (N–1)-diagnosable. Experimental results obtained by simulation and by the implementation of the algorithm applied to the Web are presented.
Collections
- Teses & Dissertações [10146]