AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Journal of Computer Science and Technology Article
Article Link
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Regular Paper

The t/s-Diagnosability and Diagnostic Strategy of Balanced Hypercube Under Two Classic Diagnostic Models

College of Mathematics and Statistics, Fujian Normal University, Fuzhou 350117, China
Center for Applied Mathematics of Fujian Province, Fujian Normal University, Fuzhou 350117, China
Department of Mathematics and Statistics, Oakland University, Rochester, MI 48309, U.S.A.
Show Author Information

Abstract

Fault diagnosis plays a crucial role in the fault tolerability assessment of an interconnection network, which is of great value in the design and maintenance of large-scale multiprocessor systems. A t/s-diagnostic strategy, as the generalization of the t/t-diagnostic strategy, refers to the self-diagnosis of a multiprocessor system in which all faulty vertices can be identified in a set of size at most s in the presence of at most t faulty vertices. In this work, we show that the balanced hypercube BHn(n⩾4) is ((2n+1)⌈g/2⌉−⌈g/2⌉2)/((2n+1)⌈g/2⌉−⌈g/2⌉2+(g−2))-diagnosable under both the Preparata, Metze, and Chien (PMC) and MM* models for 4⩽⌈g/2⌉⩽n. Moreover, we propose two effective t/s-diagnosis algorithms under the PMC and MM* models with time complexity O(NlogN) and O(N(logN)2) ( N=22n is the order of BHn), respectively. Finally, comparison results indicate that t/s-diagnosability strengthens the self-diagnosable capability of the system compared with traditional diagnosabilities.

Keywords

fault diagnosist/s-diagnosabilityt/s-diagnosis algorithmbalanced hypercube

Electronic Supplementary Material

Download File(s)
JCST-2208-12732-Highlights.pdf (154.3 KB)

References

[1]
Somani A K. System level diagnosis: A review. Technical Report, Dependable Computer Laboratory, Iowa State University, 1999. https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=1c29b953e0ff545d54b7cf2945bf182bdca26423, Jul. 2024.
[2]

Preparata F P, Metze G, Chien R T. On the connection assignment problem of diagnosable systems. IEEE Trans. Electronic Computers, 1967, EC-16(6): 848–854. DOI: 10.1109/PGEC.1967.264748.
Crossref Google Scholar
[3]
Maeng J, Malek M. A comparison connection assignment for self-diagnosis of multiprocessor systems. In Proc. the 11th International Symposium on Fault-Tolerant Computing, Jan. 1981, pp.173–175.
[4]

Chen C A, Chang G Y, Hsieh S Y. Conditional ( t, k)-diagnosis in graphs by using the comparison diagnosis model. IEEE Trans. Computers, 2015, 64(6): 1622–1632. DOI: 10.1109/TC.2014.2345407.
Crossref Google Scholar
[5]

Sengupta A, Dahbura A T. On self-diagnosable multiprocessor systems: Diagnosis by the comparison approach. IEEE Trans. Computers, 1992, 41(11): 1386–1396. DOI: 10.1109/12.177309.
Crossref Google Scholar
[6]
Friedman A D. A new measure of digital system diagnosis. In Proc. the 5th International Symposium on Fault-Tolerant Computing, Jan. 1975, pp.167–170.
[7]

Somani A K, Peleg O. On diagnosability of large fault sets in regular topology-based computer systems. IEEE Trans. Computers, 1996, 45(8): 892–903. DOI: 10.1109/12.536232.
Crossref Google Scholar
[8]

Fan J X, Lin X L. The t/k-diagnosability of the BC graphs. IEEE Trans. Computers, 2005, 54(2): 176–184. DOI: 10.1109/TC.2005.33.
Crossref Google Scholar
[9]

Zhou S M, Lin L M, Xu L, Wang D J. The t/k-diagnosability of star graph networks. IEEE Trans. Computers, 2015, 64(2): 547–555. DOI: 10.1109/TC.2013.228.
Crossref Google Scholar
[10]

Lin L M, Xu L, Zhou S M, Hsieh S Y. The t/k-diagnosability for regular networks. IEEE Trans. Computers, 2016, 65(10): 3157–3170. DOI: 10.1109/TC.2015.2512866.
Crossref Google Scholar
[11]

Liang J R, Zhang Q. The t/s-diagnosability of hypercube networks under the PMC and comparison models. IEEE Access, 2017, 5:5340–5346. DOI: 10.1109/ACCESS.2017.2672602.
Crossref Google Scholar
[12]

Liang J R, Zhang Q, Li H Y. Structural properties t/s diagnosis for star networks based on the PMC model. IEEE Access, 2017, 5:26175–26183. DOI: 10.1109/ACCESS.2017.2773144.
Crossref Google Scholar
[13]

Lin Y H, Lin L M, Huang Y Z, Wang J R. The t/s-diagnosability and t/s-diagnosis algorithm of folded hypercube under the PMC/MM* model. Theoretical Computer Science, 2021, 887:85–98. DOI: 10.1016/j.tcs.2021.07.006.
Crossref Google Scholar
[14]

Xie Y H, Liang J R, Yin W, Li C Z. The properties and t/s diagnosability of k-ary n-cube networks. The Journal of Supercomputing, 2022, 78(5): 7038–7057. DOI: 10.1007/s11227-021-04155-y.
Crossref Google Scholar
[15]

Wu J, Huang K. The balanced hypercube: A cube-based system for fault-tolerant applications. IEEE Trans. Computers, 1997, 46(4): 484–490. DOI: 10.1109/12.588063.
Crossref Google Scholar
[16]

Yang M C. Conditional diagnosability of balanced hypercubes under the PMC model. Information Sciences, 2013, 222:754–760. DOI: 10.1016/j.ins.2012.08.014.
Crossref Google Scholar
[17]

Yang M C. Conditional diagnosability of balanced hypercubes under the MM* model. The Journal of Supercomputing, 2013, 65(3): 1264–1278. DOI: 10.1007/s11227-013-0882-2.
Crossref Google Scholar
[18]

Wang X Y, Huang L J, Sun Q, Zhou N Q, Chen Y H, Lin W W, Li K Q. The g-extra diagnosability of the balanced hypercube under the PMC and MM* model. The Journal of Supercomputing, 2022, 78(5): 6995–7015. DOI: 10.1007/s11227-021-04126-3.
Crossref Google Scholar
[19]

Lin L M, Huang Y Z, Xu L, Hsieh S Y. A pessimistic fault diagnosability of large-scale connected networks via extra connectivity. IEEE Trans. Parallel and Distributed Systems, 2022, 33(2): 415–428. DOI: 10.1109/TPDS.2021.3093243.
Crossref Google Scholar
[20]

Gu M M, Hao R X, Yang D X. A short note on the 1, 2-good-neighbor diagnosability of balanced hypercubes. Journal of Interconnection Networks, 2016, 16(2): 1650001. DOI: 10.1142/S0219265916500018.
Crossref Google Scholar
[21]
Bondy J A, Murty U S R. Graph Theory. Springer, 2008.
Crossref
[22]
Yang M C, Yang M H. Reliability analysis of balanced hypercubes. In Proc. the 2012 Computing, Communications and Applications Conference, Jan. 2012, pp.376–379. DOI: 10.1109/ComComAp.2012.6154875.
Crossref
[23]
Zhang N P, Zhu Q. Extra connectivity and extra edge-connectivity of balanced hypercube. In Proc. the 2020 International Conference on Computer Information and Big Data Applications, Apr. 2020, pp.289–294. DOI: 10.1109/CIBDA50819.2020.00072.
Crossref
Journal of Computer Science and Technology
Volume 39 Issue 5,
September 2024
Pages 1207-1222
DOI: 10.1007/s11390-024-2732-5

{{item.num}}

Comments on this article

Go to comment

< Back to all reports

Review Status: {{reviewData.commendedNum}} Commended , {{reviewData.revisionRequiredNum}} Revision Required , {{reviewData.notCommendedNum}} Not Commended Under Peer Review

Review Comment

Cite this Report
Close
Close
Cite this article:
Liu X-Q, Zhou S-M, Cheng E, et al. The t/s-Diagnosability and Diagnostic Strategy of Balanced Hypercube Under Two Classic Diagnostic Models. Journal of Computer Science and Technology, 2024, 39(5): 1207-1222. https://doi.org/10.1007/s11390-024-2732-5

255

Views

1

Crossref

1

Web of Science

2

Scopus

0

CSCD

Altmetrics
Received: 09 August 2022
Accepted: 24 July 2024
Published: 05 December 2024
© Institute of Computing Technology, Chinese Academy of Sciences 2024