Two-Round Probabilistic Diagnosis Algorithm for fault identification 两轮概率诊断算法用于故障识别

《Discrete Applied Mathematics》：Two-Round Probabilistic Diagnosis Algorithm for fault identification

　　

随着云计算、大数据与物联网技术的快速发展，分布式系统已成为处理海量数据与支撑高并发服务的关键技术。然而，系统架构日益复杂、网络环境动态多样，使得分布式系统面临节点故障、网络分区与数据不一致等挑战。为此，研究人员基于分层立方网络（Hierarchical Cubic Network, HCN）探索系统的容错性与自诊断性能，重点关注移除故障集F后网络分区数量与规模的关系。利用PMC模型，研究人员证明了HCN的1-额外r分量可诊断性，并提出一种基于PMC模型的两轮概率诊断算法（Two-Round Probabilistic Diagnosis Algorithm under the PMC model, 2RPDA-PMC）。研究人员对该算法的性能优势进行了评估与比较，并将其应用于多个真实网络数据集进行仿真实验，验证了其在故障检测与诊断方面的优越性。

该研究发表于《Discrete Applied Mathematics》，针对大规模并行分布式系统在故障诊断中仅考虑单一条件的不足展开。现有研究多集中于组件连通性或额外连通性，但往往只关注分区数量或分区规模，无法全面反映实际网络拓扑的容错与自诊断能力。为此，研究人员引入h-额外_r分量连通性与可诊断性概念，结合分区规模与数量双重指标，在分层立方网络上完成理论证明，并设计了2RPDA-PMC算法以提升诊断效率。

关键技术方法方面，研究人员采用图论中的连通性概念，包括h-额外_r分量连通性（h-extra r-component connectivity）与PMC模型（Preparata-Metze-Chien model）进行故障诊断分析。研究基于分层立方网络HCN_n，结合数学推导与仿真实验验证理论结果，并在真实数据中心网络BCube中进行应用测试，以评估算法的实用性与稳定性。

研究结果如下：

Preliminaries

研究人员介绍了图论与分层立方网络的基本定义，并详细阐述了PMC模型的原理，为后续理论分析与算法设计奠定基础。

Main results

研究人员证明了HCN_n的1-额外_r分量连通性分别为4n?4（r=3）和6n?10（r=4），并在PMC模型下计算出其1-额外_r分量可诊断性τ₂¹(HCN_n)=4n?3（n≥6），从而提供了更精确的容错性能评估标准。

Design of algorithm

研究人员设计了2RPDA-PMC算法，通过两轮概率诊断过程高效识别故障节点，显著提升了大规模分布式系统中的诊断速度与准确率。

Concluding remarks

研究总结了分层立方网络在故障集F移除后的分区特性，验证了所提算法的理论可行性与实际应用价值，并指出该方法可直接推广至其他网络拓扑结构。

讨论与结论部分，研究人员认为，1-额外_r分量连通性与可诊断性的引入弥补了传统单一指标的不足，能够更真实地反映网络在复杂环境下的鲁棒性。2RPDA-PMC算法在分层立方网络及BCube中的优异表现表明，其具备在实际数据中心环境中部署的潜力，有助于提升分布式系统的可靠性与故障响应能力。