The Non-inclusion Diagnosability of Hypercubes Under the PMC Model

doi:10.1007/s40305-022-00421-9

Journal of the Operations Research Society of China ›› 2024, Vol. 12 ›› Issue (2): 478-484.doi: 10.1007/s40305-022-00421-9

Previous Articles Next Articles

The Non-inclusion Diagnosability of Hypercubes Under the PMC Model

Mei-Jie Ma¹, Min Xu², Tong-Tong Ding², Xiang-Jun Li³, Qiang Zhu⁴

1 School of Mathematics and Statistics, Qilu University of Technology (Shandong Academy of Sciences), Jinan 250353, Shandong, China;
2 School of Mathematical Sciences, Beijing Normal University, Laboratory of Mathematics and Complex Systems, Ministry of Education, Beijing 100875, China;
3 School of Information and Mathematics, Yangtze University, Jingzhou 434023, Hubei, China;
4 School of Mathematics and Statistics, XiDian University, Xi'an 710071, ShaanXi, China

Received:2020-12-20 Revised:2022-02-24 Online:2024-06-30 Published:2024-06-12
Contact: Min Xu, Mei-Jie Ma, Tong-Tong Ding, Xiang-Jun Li, Qiang Zhu E-mail:xum@bnu.edu.cn;mameij@sdu.edu.cn;dingtt@mail.bnu.edu.cn;franklxj@mail.ustc.edu.cn;qiangzhu@ustc.edu
Supported by:
This work was supported by the National Natural Science Foundation of China (Nos. 61672025, 60974082, 61179040 and 61075117), Shandong Provincial Natural Science Foundation (No. ZR2021MF012).

Abstract

Abstract: Diagnosability of a multiprocessor system is an important measure of the reliability of interconnection networks. System-level diagnosis is a primary strategy to identify the faulty processors in a multiprocessor system. Based on a sound assumption proposed by Zhu et al. recently, we proposed a new diagnosability named non-inclusion diagnosability and showed that the non-inclusion diagnosability t_N(Q_n) of the hypercube under the PMC model is 2n - 2. That is, assume that if two vertex sets F₁ and F₂ are both consistent with a syndrome and F₁ ⊂ F₂, then F₂ is not the faulty set which we are looking for; the faulty set F is 1-step diagnosable if |F| ≤2n - 2 in Q_n under the PMC model.

Key words: Interconnection network, Diagnosability, Hypercube, PMC model

CLC Number:

68M15

Mei-Jie Ma, Min Xu, Tong-Tong Ding, Xiang-Jun Li, Qiang Zhu. The Non-inclusion Diagnosability of Hypercubes Under the PMC Model[J]. Journal of the Operations Research Society of China, 2024, 12(2): 478-484.

TrendMD

References

[1] Maeng, J., Malek, M.:A comparison connection assignment for self-diagnosis of multiprocessors systems. In:Proceedings of 11th International Symposium on Fault-Tolerant Computing, pp. 173-175(1981)
[2] Preparata, F.P., Metze, G., Chien, R.T.:On the connection assignment problem of diagnosable systems. IEEE Trans. Comput. 16, 848-854(1967)
[3] Sengupta, A., Dahbura, A.T.:On self-diagnosable multiprocessor systems:diagnosis by the comparison approach. IEEE Trans. Comput. 41, 1386-1396(1992)
[4] Ahlswede, R., Aydinian, H.:On diagnosability of large multiprocessor networks. Discrete Appl. Math. 156, 3464-3474(2008)
[5] Chiang, C.-F., Hsu, G.-H., Shih, L.-M., Tan, J.J.:Diagnosability of star graphs with missing edges. Inform. Sci. 188, 253-259(2012)
[6] Gu, M.-M., Hao, R.-X., Zhou, S.:Fault diagnosability of data center networks. Theor. Comput. Sci. 776, 138-147(2019)
[7] Hsieh, S.-Y., Lee, C.-W.:Diagnosability of two-matching composition networks. In:Proceedings of the 14th Annual International Conference on Computing and Combinatorics. pp. 478-486(2008)
[8] Lian, G., Zhou, S., Hsieh, S.-Y., Liu, J., Chen, G., Wang, Y.:Performance evaluation on hybrid fault diagnosability of regular networks. Theor. Comput. Sci. 796, 147-153(2019)
[9] Lv, M., Zhou, S., Liu, J., Sun, X., Lian, G.:Fault diagnosability of DQcube under the PMC model. Discrete Appl. Math. 259, 180-192(2019)
[10] Song, S., Zhou, S., Li, X.:Conditional diagnosability of Burnt Pancake networks under the PMC model. Comp. J. 59, 91-105(2016)
[11] Stephens, J., Raghavan, V.:On single-fault set diagnosability in the PMC model. IEEE Trans. Comput. 42, 981-983(1993)
[12] Zhu, Q., Guo, G., Wang, D.:Relating diagnosability, strong diagnosability and conditional diagnosability of strong networks. IEEE Trans. Comput. 63, 1847-1851(2014)
[13] Ding, T.T., Xu, M., Zhu, Q.:The non-inclusive diagnosability of hypercubes under the MM*model. Int. J. Found. Comput. Sci. 31, 929-940(2020)
[14] Zhu, Q., Guo, G., Tang, W., Zhang, C.-Q.:A diagnosis algorithm by using graph-coloring under the PMC model. J. Comb. Optim. 32, 960-969(2016)
[15] Esfahanian, A.H.:Generalized measures of fault tolerance with application to n-cube networks. IEEE Trans. Comput. 38, 1586-1591(1989)
[16] Saad, Y., Schultz, M.H.:Topological properties of hypercubes. IEEE Trans. Comput. 37, 867-872(1988)
[17] Xu, J.-M.:Combinatorial Theory in Networks. Science Press, Beijing, China (2013)
[18] Li, X., Fan, J., Lin, C.-K., Jia, X.:Diagnosability evaluation of the data center network DCell. Comput. J. 61, 129-143(2018)
[19] Stewart, I.A.:A general technique to establish the asymptotic conditional diagnosability of interconnection networks. Theor. Comput. Sci. 452, 132-147(2012)
[20] Zhang, S., Yang, W.:The g-extra conditional diagnosability and sequential t/k-diagnosability of hypercubes. Int. J. Comput. Math. 93, 482-497(2016)
[21] Zhu, Q., Li, L., Liu, S., Zhang, X.:Hybrid fault diagnosis capability analysis of hypercubes under the PMC model and MM*model. Theor. Comput. Sci. 758, 1-8(2019)
[22] Armstrong, J.R., Gray, F.G.:Fault diagnosis in a boolean n-cube array of multiprocessors. IEEE Trans. Comput. 30, 587-590(1981)
[23] Dahbura, A.T., Masson, G.M.:An O (n^2.5) fault identification algorithm for diagnosable systems. IEEE Trans. Comput 33, 486-492(1984)
[24] Somani, A.K., Peleg, O.:On diagnosability of large fault sets in regular topology-based computer systems. IEEE Trans. Comput. 45, 892-903(1996)
[25] Yang, X., Cao, J., Megson, M., Luo, J.:Minimum neighborhood in a generalized cube. Inf. Process. Lett. 97, 88-93(2006)
[26] Yang, W., Lin, H.:Reliability evaluation of BC networks in terms of the extra vertex-and edgeconnectivity. IEEE Trans. Comput. 63, 2540-2548(2014)

The Non-inclusion Diagnosability of Hypercubes Under the PMC Model

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 2

Recommended Articles

Metrics

Comments

[1]	Yu-Long Wei, Tong-Tong Ding, Min Xu. The Non-Inclusive Diagnosability of Regular Graphs [J]. Journal of the Operations Research Society of China, 2023, 11(4): 891-910.
[2]	Yu-Long Wei, Min Xu. The g-Good-Neighbor Conditional Diagnosability of Locally Twisted Cubes [J]. Journal of the Operations Research Society of China, 2018, 6(2): 333-347.