A Survey of Comparison-Based
System-Level Diagnosis

Elias P. Duarte Jr., Roverli P. Ziwich, Luiz C. P. Albini
ACM Computing Surveys, ISSN 0360-0300, Vol. 43, Issue 3,
pp. 22:1-22:56, Apr, 2011.  [pdf]  Digital Object Identifier  ACM Digital Library





Abstract

The growing complexity and dependability requirements of hardware, software and networks demand efficient techniques for discovering disruptive behavior in those systems. Comparison-based diagnosis is a realistic approach to detect faulty units based on the outputs of tasks executed by system units. This survey integrates the vast amount of research efforts that have been produced in this field, from the earliest theoretical models to new promising applications. Key results also include the quantitative evaluation of a relevant reliability metric – the diagnosability – of several popular interconnection network topologies. Relevant diagnosis algorithms are also described. The survey aims at clarifying and uncovering the potential of this technology, which can be applied to improve the dependability of diverse complex computer systems.


References

Abrougui, K. and Elhadef, M. 2005. Parallel Self-Diagnosis of Large Multiprocessor Systems Under the Generalized Comparison Model. Proc. of the 11th Intl. Conf. on Parallel and Distributed Systems, 78–84.

Akers, S. B. and Krishnamurthy, B. 1989. A Group-Theoretic Model for Symmetric Interconnection Networks. IEEE Transactions on Computers. 38, 4 (Apr.), 555–566.

Albini, L., Caruso, A., Chessa, S., and Maestrini, P. 2006. Reliable Routing in Wireless Ad Hoc Networks: The Virtual Routing Protocol. Journal of Network and Systems Management. 14, 3 (Sept.), 335–358.

Albini, L. C. P., Chessa, S., and Maestrini, P. 2004. Diagnosis of Symmetric Graphs Under the BGM Model. The Computer Journal. 47, 1, 85–92.

Albini, L. C. P. and Duarte Jr., E. P. 2001. Generalized Distributed Comparison-Based System-Level Diagnosis. Proc of the 2nd IEEE Latin American Test Workshop, 285–290.

Albini, L. C. P., Duarte Jr., E. P., and Ziwich, R. P. 2005. A Generalized Model for Distributed Comparison-Based System-Level Diagnosis. Journal of the Brazilian Computer Society. 10, 3 (Apr.), 44–56.

Amaral, J., Amaral, J., Tanscheit, R., and Pacheco, M. 2004. An Immune Inspired Fault Diagnosis System for Analog Circuits Using Wavelet Signatures. Proc. of the 2004 NASA/DoD Conf. on Evolvable Hardware, 138–141.

Ammann, E. and Dal Cin, M. 1981. Efficient Algorithms for Comparison-Based Self-Diagnosis. Self-Diagnosis and Fault Tolerance, Werkhefte der Universitat Ttibingen, 4 Attempto-Verlag, Tubingen, 1. 18.

Araki, T. and Shibata, Y. 2000. Diagnosability of Networks by the Cartesian Product. IEICE Transactions on Fundamentals. E83-A, 3, 465–470.

Araki, T. and Shibata, Y. 2002a. Diagnosability of Butterfly Networks Under the Comparison Approach. IEICE Transactions on Fundamentals. E85-A, 5 (May).

Araki, T. and Shibata, Y. 2002b. Efficient Diagnosis on Butterfly Networks under the Comparison Approach. IEICE Transactions on Fundamentals. E85-A, 4 (Apr.).

Araki, T. and Shibata, Y. 2003. (t, k)-Diagnosable System: A Generalization of the PMC Models. IEEE Transactions on Computers. 52, 7 (July), 971–975.

Bagchi, A. and Hakimi, S. L. 1991. An Optimal Algorithm for Distributed System-Level Diagnosis. Proc. of the 21th IEEE Fault-Tolerant Computing Symp.

Barborak, M., Dahbura, A., and Malek, M. 1993. The Consensus Problem in Fault-Tolerant Computing. ACM Computing Surveys. 25, 2 (June), 171–220.

Barsi, F., Grandoni, F., and Maestrini, P. 1976. A Theory of Diagnosability Without Repair. IEEE Transactions on Computers. C-25, 585–593.

Basile, C., Killijian, M., and Powel, D. 2003. A Survey of Dependability Issues in Mobile Wireless Networks. Technical Report, Laboratory for Analysis and Architecture of Systems, National Center for Scientific Research, Toulouse, France.

Berge, C. 1973. Graphs and Hypergraphs. Amsterdam, The Netherlands: North-Holland. Bettayeb, S. 1995. On the k-Ary n-Cubes. Theoretical Computer Science. 140, 2, 333–339.

Bianchini, R. P. and Buskens, R. 1991. An Adaptive Distributed System-Level Diagnosis Algorithm and Its Implementation. Proc. of the 21th IEEE Fault-Tolerance Computing Symp.

Bianchini, R. P. and Buskens, R. 1992. Implementation of On-Line Distributed System-Level Diagnosis Theory. IEEE Transactions on Computers. 41, 616–626.

Bianchini, R. P., Goodwin, K., and Nydick, D. S. 1990. Practical Application and Implementation of System-Level Diagnosis Theory. Proc. of the 16th IEEE Fault-Tolerance Computing Symp., 332–339.

Blough, D. M. and Brown, H. W. 1999. The Broadcast Comparison Model for On-Line Fault Diagnosis in Multicomputer Systems: Theory and Implementation. IEEE Transactions on Computers. 48, 470–493.

Blough, D. M. and Pelc, A. 1992. Complexity of Fault Diagnosis in Comparison Models. IEEE Transactions on Computers. 41, 318–324.

Blough, D. M., Sullivan, G. F., and Masson, G. M. 1988. Almost Certain Diagnosis for Intermittently Faulty Systems. Proc. of the 18th IEEE Fault-Tolerant Computing Symp., 260–271.

Blount, M. L. 1977. Probabilistc Treatment of Diagnosis in Digital Systems. Proc. of the 7th IEEE Fault-Tolerance Computing Symp., 72–77.

Chang, C.-P., Lai, P.-L., Tan, J. J.-M., and Hsu, L.-H. 2004. Diagnosability of t-Connected Networks and Product Networks under the Comparison Diagnosis Model. IEEE Transactions on Computers. 53, 12 (Dec.), 1582–1590.

Chang, C.-P., Sung, T.-Y., and Hsu, L.-H. 2000. Edge Congestion and Topological Properties of Crossed Cubes. IEEE Transactions on Parallel and Distributed Systems. 11, 1 (Jan.), 64–80.

Chang, G.-Y., Chen, G.-H., and Chang, G. J. 2007. (t, k)-Diagnosis for Matching Composition Networks under the MM* Model. IEEE Transactions on Computers. 56, 1 (Jan.), 73–79.

Chen, Y., Bucken, W., and Echtle, K. 1993. Efficient Algorithms for System Diagnosis with Both Processor and Comparator Faults. IEEE Transactions on Parallel and Distributed Systems. 4, 4 (Apr.), 371–381.

Chessa, S. and Santi, P. 2001. Comparison-Based System-Level Fault Diagnosis in Ad Hoc Networks. Proc. of the 20th Symp. on Reliable Distributed Systems, LA, USA, 257–266.

Chiang, C.-F. and Tan, J. J. M. 2007. A Novel Approach to Comparison-Based Diagnosis for Hypercube-Like Multiprocessor Systems. Intl. Computer Symp., 166–169.

Chiang, C.-F. and Tan, J. J. M. 2009. Using Node Diagnosability to Determine t-Diagnosability under the Comparison Diagnosis Model. IEEE Transactions on Computers. 58, 1 (Jan.), 251–259.

Choi, Y.-H. and Jung, T. 1990. Probabilistic Diagnosis for Sparsely Interconnected Systems. Proc. of the ACM Annual Conf. on Cooperation, 298–304.

Chwa, K. Y. and Hakimi, S. L. 1981a. On Fault Identification in Diagnosable Systems. IEEE Transactions on Computers, C-30, 6 (June), 414–422.

Chwa, K. Y. and Hakimi, S. L. 1981b. Schemes for Fault-Tolerant Computing: A Comparison of Modularly Redundant and t-Diagnosable Systems. Information and Control. 49, 212–238.

Cull, P. and Larson, S. M. 1995. The M¨obius Cubes. IEEE Transactions on Computers. 44, 5 (May), 647–659.

Dahbura, A. T. and Masson, G. M. 1984. An O(n2.5) Fault Identification Algorithm for Diagnosable Systems. IEEE Transactions on Computers. C-33, 486–492.

Dahbura, A. T., Sabnani, K. K., and King, L. L. 1987. The Comparison Approach to Multiprocessor Fault Diagnosis. IEEE Transactions on Computers. C-36, 3 (Mar.), 373–378.

Dal Cin, M. 1982. A Diagnostic Device for Large Multiprocessor Systems. Proc. of the 12th IEEE Fault-Tolerant Computing Symp., 357–360.

Das, S. K., Ohring, S. R., and Banerjee, A. K. 1995. Embeddings Into Hyper Petersen Networks: Yet Another Hypercube-Like Interconnection Topology. VLSI Design. 2, 4, 335–351.

Dasgupta, D., KrishnaKumar, K., Wong, D., and Berry, M. 2004. Negative Selection Algorithm for Aircraft Fault Detection. Proc. of the 3rd Intl. Conf. on Artificial Immune Systems, 1–13.

Duarte Jr., E. P., Brawerman, A., and Albini, L. C. P. 2000. An Algorithm for Distributed Hierarquical Diagnosis of Dynamic Fault and Repair Events. Proc. of the IEEE Intl. Conf. on Parallel and Distributed Systems, 299–306.

Duarte Jr., E. P. and Nanya, T. 1995. Multi-Cluster Adaptive Distributed System-Level Diagnosis Algorithms. IEICE Techinical Report FTS, 95-73.

Duarte Jr., E. P. and Nanya, T. 1998. A Hierarquical Adaptive Distributed System-Level Diagnosis Algotithm. IEEE Transactions on Computers. 47, 1 (Jan.), 34–45.

Duarte Jr., E. P. and Weber, A. 2003. A Distributed Network Connectivity Algorithm. Proc. of the 6th IEEE Intl. Symp. on Autonomous Decentralized Systems (ISADS’2003), Pisa, Italy, 285–292.

Efe, K. 1991. A Variation on the Hypercube with Lower Diameter. IEEE Transactions on Computers. 40, 11 (Nov.), 1312–1316.

Efe, K. 1992. The Crossed Cube Architecture for Parallel Computing. IEEE Transactions on Parallel and Distributed Systems. 3, 5 (Sept.), 513–524.

Efe, K., Blackwell, P. K., Slough, W., and Shiau, T. 1995. Topological Properties of the Crossed Cubes Architecture. IEEE Transactions on Computers. 44, 7 (July), 923–929.

Elhadef, M. and Ayeb, B. 2000. An Evolutionary Algorithm for Identifying faults in t-Diagnosable Systems. Proc. of the 19th Symp. on Reliable Distributed Systems, 74–83.

Elhadef, M. and Ayeb, B. 2001a. Efficient Comparison-Based Fault Diagnosis of Multiprocessor Systems Using an Evolutionary Approach. Proc. of the 15th Intl. Parallel and Distributed Processing Symp. 1, 6.

Elhadef, M. and Ayeb, B. 2001b. Self-Diagnosis of Multiprocessor Systems Under Generalized Comparison Model. Proc. of the ISCA Intl. Conf. on Parallel and Distributed Computing Systems, 372–379.

Elhadef, M. and Ayeb, B. 2002. An Evolutionary Algorithm for Generalized Comparison-Based Self-Diagnosis of Multiprocessor Systems. Applied Artificial Intelligence. 16, 1 (Jan.), 73–95.

Elhadef, M., Boukerche, A., and Elkadiki, H. 2006a. Diagnosing Mobile Ad Hoc Networks: Two Distributed Comparison-Based Self-Diagnosis Protocols. Proc. of the 4th ACM Intl. Workshop on Mobility Management and Wireless Access, 18–27.

Elhadef, M., Boukerche, A., and Elkadiki, H. 2006b. Performance Analysis of a Distributed Comparison-Based Self-Diagnosis Protocol for Wireless Ad Hoc Networks. Proc. of the 9th ACM Intl. Symp. on Modeling Analysis and Simulation of Wireless and Mobile Systems, 165–172.

Elhadef, M., Boukerche, A., and Elkadiki, H. 2007. Self-Diagnosing Wireless Mesh and Ad Hoc Networks using an Adaptable Comparison-Based Approach. Proc. of the 2nd Intl. Conf. Availability, Reliability and Security, 983–990.

Elhadef, M., Das, S., and Nayak, A. 2006. System-Level Fault Diagnosis Using Comparison Models: An Artificial-Immune-Systems-Based Approach. Journal of Networks, 43–53.

Esfahanian, A.-H., Ni, L. M., and Sagan, B. E. 1991. The Twisted n-Cube with Application to Multiprocessing. IEEE Transactions on Computers. 40, 1 (Jan.), 88–93.

Fan, J. 1998. Diagnosability of the M¨obius Cubes. IEEE Transactions on Parallel and Distributed Systems. 9, 9 (Sept.), 923–928.

Fan, J. 2002. Diagnosability of Crossed Cubes. IEEE Transactions on Computers. 13, 10 (Oct.), 1099–1104.

Friedman, A. D. 1975. A New Measure of Digital System Diagnosis. Proc. of the 5th IEEE Fault-Tolerant Computing Symp., 167–169.

Fuhrman, C. P. and Nussbaumer, H. J. 1996a. A New Comparison Model in System-Level Diagnosis. Proc. of the Intl. Conf. on Parallel and Distributed Processing Techniques and Applications.

Fuhrman, C. P. and Nussbaumer, H. J. 1996b. Comparison Diagnosis in Large Multiprocessor Systems. Proc. of the 5th Asian Test Symp., 244–249.

Fujiwara, H. and Kinoshita, K. 1978. Connection Assignments for Probabilistically Diagnosable Systems. IEEE Transactions on Computers. C-27, 280–283.

Fussell, D., Malek, M., and Rangarajan, S. 1989. Wafer-Scale Testing/Design for Testability. Kluwer, Chapter 9, 413–472.

Fussell, D. and Rangarajan, S. 1989. Probabilistic Diagnosis of Multiprocessor Systems with Arbitrary Connectivity. Proc. of the 19th IEEE Fault-Tolerant Computing Symp., 560–565.

Hadzilacos, V. and Toueg, S. 1993. Fault-Tolerant Broadcasts and Related Problems, Distributed Systems. S. Mullender, ACM Press, C.5.

Hakimi, S. L. and Amin, A. T. 1974. Characterization of Connection Assignment of Diagnosable Systems. IEEE Transactions on Computers. 23, 86–88.

Hakimi, S. L. and Nakajima, K. 1984. On Adaptive System Diagnosis. IEEE Transactions on Computers. C-33, 3 (Mar.), 234–240.

Hollick, M., Martinovic, I., Krop, T., and Rimac, I. 2004. A Survey on Dependable Routing in Sensor Networks, Ad Hoc Networks, and Cellular Networks. Proc. of the 30th EUROMICRO Conf., 495–502.

Hosseini, S. H., Kuhl, J. G., and Reddy, S. M. 1984. A Diagnosis Algorithm for Distributed Computing Systems with Dynamic Failure and Repair. IEEE Transactions on Computers. C-33, 3 (Mar.), 223–233.

Hsieh, S.-Y. and Chen, Y.-S. 2008a. Strongly Diagnosable Product Networks Under the Comparison Diagnosis Model. IEEE Transactions on Computers. 57, 6 (June), 721–732.

Hsieh, S.-Y. and Chen, Y.-S. 2008b. Strongly Diagnosable Systems Under the Comparison Model. IEEE Transactions on Computers. 57, 12 (Dec.), 1720–1725.

Ishida, Y. 1997. Active Diagnosis by Self-Organization: An Approach by The Immune Network Metaphor. Proc. of the 15th Intl. Joint Conf. on Artificial Intelligence, 1084–1091.

Jalote, P. 1994. Fault Tolerance in Distributed Systems. Prentice Hall. Kavianpour, A. 1996. Sequential Diagnosability of Star Graphs. Journal of Computers and Electrical Engineering. 22, 1 (Jan.), 37–44.

Kozlowski, W. E. and Krawczyk, H. 1991. A Comparison-Based Approach in Multicomputer System Diagnosis in Hybrid Fault Situations. IEEE Transations on Computers. 40, 11, 1283– 1286.

Kreutzer, S. E. and Hakimi, S. L. 1983. Adaptive Fault Identification in Two DiagnosticModels. Proc. of the 21th Allerton Conf. on Communication, Control and Computing, 353–362.

Kuhl, J. G. 1980. Fault Diagnosis in Computing Networks. Dep. Elec. Comput. Eng., Univ. of Iowa, Technical Report.

Kuhl, J. G. and Reddy, S. M. 1980. Distributed Fault-Tolerance for Large Multiprocessor Systems. Proc. of the 7th Annual Intl. Symp. on Computer Architecture, 23–30.

Kuhl, J. G. and Reddy, S. M. 1981. Fault-Diagnosis in Fully Distributed Systems. Proc. of the 11th IEEE Fault-Tolerant Computing Symp., 100–105.

Kulasinghe, P. and Bettayeb, S. 1995. Embedding Binary Trees into Crossed Cubes. IEEE Transactions on Computers. 44, 7 (July), 923–929.

LaForge, L. E., Kover, K. F., and Fadali, M. S. 2003. What Designers of Bus and Networks Architectures Should Know about Hypercubes. IEEE Transactions on Computers. 52, 4 (Apr.), 525–533.

Lai, P.-L., Tan, J. J., Tsai, C.-H., and Hsu, L.-H. 2004. The Diagnosability of the matching Composition Netork under the Comparison Diagnosis Model. IEEE Transactions on Computers. 53, 8 (Aug.), 1064–1069.

Lai, P.-L., Tan, J. J. M., Chang, C.-P., and Hsu, L.-H. 2005. Conditional Diagnosability Measures for Large Multiprocessor Systems. IEEE Transactions on Computers. 54, 2 (Feb.), 165–175.

Laranjeira, L. A., Malek, M., and Jenevein, R. M. 1991. On Tolerating Faults in Naturally Redundant Algorithms. Proc. of the 10th IEEE Symp. Reliable Distributed Systems, 118–127.

Lee, S. and Shin, K. G. 1994. On Probabilistic Diagnosis of Multiprocessor Systems Using Multiple Syndromes. IEEE Transactions on Parallel and Distributed Systems. 5, 6 (June), 630–638.

Leighton, F. T. 1992. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann, San Mateo, CA.

Leighton, F. T., Maggs, B. M., and Sitaraman, R. K. 1998. On The Fault Tolerance of Some Popular Bounded-Degree Networks. SIAM Journal on Computing. 27, 5, 1303–1333.

Lombardi, F. 1986. Comparison-Based Diagnosis with Faulty Comparators. Eletronic Letters. 22, 22 (Oct.), 1158–1160.

Ma, M. J. and Xu, J. M. 2006. Panconnectivity of Locally Twisted Cubes. Appl. Math. Lett. 19, 7, 673–677.

Maeng, J. and Malek, M. 1981. A Comparison Connection Assignment for Self-Diagnosis of Multiprocessor Systems. Proc. of the 11th IEEE Fault-Tolerant Computing Symp., 173–175.

Maestrini, P. and Santi, P. 1995. Self Diagnosis of Processor Arrays Using a Comparison Model. Proc. of the 14th Symp. on Reliable Distributed Systems, 218–228.

Maheshwari, S. N. and Hakimi, S. L. 1976. OnModels for Diagnosable Systems and Probabilistic Fault Diagnosis. IEEE Transactions on Computers. C-25, 228–236.

Malek, M. 1980. A Comparison Connection Assignment for Diagnosis of Multiprocessor Systems. Proc. of the 7th Annual Intl. Symp. on Computer Architecture, 31–36.

Martins, F. S., Maia, M., Andrade, R. M., Santos, A. L., and de Souza, J. N. 2006a. A Grid Computing Diagnosis Model for Tolerating Manipulation Attacks. Proc. of the Intl. Conf. on Self-Organization and Autonomous Systems in Computing and Communications.

Martins, F. S., Maia, M., Andrade, R. M., Santos, A. L., and de Souza, J. N. 2006b. A New Comparison-Based Scheme for Multiprocessor Fault Tolerance. Proc. of the 18th Intl. Symp. on Computer Architecture and High Performance Computing.

Masson, G., Blough, D., and Sullivan, G. 1996. System Diagnosis. Prentice-Hall.

Micali, S. and Vazirani, V. V. 1980. An O(p|V ||E|) Algorithm for Maximum Matching in General Graphs. Proc. of the 16th Annual Symp. Foundations of Comput. Science, 17–27.

Nakajima, K. 1981. A New Approach to System Diagnosis. Proc. of the 19th Allerton Conf. on Communication, Control and Computing, 697–706.

Nassu, B. T., Duarte Jr., E. P., and Pozo, A. T. R. 2005. A Comparison of Evolutionary Algorithms for System-Level Diagnosis. Proc. of the 7th ACM Genetic and Evolutionary Computation Conf., 2053–2060.

Pelc, A. 1991. Undirected Graph Models for System-Level Fault Diagnosis. IEEE Transactions on Computers. 40, 1271–1276.

Pelc, A. 1992. Optimal Fault Diagnosis in Comparison Models. IEEE Transations on Computers. 41, 6 (June), 779–786.

Preparata, F., Metze, G., and Chien, R. T. 1967. On the Connection Assignment Problem of Diagnosable Systems. IEEE Transactions on Computers. 16, 848–854.

Pressman, R. 2004. Software Engineering: A Practitioner’s Approach. McGraw-Hill.

Raghavan, V. and Tripathi, A. R. 1991. Sequential Diagnosability is co-NP-Complete. IEEE Transactions on Computers. 40, 5 (May), 584–595.

Rangarajan, S., Dahbura, A. T., and Ziegler, E. A. 1995. A Distributed System-Level Diagnosis Algorithm for Arbitrary Network Topologies. IEEE Transactions on Computers. 44, 2 (Feb.), 312–333.

Rangarajan, S. and Fussell, D. 1988. A Probabilistic Method for Fault Diagnosis of Multiprocessor Systems. Proc. of the 18th IEEE Fault-Tolerant Computing Symp., 278–283.

Rangarajan, S., Fussell, D., and Malek, M. 1990. Built-in Testing of Integrated Circuits Wafers. IEEE Transactions on Computers. 39, 2 (Feb.), 195–205.

Rettberg, R. D. 1986. Shared Memory Parallel Processing: The Butterfly and the Monarch. MIT Press.

Sallay, B., Maestrini, P., and Santi, P. 1999. Wafer-Scale Diagnosis Tolerating Comparator Faults. IEE Proc. Computer and Digital Techniques. 146, 4 (July), 211–215.

Sengupta, A. and Dahbura, A. T. 1992. On Self-Diagnosable Multiprocessor Systems: Diagnosis by Comparison Approach. IEEE Transactions on Computers. 41, 11 (Nov.), 1386–1396.

Sengupta, A. and Rhee, C. 1990. On the Diagnosability of Systems with Three Valued Test Results: Diagnosis by Comparison Strategy. Proc. of the 20th Intl. Symp. on Multiple-Valued Logic, 115–120.

Sheu, J.-J., Huang, W.-T., and Chen, C.-H. 2008. Strong Diagnosability of Regular Networks Under the Comparison Model. Information Processing Letters 106, 1 (Mar.), 19–25.

Stahl, M., Buskens, R., and Bianchini, R. 1992. Simulation of the Adapt On-Line Diagnosis Algorithm for General Topology Networks. Proc. of the 11th IEEE Symp. Reliable Distributed Systems.

Subbiah, A. and Blough, D. M. 2004. Distributed Diagnosis in Dynamic Fault Environments. IEEE Transactions on Parallel and Distributed Systems. 15, 5 (May), 453–467.

Sullivan, G. 1988. An O(t3+|E|) Fault Identification Algorithm for Diagnosable Systems. IEEE Transactions on Computers. 37, 4, 388–397.

Tamaki, H. 1998. Efficient Self-Embedding of Butterfly Networks with Random Faults. SIAM Journal on Computing. 27, 3, 614–636.

Tzeng, N. F. and Wei, S. 1991. Enhanced Hypercubes. IEEE Transactions on Computers. 40, 3 (Mar.), 284–294.

Vaidya, A. S., Rao, P. S. N., and Shankar, S. R. 1993. A Class of Hypercube-like Networks. Proc. of the 5th IEEE Symp. Parallel and Distributed Processing. 1, 4 (Dec.), 800–803.

Wang, D. 1999. Diagnosability of Hipercubes and Enhanced Hypercubes under the Comparison Diagnosis Model. IEEE Transactions on Computers. 48, 12, 1369–1374.

Wang, H., Blough, D. M., and Alkalaj, L. 1994a. Analysis and Experimental Evaluation of Comparison-Based System-Level Diagnosis for Multiprocessor Systems. Proc. of the 24th IEEE Fault-Tolerant Computing Symp., 55–64.

Wang, H., Blough, D. M., and Alkalaj, L. 1994b. Practical Approach to Comparison-based Fault Diagnosis in Multiprocessor Systems. Intl. Journal of Computer Systems Science and Engineering. 9, 11–20.

Xu, J. and Huang, S. 1990. A New Comparison-Based Scheme for Multiprocessor Fault Tolerance. Microprocessing and Microprogramming. 30, 617–624.

Xu, J. and Randell, B. 1997. Software Fault Tolerance: t/(n-1)-Variant Programming. IEEE Transactions on Reliability. 46, 1 (Mar.), 60–68.

Yang, C.-L. and Masson, G. M. 1987. An Efficient Algorithm for Multiprocessor Fault Diagnosis Using the Comparison Approach. Information and Computation. 74, 1 (July), 50–63.

Yang, H. and Yang, X. 2007. A Fast Diagnosis Algorithm for Locally Twisted Cube Multiprocessor Systems under the MM* Model. Computers & Mathematics with Applications. 53, 6, 918–926.

Yang, X. 2003. A Linear Time Fault Diagnosis Algorithm for Hypercube Multiprocessors Under the MM* Model. Proc. of the 12th Asian Test Symp., 50–55.

Yang, X. and Tang, Y. Y. 2007. Efficient Fault Identification of Diagnosable Systems under the Comparison Model. IEEE Transactions on Computers. 56, 12 (Dec.), 1612–1618.

Yang, X. F., Evans, D. J., and Megson, G. M. 2004. Locally Twisted Cubes are 3-Pancyclic. Appl. Math. Lett., 17, 8, 919–925.

Yang, X. F., Evans, D. J., and Megson, G. M. 2005. The Locally Twisted Cubes. Intl. Journal of Computer Mathematics. 82, 4 (Apr.), 401–413.

Yang, X. F., Megson, G. M., and Evans, D. J. 2005. A Comparison-Based Diagnosis Algorithm Tailored for Crossed Cube Multiprocessor Systems. Microprocessors and Microsystems. 19, 4 (May), 169–175.

Zheng, J., Latifi, S., Regentova, E., Luo, K., and Wu, X. 2002. Diagnosability of Star Graphs under the Comparison Diagnosis Model. Information Processing Letters. 16, 1 (Jan.), 73–95.

Ziwich, R. P., Duarte Jr., E. P., and Albini, L. C. P. 2005. Distributed Integrity Checking for System with Replicated Data. Proc. of the 11th IEEE Intl. Conf. on Parallel and Distributed Systems, 363–369.