Top

Journal of Combinatorial Optimization

Published in:

01-10-2016

A diagnosis algorithm by using graph-coloring under the PMC model

Authors: Qiang Zhu, Guodong Guo, Wenliang Tang, Cun-Quan Zhang

Published in: Journal of Combinatorial Optimization | Issue 3/2016

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Fault diagnosis is important to the design and maintenance of large multiprocessor systems. PMC model is the most well known and widely studied model in the system level diagnosis of multiprocessor systems. Under the PMC model, a diagnosis algorithm based on some graph-coloring techniques has been proposed in this paper. Given a syndrome \(\sigma \), the first part of the algorithm can locate all the definitely faulty vertices. Then in the second part of the algorithm a diagnosis graph corresponding to the syndrome can be constructed and the suspicious faulty sets can be determined by finding the maximal independent sets of the diagnosis graph. A weight is assigned to each suspicious faulty vertex set which can measure its occurring probability. The algorithm is shown to be correct, not based on any conjecture and can be applied to the fault identification for any multiprocessor system.

previous article Packing feedback arc sets in reducible flow graphs

next article Efficient approximation schemes for the maximum lateness minimization on a single machine with a fixed operator or machine non-availability interval

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Barsi F, Grandoni F, Maestrini P (1976) A theory of diagnosability of digital systems. IEEE Trans Comput 100(6):585–593MathSciNetCrossRefMATH

Berthet GG, Nussbaumer HJ (1996) A unified theory for f1/f2-diagnosable communication networks. In: Dependable computing—EDCC-2. Springer, Berlin, Heidelberg, pp 421–438

Bondy JA, Murty USR (1976) Graph theory with applications, vol 290. Macmillan, London

Caruso A, Chessa S (2007) Worst-case diagnosis completeness in regular graphs under the pmc model. IEEE Trans Comput 56(7):917–924MathSciNetCrossRef

Caruso A, Chessa S, Maestrini P, Santi P (2002) Diagnosability of regular systems. J Algorithms 45(2):126–143MathSciNetCrossRefMATH

Dahbura AT, Sabnani KK, King LL (1987) The comparison approach to multiprocessor fault diagnosis. IEEE Trans Comput C–36(3):373–378CrossRef

Dahbura AT, Masson GM (1984) An 0\((n^{2.5}p)\) fault identification algorithm for diagnosable systems. IEEE Trans Comput C–33(6):486–492CrossRefMATH

Elbably ME (2005) Dynamic diagnosis algorithm to minimize the diagnosis complexity of digital systems. J Eng Appl Sci 52(4):753–763

Hakimi SL, Amin AT (1974) Characterization of connection assignment of diagnosable systems. IEEE Trans Comput 100(1):86–88MathSciNetCrossRefMATH

Harper LH (1966) Optimal numberings and isoperimetric problems on graphs. J Comb Theory 1(3):385–393MathSciNetCrossRefMATH

Krishnamoorthy MS, Krishnamurthy B (1987) Fault diameter of interconnection networks. Comput Math Appl 13(5–6):577–582MathSciNetCrossRefMATH

Lai PL, Tan JJ, Chang CP, Hsu LH (2005) Conditional diagnosability measures for large multiprocessor systems. IEEE Trans Comput 54(2):165–175CrossRef

Li TK, Tsai CH, Hsu HC (2012) A fast fault-identification algorithm for bijective connection graphs using the pmc model. Inf Sci 187:291–297MathSciNetCrossRefMATH

Liaw SC, Chang GJ (1999) Generalized diameters and Rabin numbers of networks. J Comb Optim 4:371–384MathSciNetMATH

Lombardi F (1986) Comparison-based diagnosis with faulty comparators. Electron Lett 22(22):1158–1160CrossRef

Manik M, Gramatová E (2009) Diagnosis of faulty units in regular graphs under the PMC model. In: 12th International symposium on design and diagnostics of electronic circuits & systems, 2009 (DDECS’09). IEEE, pp 202–205

Masson GM, Blough DM, Gregory GM (1996) System diagnosis. In: Fault-tolerant computer system design. Prentice-Hall, Inc., NJ, pp 478–536

Metze G, Preparata FP, Chien RT (1967) On the connection assignment problem of diagnosable systems. IEEE Trans Comput 6:848–854MATH

Meyer GGL, Masson GM (1978) An efficient fault diagnosis algorithm for symmetric multiple processor architectures. IEEE Trans Comput 100(11):1059–1063CrossRefMATH

Meyer GGL (1981) A fault diagnosis algorithm for asymmetric modular architectures. IEEE Trans Comput 100(1):81–83MathSciNetCrossRefMATH

Pelc A (1991) Undirected graph models for system-level fault diagnosis. IEEE Trans Comput 40(11):1271–1276MathSciNetCrossRef

Peng Y, Hong BR, Qiao YQ (2000) The characterization of t-diagnosable systems based on the generalized comparison model and a parallel algorithm for diagnosis. Chin J Comput 23(2):126–133MathSciNet

Rangarajan S, Fussell D (1991) Probabilistic diagnosis algorithms tailored to system topology. In: Twenty-first international symposium on fault-tolerant computing, 1991 (FTCS-21). Digest of papers. IEEE, pp 230–237

Rangarajan S, Fussell D (1992) Diagnosing arbitrarily connected parallel computers with high probability. IEEE Trans Comput 41(5):606–615CrossRef

Shi TL, Lu M (2012) Fault-tolerant diameter for three family interconnection networks. J Comb Optim 23:471–482MathSciNetCrossRefMATH

Wang H, Bian X, Ding F, Han G (2002) The application of a distributed system-level diagnosis algorithm in dynamic positioning system. In: Proceedings of the 4th world congress on intelligent control and automation, 2002, vol 3. IEEE, pp 2274–2278

Xiong W, Zhang Z, Lai HJ (2014) Spanning 3-connected index of graphs. J Comb Optim 27:199–208MathSciNetCrossRefMATH

Xuan HN, Zhang DF, Zhang M (2003) The equation diagnosis on pmc fault model. Acta Electron Sin 31(5):694–697MathSciNet

Yang H, Elhadef M, Nayak A, Yang X (2008) Network fault diagnosis: an artificial immune system approach. In: 14th IEEE international conference on parallel and distributed systems, 2008 (ICPADS’08). IEEE, pp 463–469

Yang XF (2004) A fast pessimistic one-step diagnosis algorithm for hypercube multicomputer systems. J Parallel Distrib Comput 64(4):546–553CrossRefMATH

Yang XF, Tang YY (2007) Efficient fault identification of diagnosable systems under the comparison model. IEEE Trans Comput 56(12):1612–1618MathSciNetCrossRef

Title: A diagnosis algorithm by using graph-coloring under the PMC model
Authors: Qiang Zhu
Guodong Guo
Wenliang Tang
Cun-Quan Zhang
Publication date: 01-10-2016
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 3/2016
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-015-9923-5

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 3/2016

The inverse 1-center problem on trees with variable edge lengths under Chebyshev norm and Hamming distance

Robustness of power-law networks: its assessment and optimization

Equitable colorings of Cartesian products of square of cycles and paths with complete bipartite graphs

Solving constrained optimization problems by solution-based decomposition search

Scheduling two job families on a single machine with two competitive agents

Characterisation of forests with trivial game domination numbers

Premium Partner