This work presents a new comparison-based diagnosis model and a new algorithm, called Hi-Dif, based on this model. The algorithm is used for checking the integrity of systems with replicated data, for instance, unauthorized Web page modifications. Fault-free nodes running Hi-Dif send a test to two other nodes and the test results are compared. Based on task results, tested nodes are classified in sets. 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 task results. One of the sets always contains all fault-free nodes. One fundamental difference of the proposed model to previously published models is that the new 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; that the maximun number of tests required is O(N2) in the worst case; and, that the algorithm is (N-1)-diagnosable. Experimental results obtained by simulation and by the implementation of the algorithm applied to the Web are presented.
http://www.lbd.dcc.ufmg.br/colecoes/sbseg/2005/003.pdfCaso o link acima esteja inválido, faça uma busca pelo texto completo na Web: Buscar na Web