Regular PapersNo Access

FAULT DIAGNOSIS OF MULTIPROCESSOR SYSTEMS BASED ON GENETIC AND ESTIMATION OF DISTRIBUTION ALGORITHMS: A PERFORMANCE EVALUATION

ELIAS P. DUARTE, Jr.

Department of Computer Science – Federal University of Parana, P.O. Box 19018 Curitiba, PR Brazil

Search for more papers by this author

AURORA T. R. POZO

Department of Computer Science – Federal University of Parana, P.O. Box 19018 Curitiba, PR Brazil

Search for more papers by this author

, and

BOGDAN T. NASSU

Department of Computer Science – Federal University of Parana, P.O. Box 19018 Curitiba, PR Brazil

Search for more papers by this author

https://doi.org/10.1142/S0218213010000017Cited by:6 (Source: Crossref)

Abstract

As faults are unavoidable in large scale multiprocessor systems, it is important to be able to determine which units of the system are working and which are faulty. System-level diagnosis is a long-standing realistic approach to detect faults in multiprocessor systems. Diagnosis is based on the results of tests executed on the system units. In this work we evaluate the performance of evolutionary algorithms applied to the diagnosis problem. Experimental results are presented for both the traditional genetic algorithm (GA) and specialized versions of the GA. We then propose and evaluate specialized versions of Estimation of Distribution Algorithms (EDA) for system-level diagnosis: the compact GA and Population-Based Incremental Learning both with and without negative examples. The evaluation was performed using four metrics: the average number of generations needed to find the solution, the average fitness after up to 500 generations, the percentage of tests that got to the optimal solution and the average time until the solution was found. An analysis of experimental results shows that more sophisticated algorithms converge faster to the optimal solution.

Keywords:

Remember to check out the Most Cited Articles!
Check out Notable Titles in Artificial Intelligence.

References

R. Armananzaset al., BioData Mining 1(6), (2008), DOI: 10.1186/1756-0381-1-6. Google Scholar
J. A. Lozano et al. (eds.) , Towards a new evolutionary computation: advances on estimation of distribution algorithms ( Springer-Verlag , 2006 ) . Crossref, Google Scholar
S. Baluja , Population-based incremental learning: A method for integrating genetic search based function optimization and competitive learning , Technical Report CMU-CS-94-163 ( Carnegie Mellon University , Pittsburgh, PA , 1994 ) . Google Scholar
S. Baluja and R. Caruana, Removing the genetics from the standard genetic algorithm, The International Conference on Machine Learning pp. 38–46. Google Scholar
R. P. Bianchini and R. Buskens, IEEE Transactions on Computers 41, 616 (1992), DOI: 10.1109/12.142688. Crossref, Web of Science, Google Scholar
A. Caruso, S. Chessa and P. Maestrini, IEEE Transactions on Computers 56(7), 917 (2007), DOI: 10.1109/TC.2007.1052. Crossref, Web of Science, Google Scholar
Y.-P. Chen et al. , A survey of linkage learning techniques in genetic and evolutionary algorithms ( University of Illinois , Urbana-Champaign , 2007 ) . Google Scholar
E. P. Duarte Jr. and T. Nanya, IEEE Transactions on Computers 47(1), 34 (1998), DOI: 10.1109/12.656078. Crossref, Web of Science, Google Scholar
E. P. Duarte Jr., A. Brawerman and L. C. P. Albini, An algorithm for distributed hierarchical diagnosis of dynamic fault and repair events, The 6th IEEE International Conference on Parallel and Distributed Systems (ICPADS) pp. 299–306. Google Scholar
E. P. Duarte Jr. and L. C. E. Bona, A dependable snmp-based tool for distributed network management, IEEE/IFIP International Conference on Dependable Systems and Networks (DSN) pp. 279–284. Google Scholar
E. P. Duarte Jr. and A. Weber, A distributed network connectivity algorithm, The 6th IEEE International Symposium on Autonomous Decentralized Systems (ISADS) pp. 285–292. Google Scholar
M. Elhadef and B. el Ayeb, An evolutionary algorithm for identifying faults in t-diagnosable systems, IEEE Symposium on Reliable Distributed Systems (SRDS) pp. 74–83. Google Scholar
M. Elhadef, L. B. Romdhane and B. Ayeb, International Journal of Parallel, Emergent and Distributed Systems 22(5), 387 (2007), DOI: 10.1080/17445760701207629. Crossref, Google Scholar
M. Elhadef, S. Das and A. Nayak, International Journal of Parallel, Emergent and Distributed Systems 20(2), 113 (2005), DOI: 10.1080/17445760500033374. Crossref, Google Scholar
M. Elhadef, S. Das and A. Nayak, Journal of Networks 1(5), 43 (2006), DOI: 10.4304/jnw.1.5.43-53. Google Scholar
M. Elhadefet al., Parallel Processing Letters 16(1), 63 (2006), DOI: 10.1142/S0129626406002472. Link, Google Scholar
M. Elhadef, A. Nayak and N. Zeng, Ants vs. faults: A swarm intelligence approach for diagnosing distributed computing networks, The 13th IEEE International Conference on Parallel and Distributed Systems (ICPADS) pp. 1–8. Google Scholar
S. L. Hakimi and A. T. Amin, IEEE Transactions on Computers 23, 86 (1974). Web of Science, Google Scholar
S. L. Hakimi and K. Nakajima, IEEE Transactions on Computers 33(3), 234 (1984). Web of Science, Google Scholar
G. R. Harik , Linkage learning via probabilistic modeling in the ecga ( University of Illinois , Urbana-Champaign , 1999 ) . Google Scholar
G. R. Harik, F. G. Lobo and D. E. Goldberg, IEEE Transactions on Evolutionary Computation 3(4), 287 (1998), DOI: 10.1109/4235.797971. Crossref, Web of Science, Google Scholar
S. H. Hosseini, J. G. Kuhl and S. M. Reddy, IEEE Transactions on Computers 33(3), 223 (1984). Web of Science, Google Scholar
G. Masson , D. Blough and G. Sullivan , Fault-Tolerant Computer System Design , System diagnosis , ed. D. K. Pradhan ( Prentice-Hall , 1996 ) . Google Scholar
B. T. Nassu, E. P. Duarte Jr. and A. T. R. Pozo, A comparison of evolutionary algorithms for system-level diagnosis, The 7th ACM Genetic and Evolutionary Computation COnference (GECCO) pp. 2053–2060. Google Scholar
M. Pelikan, D. E. Goldberg and E. Cantú-Paz, BOA: The Bayesian optimization algorithm, The 1st Genetic and Evolutionary Computation Conference (GECCO) pp. 525–532. Google Scholar
F. Preparata, G. Metze and R. Chien, IEEE Transactions on Electronic Computers 16(6), 848 (1967). Google Scholar
S. Rangarajan, A. T. Dahbura and E. A. Ziegler, IEEE Transactions on Computers 44, 312 (1995), DOI: 10.1109/12.364542. Crossref, Web of Science, Google Scholar
A. Subbiah and D. M. Blough, IEEE Transactions on Parallel Distributed Systems 15(5), 453 (2004), DOI: 10.1109/TPDS.2004.1278102. Crossref, Web of Science, Google Scholar
G. Khannaet al., IEEE Transactions on Dependable and Secure Computing 4(4), 266 (2007), DOI: 10.1109/TDSC.2007.70211. Crossref, Web of Science, Google Scholar
X. Yang and Y. Y. Tang, IEEE Transactions on Computers 56(12), 1 (2007). Google Scholar
A. Avizieniset al., IEEE Transactions on Dependable and Secure Computing 1(1), 11 (2004), DOI: 10.1109/TDSC.2004.2. Crossref, Web of Science, Google Scholar
C.-F. Chiang and J. J. M. Tan, IEEE Transactions on Computers 58(2), 251 (2009), DOI: 10.1109/TC.2008.158. Crossref, Web of Science, Google Scholar
H. Yanget al., Network fault diagnosis: an artificial immune system approach, The 14th IEEE International Conference on Parallel and Distributed Systems (ICPADS) pp. 463–469. Google Scholar