MM*模型下网络的限制局部可诊断性
Extra Local Diagnosability of Networks under the MM* Model
DOI: 10.12677/aam.2025.145244, PDF,    科研立项经费支持
作者: 郭慧铃, 张淑蓉*：太原理工大学数学学院，山西 太原
关键词: 局部诊断；MM*模型；限制故障模型；多处理器系统；Local Diagnosis； MM* Model； Restricted Fault Model； Multiprocessor System
摘要: 故障诊断对提升大规模网络可靠性意义重大。实际应用中，往往无需全局诊断，仅需确定信息传输区域内特定顶点(处理器)的工作状态。为此提出局部诊断方法，即设计包含特定顶点v的子网络，通过分析该子网络基于诊断模型得到的症状判断v是否故障。为保障故障网络局部连通性，引入h-限制故障模型，该模型要求移除所有故障顶点后网络的每个连通分量所含顶点数大于h。基于此，进一步提出h-限制局部可诊断性的概念，并给出在MM*模型下估计顶点v的限制局部可诊断性的充分条件，同时设计了包含顶点v的子网络结构 TM( v;h ) 。
Abstract: Fault diagnosis is crucial for improving the reliability of large-scale networks. In practice, it is often unnecessary to diagnose the entire network. Instead, determining the operational status of specific vertices (processors) within a particular information transmission region is more important. To address this, we propose a local diagnosis method that constructs a sub-network containing a specific vertex v. By analyzing the symptoms of this sub-network under a given diagnosis model, we can determine whether v is faulty. To ensure local network connectivity in the presence of faults, we introduce the h-extra fault model. This model requires that after removing all faulty vertices, each connected component of the network must have more than h vertices. Based on this, we further introduce the concept of h-extra local diagnosability. We provide sufficient conditions for estimating the extra local diagnosability of a vertex v under the MM* model and design a sub-network structure TM( v;h ) that includes vertex v.
文章引用：郭慧铃, 张淑蓉. MM*模型下网络的限制局部可诊断性[J]. 应用数学进展, 2025, 14(5): 153-161. https://doi.org/10.12677/aam.2025.145244

参考文献

[1] Dahbura, A.T. and Masson, G.M. (1984) An 0(n2.5) Fault Identification Algorithm for Diagnosable Systems. IEEE Transactions on Computers, 33, 486-492. [Google Scholar] [CrossRef] 
[2] Preparata, F.P., Metze, G. and Chien, R.T. (1967) On the Connection Assignment Problem of Diagnosable Systems. IEEE Transactions on Electronic Computers, 16, 848-854. [Google Scholar] [CrossRef] 
[3] Maeng, J. and Malek, M. (1981) A Comparison Connection Assignment for Self-Diagnosis of Multiprocessor Systems. In: Proceeding of the 11th International Symposium on Fault-Tolerant Computing, ACM Press, 173-175.
[4] 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] 
[5] Hsu, G. 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] 
[6] Chiang, C. 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] 
[7] Chen, M., Hsu, D.F. and Lin, C. (2022) A New Structure for a Vertex to Be Locally T-Diagnosable in Large Multiprocessor Systems. Theoretical Computer Science, 934, 81-90. [Google Scholar] [CrossRef] 
[8] Chen, M., Lin, C. and Pai, K. (2022) A Tree Structure for Local Diagnosis in Multiprocessor Systems under Comparison Model. In: Hsieh, S.Y., Hung, L.J., Klasing, R., Lee, C.W. and Peng, S.L., Eds., Communications in Computer and Information Science, Springer, 49-60. [Google Scholar] [CrossRef] 
[9] Lv, Y., Lin, C., Hsu, D.F. and Fan, J. (2024) An Algorithm for Conditional-Fault Local Diagnosis of Multiprocessor Systems under the MM⁎ Model. Theoretical Computer Science, 987, Article ID: 114372. [Google Scholar] [CrossRef] 
[10] Lin, C., Kung, T. and Tan, J.J.M. (2011) Conditional-Fault Diagnosability of Multiprocessor Systems with an Efficient Local Diagnosis Algorithm under the PMC Model. IEEE Transactions on Parallel and Distributed Systems, 22, 1669-1680. [Google Scholar] [CrossRef] 
[11] Lin, C., Kung, T. and Tan, J.J.M. (2013) An Algorithmic Approach to Conditional-Fault Local Diagnosis of Regular Multiprocessor Interconnected Systems under the PMC Model. IEEE Transactions on Computers, 62, 439-451. [Google Scholar] [CrossRef] 
[12] Lin, C., Teng, Y., Tan, J.J.M. and Hsu, L. (2013) Local Diagnosis Algorithms for Multiprocessor Systems under the Comparison Diagnosis Model. IEEE Transactions on Reliability, 62, 800-810. [Google Scholar] [CrossRef] 
[13] Lin, L., Huang, Y., Lin, Y., Hsieh, S. and Xu, L. (2021) FFNLFD: Fault Diagnosis of Multiprocessor Systems at Local Node with Fault-Free Neighbors under PMC Model and MM* Model. IEEE Transactions on Parallel and Distributed Systems, 33, 1739-1751. [Google Scholar] [CrossRef] 
[14] Yuan, J., Qiao, H., Liu, A. and Wang, X. (2022) Measurement and Algorithm for Conditional Local Diagnosis of Regular Networks under the MM* Model. Discrete Applied Mathematics, 309, 46-67. [Google Scholar] [CrossRef] 
[15] Lai, P., Tan, J.J.M., Chang, C. and Hsu, L. (2005) Conditional Diagnosability Measures for Large Multiprocessor Systems. IEEE Transactions on Computers, 54, 165-175. [Google Scholar] [CrossRef] 
[16] Fàbrega, J. and Fiol, M.A. (1996) On the Extraconnectivity of Graphs. Discrete Mathematics, 155, 49-57. [Google Scholar] [CrossRef] 
[17] Zhang, S. and Yang, W. (2016) The g-Extra Conditional Diagnosability and Sequential t/k-Diagnosability of Hypercubes. International Journal of Computer Mathematics, 93, 482-497. [Google Scholar] [CrossRef] 
[18] Lin, L., Hsieh, S., Xu, L., Zhou, S. and Chen, R. (2018) The Relationship between Extra Connectivity and Conditional Diagnosability of Regular Graphs under the PMC Model. Journal of Computer and System Sciences, 95, 1-18. [Google Scholar] [CrossRef] 
[19] Lin, L., Xu, L., Chen, R., Hsieh, S. and Wang, D. (2019) Relating Extra Connectivity and Extra Conditional Diagnosability in Regular Networks. IEEE Transactions on Dependable and Secure Computing, 16, 1086-1097. [Google Scholar] [CrossRef] 

为你推荐