Um algoritmo de diagnóstico distribuído para redes particionáveis de topologia arbitrária

Este trabalho apresenta um novo algoritmo de diagnóstico distribuído em nível de sistema, Distributed Network Reachability (DNR). O algoritmo permite que cada nodo de uma rede particionável de topologia arbitrária determine quais porções da rede estão alcançáveis e inalcançáveis. DNR é o primeiro algoritmo de diagnóstico distribuído que permite a ocorrência de eventos dinâmicos de falha e recuperação de nodos e enlaces, inclusive com partições e healings da rede. O estado diagnosticado de um nodo é ou sem-falha ou inatingível; o estado diagnosticado de um enlace é ou sem-falha ou não-respondendo ou inatingível. O algoritmo consiste de três fases: teste, disseminação e cálculo de alcançabilidade. Durante a fase de testes cada enlace é testado por um de seus nodos adjacentes em intervalos de teste alternados. Após a detecção de um novo evento, o testador inicia a fase de disseminação, na qual a nova informação de diagnóstico é transmitida para os nodos alcançáveis. A cada vez que um novo evento é detectado ou informado, a terceira fase é executada, na qual um algoritmo de conectividade em grafos é empregado para calcular a alcançabilidade da rede. O algoritmo DNR utiliza o número mínimo de testes por enlace por rodada de testes e tem a menor latência possível de diagnóstico, assegurada pela disseminação paralela de eventos. A correção do algoritmo é provada formalmente. Uma prova de correção no arcabouço bounded correctness também foi elaborada, incluindo latência delimitada de diagnóstico, latência delimitada de inicialização e acuidade. Um simulador do algoritmo foi implementado. Experimentos foram executados em diversas topologias incluindo grafos aleatórios (k-vertex connected e Power-Law) bem como grafos regulares (meshes e hipercubos). Extensivos resultados de simulação de eventos dinâmicos de falha e recuperação em nodos e enlaces são apresentados.This thesis introduces the new Distributed Network Reachability (DNR) algorithm, a distributed system-level diagnosis algorithm that allows every node of a partitionable general topology network to determine which portions of the network are reachable and unreachable. DNR is the first distributed diagnosis algorithm that works in the presence of network partitions and healings caused by dynamic fault and repair events. A node is diagnosed as either working or unreachable and a link is diagnosed either as working or unresponsive or unreachable. The algorithm is formally specified and consists of three phases: test, dissemination, and reachability computation. During the testing phase each link is tested by one of the adjacent nodes at alternating testing intervals. Upon the detection of a new event, the tester starts the dissemination phase, in which the new diagnostic information is received by every reachable node in the network. New events can occur before the dissemination completes. After a new event is detected or informed, a working node runs the third phase, in which a graph connectivity algorithm is employed to compute the network reachability. The algorithm employs the optimal number of tests per link per testing interval and the best possible diagnosis latency, assured by the parallel dissemination of event information. The correctness of the algorithm is proved, including the bounded diagnostic latency, bounded start-up and accuracy. Experimental results obtained from simulation are presented. Simulated topologies include random graphs (k-vertex connected and Power-Law) as well as regular graphs (meshes and hypercubes). Extensive simulation results of dynamic fault and repair events on nodes and links are presented