Distributed Integrity Checking for Systems with Replicated Data

Roverli P. Ziwich, Elias P. Duarte Jr., Luiz C. P. Albini
The 11th IEEE International Conference on Parallel and Distributed Systems (ICPADS'2005),
pp. 363-369, Fukuoka, Japan, Jul, 2005.  [pdf]  Digital Object Identifier  IEEE Xplore Digital Library

Best Paper AWARD from The IEEE Computer Society


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, detecting unauthorized Web page modifications. Faultfree nodes running Hi-Dif send a task to two other nodes and the task results are 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, we prove that the algorithm has latency equal to log2N testing rounds in the worst case; that the maximum number of tests required is O(N2); and, that the algorithm is (N–1)-diagnosable. Experimental results obtained by simulation and by the execution of a tool implemented applied to the Web are presented.


[1]   CERT Coordination Center, http://www.cert.org, Accessed on 05/09/2004.

[2]   ALDAS, Analytisches Labor Dr. Axel Schumann, http://www.aldas.de, Accessed on 05/10/2003.

[3]   A. Subbiah, and D. M. Blough, “Distributed Diagnosis in Dynamic Fault Environments,” IEEE Trans. on Parallel and Distributed Systems, Vol. 15, No. 5, pp. 453-467, May 2004.

[4]   L. C. P. Albini, and E. P. Duarte Jr., “Generalized Distributed Comparison-Based System-Level Diagnosis,” 2nd IEEE Latin American Test Workshop, pp. 285-290, Sep. 2001.

[5]   D. Ingham, S. K. Shrivastava, and F. Panzieri, “Constructing Dependable Web Services,” IEEE Internet Computing, Vol. 4, No. 1, pp 25-33, Jan/Feb 2000.

[6]   B. Tan, S. Foo, and S. C. Hui, “Monitoring Web Information Using PBD Technique,” Proc. 2nd Intl. Conference on Internet Computing (IC’2001), Las Vegas, USA, pp. 666-672, Jun. 2001.

[7]   Url Minder, http://www.netmind.com/URL-minder/URLminder. html. Accessed on 22/09/2003.

[8]   B. Lu, S. C. Hui, and Y. Zhang, “Personalized Information Monitoring Over the Web,” 1st Intl. Conference on Information Technology & Applications (ICITA 2002), Nov. 2002.

[9]   V. Boyapati, K. Chevrier, A. Finkel, N. Glance, T. Pierce, R. Stockton, and C. Whitmer, “ChangeDetectorTM: A Site- Level Monitoring Tool for the WWW,” Intl. World Wide Web Conference, USA, pp. 570-579, May 2002.

[10] S.-J. Lim, and Y.-K. Ng, “An Automated Changedetection Algorithm for HTML documents Based on Semantic Hierachies,” Proceedings of the 17th Intl. Conference on Data Engineering (ICDE’01), Heidelberg, Germany, pp. 303-312, Apr. 2001.

[11] M. Malek, “A Comparison Connection Assignment for Diagnosis of Multiprocessor Systems,” Proc. 7th Intl. Symp. Computer Architecture, pp. 31-36, 1980.

[12] K. Y. Chwa, and 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.

[13] J. Maeng, and M. Malek, “A Comparison Connection Assignment for Self-Diagnosis of Multiprocessor Systems,” Digest 11th Intl. Symp. Fault Tolerant Computing, pp. 173-175, 1981.

[14] A. Sengupta, and A. T. Dahbura, “On Self-Diagnosable Multiprocessor Systems: Diagnosis by Comparison Approach,” IEEE Trans. on Computers, Vol. 41, No. 11, pp. 1386-1396, 1992.

[15] D. M. Blough, and H. W. Brown, “The Broadcast Comparison Model for On-Line Fault Diagnosis in Multicomputer Systems: Theory and Implementation,” IEEE Trans. on Computers, Vol. 48, pp. 470-493, 1999.

[16] D. Wang, “Diagnosability of Hipercubes and Enhanced Hypercubes under the Comparison Diagnosis Model,” IEEE Trans. on Computers, Vol. 48, No. 12, pp. 1369- 1374, 1999.

[17] T. Araki, and Y. Shibata, “Diagnosability of Butterfly Networks under the Comparison Approach,” IEICE Trans. Fundamentals, Vol. E85-A, No. 5, May 2002.

[18] J. Fan, “Diagnosability of Crossed Cubes,” IEEE Trans. on Computers, Vol. 13, No. 10, pp. 1099-1104, Oct. 2002.

[19] E. P. Duarte Jr., A. Brawerman, and L. C. P. Albini, “An Algorithm for Distributed Hierarquical Diagnosis of Dynamic Fault and Repair Events,” Proc. IEEE Intl. Conference on Parallel and Distributed Systems 2000, pp. 299-306, 2000.