More Web Proxy on the site http://driver.im/

research-article

A survey of comparison-based system-level diagnosis

Authors:

Elias P. Duarte, Jr.,

Roverli P. Ziwich,

Luiz C.P. AlbiniAuthors Info & Claims

ACM Computing Surveys (CSUR), Volume 43, Issue 3

Article No.: 22, Pages 1 - 56

https://doi.org/10.1145/1922649.1922659

Published: 29 April 2011 Publication History

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

[1]

Abrougui, K. and Elhadef, M. 2005. Parallel self-diagnosis of large multiprocessor systems under the generalized comparison model. In Proceedings of the 11th International Conference on Parallel and Distributed Systems. 78--84.

Digital Library

[2]

Akers, S. B. and Krishnamurthy, B. 1989. A group-theoretic model for symmetric interconnection networks. IEEE Trans. Comput. 38, 4, 555--566.

Digital Library

[3]

Albini, L., Caruso, A., Chessa, S., and Maestrini, P. 2006. Reliable routing in wireless ad hoc networks: The virtual routing protocol. J. Netw. Syst. Manag. 14, 3, 335--358.

Digital Library

[4]

Albini, L. C. P., Chessa, S., and Maestrini, P. 2004. Diagnosis of symmetric graphs under the BGM model. The Comput. J. 47, 1, 85--92.

[5]

Albini, L. C. P. and Duarte Jr., E. P. 2001. Generalized distributed comparison-based system-level diagnosis. In Proceedings of the 2nd IEEE Latin American Test Workshop. 285--290.

[6]

Albini, L. C. P., Duarte Jr., E. P., and Ziwich, R. P. 2005. A generalized model for distributed comparison-based system-level diagnosis. J. Brazil. Comput. Soc. 10, 3, 44--56.

[7]

Amaral, J., Amaral, J., Tanscheit, R., and Pacheco, M. 2004. An immune inspired fault diagnosis system for analog circuits using wavelet signatures. In Proceedings of the NASA/DoD Conference on Evolvable Hardware. 138--141.

[8]

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.

[9]

Araki, T. and Shibata, Y. 2000. Diagnosability of networks by the Cartesian product. IEICE Trans. Fundam. E83-A, 3, 465--470.

[10]

Araki, T. and Shibata, Y. 2002a. Diagnosability of butterfly networks under the comparison approach. IEICE Trans. Fundam. E85-A, 5.

[11]

Araki, T. and Shibata, Y. 2002b. Efficient diagnosis on butterfly networks under the comparison approach. IEICE Trans. Fundam. E85-A, 4.

[12]

Araki, T. and Shibata, Y. 2003. (t,k)-Diagnosable system: A generalization of the PMC models. IEEE Trans. Comput. 52, 7, 971--975.

Digital Library

[13]

Bagchi, A. and Hakimi, S. L. 1991. An optimal algorithm for distributed system-level diagnosis. In Proceedings of the 21th IEEE Fault-Tolerant Computing Symposium.

[14]

Barborak, M., Dahbura, A., and Malek, M. 1993. The consensus problem in fault-tolerant computing. ACM Comput. Surv. 25, 2, 171--220.

Digital Library

[15]

Barsi, F., Grandoni, F., and Maestrini, P. 1976. A theory of diagnosability without repair. IEEE Trans. Comput. C-25, 585--593.

Digital Library

[16]

Basile, C., Killijian, M., and Powel, D. 2003. A survey of dependability issues in mobile wireless networks. Tech. rep., Laboratory for Analysis and Architecture of Systems, National Center for Scientific Research, Toulouse, France.

[17]

Berge, C. 1973. Graphs and Hypergraphs. North-Holland, Amsterdam, The Netherlands.

Digital Library

[18]

Bettayeb, S. 1995. On the k-ary n-cubes. Theor. Comput. Sci. 140, 2, 333--339.

Digital Library

[19]

Bianchini, R. P. and Buskens, R. 1991. An adaptive distributed system-level diagnosis algorithm and its implementation. In Proceedings of the 21th IEEE Fault-Tolerance Computing Symposium.

[20]

Bianchini, R. P. and Buskens, R. 1992. Implementation of on-line distributed system-level diagnosis theory. IEEE Trans. Comput. 41, 616--626.

Digital Library

[21]

Bianchini, R. P., Goodwin, K., and Nydick, D. S. 1990. Practical application and implementation of system-level diagnosis theory. In Proceedings of the 16th IEEE Fault-Tolerance Computing Symposium. 332--339.

[22]

Blough, D. M. and Brown, H. W. 1999. The broadcast comparison model for on-line fault diagnosis in multicomputer systems: Theory and implementation. IEEE Trans. Comput. 48, 470--493.

Digital Library

[23]

Blough, D. M. and Pelc, A. 1992. Complexity of fault diagnosis in comparison models. IEEE Trans. Comput. 41, 318--324.

Digital Library

[24]

Blough, D. M., Sullivan, G. F., and Masson, G. M. 1988. Almost certain diagnosis for intermittently faulty systems. In Proceedings of the 18th IEEE Fault-Tolerant Computing Symposium. 260--271.

[25]

Blount, M. L. 1977. Probabilistc treatment of diagnosis in digital systems. In Proceedings of the 7th IEEE Fault-Tolerance Computing Symposium. 72--77.

[26]

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 Trans. Comput. 53, 12, 1582--1590.

Digital Library

[27]

Chang, C.-P., Sung, T.-Y., and Hsu, L.-H. 2000. Edge congestion and topological properties of crossed cubes. IEEE Trans. Parallel Distrib. Syst. 11, 1, 64--80.

Digital Library

[28]

Chang, G.-Y., Chen, G.-H., and Chang, G. J. 2007. (t,k)-Diagnosis for matching composition networks under the MM&ast; model. IEEE Trans. Comput. 56, 1, 73--79.

Digital Library

[29]

Chen, Y., Bucken, W., and Echtle, K. 1993. Efficient algorithms for system diagnosis with both processor and comparator faults. IEEE Trans. Parallel Distrib. Syst. 4, 4, 371--381.

Digital Library

[30]

Chessa, S. and Santi, P. 2001. Comparison-based system-level fault diagnosis in ad hoc networks. In Proceedings of the 20th Symposium on Reliable Distributed Systems. 257--266.

[31]

Chiang, C.-F. and Tan, J. J. M. 2007. A novel approach to comparison-based diagnosis for hypercube-like multiprocessor systems. In Proceedings of the International Computer Symposium. 166--169.

[32]

Chiang, C.-F. and Tan, J. J. M. 2009. Using node diagnosability to determine t-diagnosability under the comparison diagnosis model. IEEE Trans. Comput. 58, 1, 251--259.

Digital Library

[33]

Choi, Y.-H. and Jung, T. 1990. Probabilistic diagnosis for sparsely interconnected systems. In Proceedings of the ACM Annual Conference on Cooperation. 298--304.

Digital Library

[34]

Chwa, K. Y. and Hakimi, S. L. 1981a. On fault identification in diagnosable systems. IEEE Trans. Comput. C-30, 6, 414--422.

Digital Library

[35]

Chwa, K. Y. and Hakimi, S. L. 1981b. Schemes for fault-tolerant computing: A comparison of modularly redundant and t-diagnosable systems. Inf. Control 49, 212--238.

[36]

Cull, P. and Larson, S. M. 1995. The m&#246;bius cubes. IEEE Trans. Comput. 44, 5, 647--659.

Digital Library

[37]

Dahbura, A. T. and Masson, G. M. 1984. An O(n<sup>2.5</sup>) fault identification algorithm for diagnosable systems. IEEE Trans. Comput. C-33, 486--492.

Digital Library

[38]

Dahbura, A. T., Sabnani, K. K., and King, L. L. 1987. The comparison approach to multiprocessor fault diagnosis. IEEE Trans. Comput. C-36, 3, 373--378.

Digital Library

[39]

Dal Cin, M. 1982. A diagnostic device for large multiprocessor systems. In Proceedings of the 12th IEEE Fault-Tolerant Computing Symposium. 357--360.

[40]

Das, S. K., Ohring, S. R., and Banerjee, A. K. 1995. Embeddings into hyper petersen networks: Yet another hypercube-like interconnection topology. VLSI Des. 2, 4, 335--351.

[41]

Dasgupta, D., KrishnaKumar, K., Wong, D., and Berry, M. 2004. Negative selection algorithm for aircraft fault detection. In Proceedings of the 3rd International Conference on Artificial Immune Systems. 1--13.

[42]

Duarte Jr., E. P., Brawerman, A., and Albini, L. C. P. 2000. An algorithm for distributed hierarquical diagnosis of dynamic fault and repair events. In Proceedings of the IEEE International Conference on Parallel and Distributed Systems. 299--306.

Digital Library

[43]

Duarte Jr., E. P. and Nanya, T. 1995. Multi-cluster adaptive distributed system-level diagnosis algorithms. IEICE Tech. rep. FTS 95-73.

[44]

Duarte Jr., E. P. and Nanya, T. 1998. A hierarquical adaptive distributed system-level diagnosis algotithm. IEEE Trans. Comput. 47, 1, 34--45.

Digital Library

[45]

Duarte Jr., E. P. and Weber, A. 2003. A distributed network connectivity algorithm. In Proceedings of the 6th IEEE International Symposium on Autonomous Decentralized Systems (ISADS'03). 285--292.

Digital Library

[46]

Efe, K. 1991. A variation on the hypercube with lower diameter. IEEE Trans. Comput. 40, 11, 1312--1316.

Digital Library

[47]

Efe, K. 1992. The crossed cube architecture for parallel computing. IEEE Trans. Parallel Distrib. Syst. 3, 5, 513--524.

Digital Library

[48]

Efe, K., Blackwell, P. K., Slough, W., and Shiau, T. 1995. Topological properties of the crossed cubes architecture. IEEE Trans. Comput. 44, 7, 923--929.

[49]

Elhadef, M. and Ayeb, B. 2000. An evolutionary algorithm for identifying faults in t-diagnosable systems. In Proceedings of the 19th Symposium on Reliable Distributed Systems. 74--83.

Digital Library

[50]

Elhadef, M. and Ayeb, B. 2001a. Efficient comparison-based fault diagnosis of multiprocessor systems using an evolutionary approach. In Proceedings of the 15th International Parallel and Distributed Processing Symposium. 1, 6.

Digital Library

[51]

Elhadef, M. and Ayeb, B. 2001b. Self-diagnosis of multiprocessor systems under generalized comparison model. In Proceedings of the ISCA International Conference on Parallel and Distributed Computing Systems. 372--379.

[52]

Elhadef, M. and Ayeb, B. 2002. An evolutionary algorithm for generalized comparison-based self-diagnosis of multiprocessor systems. Appl. Artif. Intell. 16, 1, 73--95.

[53]

Elhadef, M., Boukerche, A., and Elkadiki, H. 2006a. Diagnosing mobile ad hoc networks: Two distributed comparison-based self-diagnosis protocols. In Proceedings of the 4th ACM International Workshop on Mobility Management and Wireless Access. 18--27.

Digital Library

[54]

Elhadef, M., Boukerche, A., and Elkadiki, H. 2006b. Performance analysis of a distributed comparison-based self-diagnosis protocol for wireless ad hoc networks. In Proceedings of the 9th ACM International Symposium on Modeling Analysis and Simulation of Wireless and Mobile Systems. 165--172.

Digital Library

[55]

Elhadef, M., Boukerche, A., and Elkadiki, H. 2007. Self-diagnosing wireless mesh and ad hoc networks using an adaptable comparison-based approach. In Proceedings of the 2nd International Conference on Availability, Reliability and Security. 983--990.

Digital Library

[56]

Elhadef, M., Das, S., and Nayak, A. 2006c. System-level fault diagnosis using comparison models: An artificial-immune-systems-based approach. J. Netw., 43--53.

[57]

Esfahanian, A.-H., Ni, L. M., and Sagan, B. E. 1991. The twisted n-cube with application to multiprocessing. IEEE Trans. Comput. 40, 1, 88--93.

Digital Library

[58]

Fan, J. 1998. Diagnosability of the m&#246;bius cubes. IEEE Trans. Parallel Distrib. Syst. 9, 9, 923--928.

Digital Library

[59]

Fan, J. 2002. Diagnosability of crossed cubes. IEEE Trans. Comput. 13, 10, 1099--1104.

Digital Library

[60]

Friedman, A. D. 1975. A new measure of digital system diagnosis. In Proceedings of the 5th IEEE Fault-Tolerant Computing Symposium. 167--169.

[61]

Fuhrman, C. P. and Nussbaumer, H. J. 1996a. A new comparison model in system-level diagnosis. In Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications.

[62]

Fuhrman, C. P. and Nussbaumer, H. J. 1996b. Comparison diagnosis in large multiprocessor systems. In Proceedings of the 5th Asian Test Symposium. 244--249.

Digital Library

[63]

Fujiwara, H. and Kinoshita, K. 1978. Connection assignments for probabilistically diagnosable systems. IEEE Trans. Comput. C-27, 280--283.

Digital Library

[64]

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

[65]

Fussell, D. and Rangarajan, S. 1989. Probabilistic diagnosis of multiprocessor systems with arbitrary connectivity. In Proceedings of the 19th IEEE Fault-Tolerant Computing Symposium. 560--565.

[66]

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

Digital Library

[67]

Hakimi, S. L. and Amin, A. T. 1974. Characterization of connection assignment of diagnosable systems. IEEE Trans. Comput. 23, 86--88.

Digital Library

[68]

Hakimi, S. L. and Nakajima, K. 1984. On adaptive system diagnosis. IEEE Trans. Comput. C-33, 3, 234--240.

Digital Library

[69]

Hollick, M., Martinovic, I., Krop, T., and Rimac, I. 2004. A survey on dependable routing in sensor networks, ad hoc networks, and cellular networks. In Proceedings of the 30th EUROMICRO Conference. 495--502.

Digital Library

[70]

Hosseini, S. H., Kuhl, J. G., and Reddy, S. M. 1984. A diagnosis algorithm for distributed computing systems with dynamic failure and repair. IEEE Trans. Comput. C-33, 3, 223--233.

Digital Library

[71]

Hsieh, S.-Y. and Chen, Y.-S. 2008a. Strongly diagnosable product networks under the comparison diagnosis model. IEEE Trans. Comput. 57, 6, 721--732.

Digital Library

[72]

Hsieh, S.-Y. and Chen, Y.-S. 2008b. Strongly diagnosable systems under the comparison model. IEEE Trans. Comput. 57, 12, 1720--1725.

Digital Library

[73]

Ishida, Y. 1997. Active diagnosis by self-organization: An approach by the immune network metaphor. In Proceedings of the 15th International Joint Conference on Artificial Intelligence. 1084--1091.

Digital Library

[74]

Jalote, P. 1994. Fault Tolerance in Distributed Systems. Prentice Hall.

Digital Library

[75]

Kavianpour, A. 1996. Sequential diagnosability of star graphs. J. Comput. Electr. Engin. 22, 1, 37--44.

[76]

Kozlowski, W. E. and Krawczyk, H. 1991. A comparison-based approach in multicomputer system diagnosis in hybrid fault situations. IEEE Trans. Comput. 40, 11, 1283--1286.

Digital Library

[77]

Kreutzer, S. E. and Hakimi, S. L. 1983. Adaptive fault identification in two diagnostic models. In Proceedings of the 21th Allerton Conference on Communication, Control and Computing. 353--362.

[78]

Kuhl, J. G. 1980. Fault diagnosis in computing networks. Tech. rep., Department of Electrical and Computer Engineering, University of Iowa.

[79]

Kuhl, J. G. and Reddy, S. M. 1980. Distributed fault-tolerance for large multiprocessor systems. In Proceedings of the 7th Annual International Symposium on Computer Architecture. 23--30.

Digital Library

[80]

Kuhl, J. G. and Reddy, S. M. 1981. Fault-diagnosis in fully distributed systems. In Proceedings of the 11th IEEE Fault-Tolerant Computing Symposium. 100--105.

[81]

Kulasinghe, P. and Bettayeb, S. 1995. Embedding binary trees into crossed cubes. IEEE Trans. Comput. 44, 7, 923--929.

Digital Library

[82]

LaForge, L. E., Kover, K. F., and Fadali, M. S. 2003. What designers of bus and networks architectures should know about hypercubes. IEEE Trans. Comput. 52, 4, 525--533.

Digital Library

[83]

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 Trans. Comput. 53, 8, 1064--1069.

Digital Library

[84]

Lai, P.-L., Tan, J. J. M., Chang, C.-P., and Hsu, L.-H. 2005. Conditional diagnosability measures for large multiprocessor systems. IEEE Trans. Comput. 54, 2, 165--175.

Digital Library

[85]

Laranjeira, L. A., Malek, M., and Jenevein, R. M. 1991. On tolerating faults in naturally redundant algorithms. In Proceedings of the 10th IEEE Symposium Reliable Distributed Systems. 118--127.

[86]

Lee, S. and Shin, K. G. 1994. On probabilistic diagnosis of multiprocessor systems using multiple syndromes. IEEE Trans. Parallel Distrib. Syst. 5, 6, 630--638.

Digital Library

[87]

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

Digital Library

[88]

Leighton, F. T., Maggs, B. M., and Sitaraman, R. K. 1998. On the fault tolerance of some popular bounded-degree networks. SIAM J. Comput. 27, 5, 1303--1333.

Digital Library

[89]

Lombardi, F. 1986. Comparison-based diagnosis with faulty comparators. Eletron. Lett. 22, 22, 1158--1160.

[90]

Ma, M. J. and Xu, J. M. 2006. Panconnectivity of locally twisted cubes. Appl. Math. Lett. 19, 7, 673--677.

[91]

Maeng, J. and Malek, M. 1981. A comparison connection assignment for self-diagnosis of multiprocessor systems. In Proceedings of the 11th IEEE Fault-Tolerant Computing Symposium. 173--175.

[92]

Maestrini, P. and Santi, P. 1995. Self diagnosis of processor arrays using a comparison model. In Proceedings of the 14th Symposium on Reliable Distributed Systems. 218--228.

Digital Library

[93]

Maheshwari, S. N. and Hakimi, S. L. 1976. On models for diagnosable systems and probabilistic fault diagnosis. IEEE Trans. Comput. C-25, 228--236.

Digital Library

[94]

Malek, M. 1980. A comparison connection assignment for diagnosis of multiprocessor systems. In Proceedings of the 7th Annual International Symposium on Computer Architecture. 31--36.

Digital Library

[95]

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. In Proceedings of the International Conference on Self-Organization and Autonomous Systems in Computing and Communications.

[96]

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. In Proceedings of the 18th International Symposium on Computer Architecture and High Performance Computing.

[97]

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

[98]

Micali, S. and Vazirani, V. V. 1980. An O(&sqrt;&vert;V&Vert;E&vert;) algorithm for maximum matching in general graphs. In Proceedings of the 16th Annual Symposium Foundations of Computer Science. 17--27.

Digital Library

[99]

Nakajima, K. 1981. A new approach to system diagnosis. In Proceedings of the 19th Allerton Conference on Communication, Control and Computing. 697--706.

[100]

Nassu, B. T., Duarte Jr., E. P., and Pozo, A. T. R. 2005. A comparison of evolutionary algorithms for system-level diagnosis. In Proceedings of the 7th ACM Genetic and Evolutionary Computation Conference. 2053--2060.

Digital Library

[101]

Pelc, A. 1991. Undirected graph models for system-level fault diagnosis. IEEE Trans. Comput. 40, 1271--1276.

Digital Library

[102]

Pelc, A. 1992. Optimal fault diagnosis in comparison models. IEEE Trans. Comput. 41, 6, 779--786.

Digital Library

[103]

Preparata, F., Metze, G., and Chien, R. T. 1967. On the connection assignment problem of diagnosable systems. IEEE Trans. Comput. 16, 848--854.

[104]

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

Digital Library

[105]

Raghavan, V. and Tripathi, A. R. 1991. Sequential diagnosability is co-NP-complete. IEEE Trans. Comput. 40, 5, 584--595.

Digital Library

[106]

Rangarajan, S., Dahbura, A. T., and Ziegler, E. A. 1995. A distributed system-level diagnosis algorithm for arbitrary network topologies. IEEE Trans. Comput. 44, 2, 312--333.

Digital Library

[107]

Rangarajan, S. and Fussell, D. 1988. A probabilistic method for fault diagnosis of multiprocessor systems. In Proceedings of the 18th IEEE Fault-Tolerant Computing Symposium. 278--283.

[108]

Rangarajan, S., Fussell, D., and Malek, M. 1990. Built-In testing of integrated circuits wafers. IEEE Trans. Comput. 39, 2, 195--205.

Digital Library

[109]

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

[110]

Sallay, B., Maestrini, P., and Santi, P. 1999. Wafer-scale diagnosis tolerating comparator faults. IEE Proc. Comput. Digital Techn. 146, 4, 211--215.

[111]

Sengupta, A. and Dahbura, A. T. 1992. On self-diagnosable multiprocessor systems: Diagnosis by comparison approach. IEEE Trans. Comput. 41, 11, 1386--1396.

Digital Library

[112]

Sengupta, A. and Rhee, C. 1990. On the diagnosability of systems with three valued test results: Diagnosis by comparison strategy. In Proceedings of the 20th International Symposium on Multiple-Valued Logic. 115--120.

[113]

Sheu, J.-J., Huang, W.-T., and Chen, C.-H. 2008. Strong diagnosability of regular networks under the comparison model. Inf. Process. Lett. 106, 1, 19--25.

Digital Library

[114]

Stahl, M., Buskens, R., and Bianchini, R. 1992. Simulation of the adapt on-line diagnosis algorithm for general topology networks. In Proceedings of the 11th IEEE Symposium on Reliable Distributed Systems.

[115]

Subbiah, A. and Blough, D. M. 2004. Distributed diagnosis in dynamic fault environments. IEEE Trans. Parallel Distrib. Syst. 15, 5, 453--467.

Digital Library

[116]

Sullivan, G. 1988. An O(t<sup>3</sup> + &vert;E&vert;) fault identification algorithm for diagnosable systems. IEEE Trans. Comput. 37, 4, 388--397.

Digital Library

[117]

Tamaki, H. 1998. Efficient self-embedding of butterfly networks with random faults. SIAM J. Comput. 27, 3, 614--636.

Digital Library

[118]

Tzeng, N. F. and Wei, S. 1991. Enhanced hypercubes. IEEE Trans. Comput. 40, 3, 284--294.

Digital Library

[119]

Vaidya, A. S., Rao, P. S. N., and Shankar, S. R. 1993. A class of hypercube-like networks. In Proceedings of the 5th IEEE Symposium on Parallel and Distributed Processing. 1, 4, 800--803.

[120]

Wang, D. 1999. Diagnosability of hipercubes and enhanced hypercubes under the comparison diagnosis model. IEEE Trans. Comput. 48, 12, 1369--1374.

Digital Library

[121]

Wang, H., Blough, D. M., and Alkalaj, L. 1994a. Analysis and experimental evaluation of comparison-based system-level diagnosis for multiprocessor systems. In Proceedings of the 24th IEEE Fault-Tolerant Computing Symposium. 55--64.

[122]

Wang, H., Blough, D. M., and Alkalaj, L. 1994b. Practical approach to comparison-based fault diagnosis in multiprocessor systems. International J. Comput. Syst. Sci. Engin. 9, 11--20.

[123]

Xu, J. and Huang, S. 1990. A new comparison-based scheme for multiprocessor fault tolerance. Microprocess. Microprogram. 30, 617--624.

[124]

Xu, J. and Randell, B. 1997. Software fault tolerance: t&sol;(n&minus;1)-Variant programming. IEEE Trans. Reliabil. 46, 1, 60--68.

[125]

Yang, C.-L. and Masson, G. M. 1987. An efficient algorithm for multiprocessor fault diagnosis using the comparison approach. Inf. Comput. 74, 1, 50--63.

Digital Library

[126]

Yang, H. and Yang, X. 2007. A fast diagnosis algorithm for locally twisted cube multiprocessor systems under the MM&ast; model. Comput. Math. Appl. 53, 6, 918--926.

Digital Library

[127]

Yang, X. 2003. A linear time fault diagnosis algorithm for hypercube multiprocessors under the MM&ast; model. In Proceedings of the 12th Asian Test Symposium. 50--55.

[128]

Yang, X. and Tang, Y. Y. 2007. Efficient fault identification of diagnosable systems under the comparison model. IEEE Trans. Comput. 56, 12, 1612--1618.

Digital Library

[129]

Yang, X. F., Evans, D. J., and Megson, G. M. 2004. Locally twisted cubes are 3-pancyclic. Appl. Math. Lett., 17, 8, 919--925.

[130]

Yang, X. F., Evans, D. J., and Megson, G. M. 2005a. The locally twisted cubes. Intl. J. Comput. Math. 82, 4, 401--413.

[131]

Yang, X. F., Megson, G. M., and Evans, D. J. 2005b. A comparison-based diagnosis algorithm tailored for crossed cube multiprocessor systems. Microprocess. Microsyst. 19, 4, 169--175.

[132]

Zheng, J., Latifi, S., Regentova, E., Luo, K., and Wu, X. 2002. Diagnosability of star graphs under the comparison diagnosis model. Inf. Process. Lett. 16, 1, 73--95.

[133]

Ziwich, R. P., Duarte Jr., E. P., and Albini, L. C. P. 2005. Distributed integrity checking for system with replicated data. In Proceedings of the 11th IEEE International Conference on Parallel and Distributed Systems. 363--369.

Digital Library

Cited By

Han YLi YYe C(2024)The cyclic diagnosability of balanced hypercubes under the PMC and MM⁎ modelTheoretical Computer Science10.1016/j.tcs.2024.1148161018(114816)Online publication date: Nov-2024
https://doi.org/10.1016/j.tcs.2024.114816
Otto ATilk C(2024)Intelligent design of sensor networks for data-driven sensor maintenance at railwaysOmega10.1016/j.omega.2024.103094127(103094)Online publication date: Sep-2024
https://doi.org/10.1016/j.omega.2024.103094
Hu JYang XYang L(2023)A Novel Diagnosis Scheme against Collusive False Data Injection AttackSensors10.3390/s2313594323:13(5943)Online publication date: 26-Jun-2023
https://doi.org/10.3390/s23135943
Show More Cited By

Recommendations

Undirected Graph Models for System-Level Fault Diagnosis

The author considers two comparison-based diagnosis models previously introduced by K.Y. Chwa et al. (1981) and M. Malek (1980). For each of them, classical t-diagnosability and probabilistic diagnosability based on the maximum likelihood principle are ...
Fault diagnosis for hypercube-like networks
AICT'11: Proceedings of the 2nd international conference on Applied informatics and computing theory

Diagnosis by comparison is a realistic approach to the fault diagnosis of multiprocessor systems. The MM* model is a comparison-based model from which each processor has to test another two processors if they are adjacent to it. Sengupta and Dahbura ...
The Comparison Approach to Multiprocessor Fault Diagnosis

In this correspondence a system-level, comparison-based strategy for identifying faulty processors in a multiprocessor system is described. Unlike other strategies which have been proposed in the literature, the comparison approach is more efficient and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Computing Surveys

ACM Computing Surveys Volume 43, Issue 3

April 2011

466 pages

ISSN:0360-0300

EISSN:1557-7341

DOI:10.1145/1922649

Issue’s Table of Contents

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 April 2011

Accepted: 01 October 2009

Revised: 01 October 2009

Received: 01 January 2008

Published in CSUR Volume 43, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Conselho Nacional de Desenvolvimento Científico e Tecnológico

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

51
Total Citations
View Citations
1,513
Total Downloads

Downloads (Last 12 months)18
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Han YLi YYe C(2024)The cyclic diagnosability of balanced hypercubes under the PMC and MM⁎ modelTheoretical Computer Science10.1016/j.tcs.2024.1148161018(114816)Online publication date: Nov-2024
https://doi.org/10.1016/j.tcs.2024.114816
Otto ATilk C(2024)Intelligent design of sensor networks for data-driven sensor maintenance at railwaysOmega10.1016/j.omega.2024.103094127(103094)Online publication date: Sep-2024
https://doi.org/10.1016/j.omega.2024.103094
Hu JYang XYang L(2023)A Novel Diagnosis Scheme against Collusive False Data Injection AttackSensors10.3390/s2313594323:13(5943)Online publication date: 26-Jun-2023
https://doi.org/10.3390/s23135943
Duarte ERodrigues LCamargo ETurchetti R(2023)The missing piece: a distributed system-level diagnosis model for the implementation of unreliable failure detectorsComputing10.1007/s00607-023-01211-8105:12(2821-2845)Online publication date: 18-Aug-2023
https://dl.acm.org/doi/10.1007/s00607-023-01211-8
Choudhary AKumar SSharma K(2022)RFDCS: A reactive fault detection and classification scheme for clustered wsnsPeer-to-Peer Networking and Applications10.1007/s12083-022-01308-515:3(1705-1732)Online publication date: 29-Mar-2022
https://doi.org/10.1007/s12083-022-01308-5
Swain RDash TKhilar P(2022)Automated Fault Diagnosis in Wireless Sensor Networks: A Comprehensive SurveyWireless Personal Communications10.1007/s11277-022-09916-3127:4(3211-3243)Online publication date: 3-Jul-2022
https://doi.org/10.1007/s11277-022-09916-3
Jarrah HAli GKumar AChong PSarkar NGutierrez J(2022)The Time-Free Comparison Model for Fault Diagnosis in Wireless Ad Hoc NetworksMobile Networks and Applications10.1007/s11036-020-01691-427:2(469-482)Online publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1007/s11036-020-01691-4
Chang NHsieh S(2020)Conditional Diagnosability of Alternating Group Networks Under the PMC ModelIEEE/ACM Transactions on Networking10.1109/TNET.2020.300209328:5(1968-1980)Online publication date: Oct-2020
https://doi.org/10.1109/TNET.2020.3002093
Ziwich RDuarte Jr ESilveira G(2020)Distributed mitigation of content pollution in peer‐to‐peer video streaming networksIET Communications10.1049/iet-com.2019.062714:11(1759-1767)Online publication date: Jul-2020
https://doi.org/10.1049/iet-com.2019.0627
Jarrah HChong PRapson CSarkar NGutierrez J(2020)A probabilistic comparison-based fault diagnosis for hybrid faults in mobile networksComputer Communications10.1016/j.comcom.2020.03.042Online publication date: Mar-2020
https://doi.org/10.1016/j.comcom.2020.03.042
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents