pp. 124-137, Florianópolis, SC, Brazil, Sep, 2005. [pdf]
Este trabalho apresenta um novo modelo de diagnóstico baseado em comparações e um novo algoritmo, chamado Hi-Dif para a detecção de alterações em sistemas com conteúdo replicado. 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. 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; que 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.
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.
[1] CERT Coordination Center, http://www.cert.org, Acessado em 05/09/2004.
[2] ALDAS, Analytisches Labor Dr. Axel Schumann, http://www.aldas.de, Acessado em 05/10/2003.
[3] S. Garfinkel, G. Spafford, e A. Schwartz, Practical Unix & Internet Security, O'Reilly, 3a. ed., Fev. 2003.
[4] A. Subbiah, D. M. Blough, “Distributed Diagnosis in Dynamic Fault Environments,” IEEE Transaction on Parallel and Distributed Systems, Vol 15, No. 5, pp. 453-467, Mai. 2004.
[5] L. C. P. Albini, E. P. Duarte Jr., “Generalized Distributed Comparison-Based System-Level Diagnosis,” 2nd IEEE Latin American Test Workshop, pp. 285-290, Set. 2001.
[6] D. Ingham, S. K. Shrivastava, F. Panzieri, “Constructing Dependable Web Services,” IEEE Internet Computing, Vol 4, No. 1, pp 25-33, Jan/Fev 2000.
[7] B. Tan, S. Foo, S. C. Hui, “Monitoring Web Information Using PBD Technique,” Proc. 2nd International Conference on Internet Computing (IC’2001), Las Vegas, USA, pp. 666-672, Jun. 2001.
[8] Url Minder, http://www.netmind.com/URL-minder/URL-minder.html. Acessado em 22/09/2003.
[9] B. Lu, S. C. Hui, Y. Zhang, “Personalized Information Monitoring Over the Web,” 1st International Conference on Information Technology & Applications (ICITA 2002), Nov. 2002.
[10] V. Boyapati, K. Chevrier, A. Finkel, N. Glance, T. Pierce, R. Stockton, C. Whitmer, “ChangeDetectorTM: A Site-Level Monitoring Tool for the WWW,” International World Wide Web Conference, Hawaii, USA, pp. 570-579, Mai. 2002.
[11] S.-J. Lim, Y.-K. Ng, “An Automated Change-detection Algorithm for HTML documents Based on Semantic Hierachies,” Proceedings of the 17th International Conference on Data Engineering (ICDE’01), Heidelberg, Alemanha, pp. 303-312, Abr. 2001.
[12] M. Malek, “A Comparison Connection Assignment for Diagnosis of Multiprocessor Systems,” Proc. 7th International Symp. Computer Architecture, pp. 31-36, 1980.
[13] K. Y. Chwa, S. L. Hakimi, “Schemes for Fault-Tolerant Computing: A Comparison of Modularly Redundant and t-Diagnosable Systems,” Information and Control, Vol. 49, pp. 212-238, 1981.
[14] J. Maeng, M. Malek, “A Comparison Connection Assignment for Self-Diagnosis of Multiprocessor Systems,” Digest 11th Internationall Symp. Fault Tolerant Computing, pp. 173-175, 1981.
[15] A. Sengupta, A. T. Dahbura, “On Self-Diagnosable Multiprocessor Systems: Diagnosis by Comparison Approach,” IEEE Transactions on Computers, Vol. 41, No. 11, pp. 1386- 1396, 1992.
[16] D. M. Blough, H. W. Brown, “The Broadcast Comparison Model for On-Line Fault Diagnosis in Multicomputer Systems: Theory and Implementation,” IEEE Transactions on Computers, Vol. 48, pp. 470-493, 1999.
[17] D. Wang, “Diagnosability of Hipercubes and Enhanced Hypercubes under the Comparison Diagnosis Model,” IEEE Transactions on Computers, Vol. 48, No. 12, pp. 1369-1374, 1999.
[18] T. Araki, Y. Shibata, “Diagnosability of Butterfly Networks under the Comparison Approach,” IEICE Trans. Fundamentals, Vol E85-A, No. 5, Mai. 2002.
[19] J. Fan, “Diagnosability of Crossed Cubes,” IEEE Transactions on Computers, Vol. 13, No. 10, pp. 1099-1104, Out. 2002.
[20] E. P. Duarte Jr., A. Brawerman, L. C. P. Albini, “An Algorithm for Distributed Hierarquical Diagnosis of Dynamic Fault and Repair Events,” Proc. IEEE International Conference on Parallel and Distributed Systems 2000, pp. 299-306, 2000.