有遗失边的k元n立方体在MM*模型下的局部诊断度
Local Diagnosability of k-Ary n-Cubes with Missing Edges under the MM* Model
摘要: 一个多重处理器系统的诊断度是一个非常重要的研究课题，它是度量多重处理器系统故障诊断的重要参数。作为重要的互连网络拓扑结构，k元n立方体具有许多良好的性质。在本文中，我们研究了k元n立方体Qnk(n≥3,k≥6)在MM*模型下的局部诊断度，证明了Qnk(n≥3,k≥6)即使存在2n-2条遗失边仍具有强局部诊断性，并且证明了2n-2是最优值。
Abstract: Diagnosability is an important research subject and parameter in measuring the fault diagnosis of multiprocessor systems. As a celebrated topology structure of interconnection networks, a k-ary n-cube Qnk has numerous great properties. In this paper, we study the diagnosability of k-ary n-cubes Qnk and demonstrate that Qnk(n≥3,k≥6) possesses the strong property even if there exist 2n-2 missing edges in it under the MM* model and the result is optimal with respect to the number of missing edges.
文章引用：王世英, 窦丰, 赵丽娜, 黄瑜. 有遗失边的k元n立方体在MM*模型下的局部诊断度[J]. 应用数学进展, 2022, 11(2): 790-803. https://doi.org/10.12677/AAM.2022.112084

参考文献

[1] Maeng, J. and Malek, M. (1981) A Comparison Connection Assignment for Self-Diagnosis of Multiprocessors Systems. Proceeding of the 11th International Symposium on Fault-Tolerant Computing, Portland, 24-26 June 1981, 173-175.
[2] Sengupta, A. and Dahbura, A.T. (1992) On Self-Diagnosable Multiprocessor Systems: Diagnosis by the Comparison Approach. IEEE Transactions on Computers, 41, 1386-1396. [Google Scholar] [CrossRef] 
[3] Dahbura, A.T. and Masson, G.M. (1984) An Fault Identification Algorithm for Diagnosable Systems. IEEE Transactions on Computers, C-33, 486-492. [Google Scholar] [CrossRef] 
[4] Fan, J.X. (2002) Diagnosability of Crossed Cubes under the Comparison Diagnosis Model. IEEE Transactions on Parallel and Distributed Systems, 13, 1099-1104. [Google Scholar] [CrossRef] 
[5] Gu, M.M., Hao, R.X., Feng, Y.Q. and Yu, A.M. (2017) The 3-Extra Connectivity and Faulty Diagnosability. The Computer Journal, 61, 672-686. [Google Scholar] [CrossRef] 
[6] Gu, M.M., Hao, R.X. and Zhou, S.M. (2019) Fault Diagnosability of Data Center Networks. Theoretical Computer Science, 776, 138-147. [Google Scholar] [CrossRef] 
[7] Lai, P.L., Tan, J.J.M., Chang, C.P. and Hsu, L.H. (2005) Conditional Diagnosability Measures for Large Multiprocessor Systems. IEEE Transactions on Computers, 54, 165-175. [Google Scholar] [CrossRef] 
[8] Hsu, G.H. and Tan, J.J.M. (2007) A Local Diagnosability Measure for Multiprocessor Systems. IEEE Transactions on Parallel and Distributed Systems, 18, 598-607. [Google Scholar] [CrossRef] 
[9] Chiang, C.F. and Tan, J.J.M. (2009) Using Node Diagnosability to Determine t-Diagnosability under the Comparison Diagnosis Model. IEEE Transactions on Computers, 58, 251-259. [Google Scholar] [CrossRef] 
[10] Chiang, C.F., Hsu, G.H., Shih, L.M. and Tan, J.J.M. (2012) Diagnosability of Star Graphs with Missing Edges. Information Sciences, 188, 253-259. [Google Scholar] [CrossRef] 
[11] Cheng, E. and Liptak, L. (2013) Dignosability of Cayley Graphs Generated by Transposition Trees with Missing Edges. Information Sciences, 238, 250-252. [Google Scholar] [CrossRef] 
[12] Cheng, E., Liptak, L. and Steffy, D.E. (2013) Strong Local Diagnosability of (n,k)-Star Graphs and Cayley Graphs Generated by 2-Trees with Missing Edges. Information Processing Letters, 113, 452-456. [Google Scholar] [CrossRef] 
[13] Wang, S.Y. and Ma, X.L. (2018) Diagnosability of Alternating Group Graphs with Missing Edges. Recent Advances in Electrical & Electronic Engineering, 11, 51-57. [Google Scholar] [CrossRef] 
[14] Wang, S.Y. and Ma, X.L. (2019) Diagnosability of Arrangement Graphs with Missing Edges under the MM* Model. International Journal of Parallel, Emergent and Distributed Systems, 35, 69-80. [Google Scholar] [CrossRef] 
[15] Zhou, Z.P., Wang, S.Y., Ma, X.L. and Ren, Y.X. (2019) Diagnosability of Expanded k-Ary n-Cubes with Missing Edges under the Comparison Model. International Journal of Parallel, Emergent and Distributed Systems, 35, 16-28. [Google Scholar] [CrossRef] 
[16] Feng, W. and Wang, S.Y. (2020) The Diagnosability of Wheel Networks with Missing Edges under the Comparison Model. Mathematics, 8, Article No. 1818. [Google Scholar] [CrossRef] 
[17] 樊畅畅, 王世英, 马晓蕾. 有遗失边的n维超立方体和折叠超立方体在MM*模型下的诊断度[J]. 应用数学进展, 2021, 10(1): 150-159.
[18] Wang, M., Jiang, S. and Wang, S.Y. (2021) Connectivity and Diagnosability of Center k-Ary n-Cubes. Discrete Applied Mathematics, 294, 98-107. [Google Scholar] [CrossRef] 
[19] Ashir, Y.A. and Stewart, I.A. (1997) On Embedding Cycles in k-Ary n-Cubes. Parallel Processing Letters, 7, 49-55. [Google Scholar] [CrossRef] 
[20] Bose, B., Broeg, B., Kwon, Y. and Ashir, Y. (1995) Lee Distance and Topological Properties of k-Ary n-Cubes. IEEE Transactions on Computers, 44, 1021-1030. [Google Scholar] [CrossRef] 
[21] Bettayeb, S. (1995) On the k-Ary Hypercube. Theoretical Computer Science, 140, 333-339. [Google Scholar] [CrossRef] 
[22] Bondy, J.A. and Murty, U.S.R. (2008) Graph Theory. Springer, New York.
[23] Lee, C.W. and Hsieh, S.Y. (2013) Diagnosability of multiprocessor systems. In: Scalable Computing and Communications: Theory and Practice, Wiley-IEEE Computer Society Press, New Jersey, USA.
[24] Yuan, J., Liu, A.X., Ma, X., Liu, X.L., Qin, X. and Zhang, J.F. (2015) The g-Good-Neighbor Conditional Diagnosability of k-Ary n-Cubes under the PMC Model and MM* Model. IEEE Transactions on Parallel and Distributed Systems, 26, 1165-1177. [Google Scholar] [CrossRef] 

为你推荐