In a multiprocessor system, as a key measure index for evaluating its reliability, diagnosability has attracted lots of attentions. Traditional diagnosability and conditional diagnosability have already been widely discussed. However, the existing diagnosability measures are not sufficiently comprehensive to address a large number of faulty nodes in a system. This article introduces a novel concept of diagnosability, called two-round diagnosability, which means that all faulty nodes can be identified by at most a one-round replacement (repairing the faulty nodes). The characterization of two-round t-diagnosable systems is provided; moreover, several important properties are also presented. Based on the abovementioned theories, for the n-dimensional hypercube Qn, we show that its two-round diagnosability is n2+n/2, which is n+1/2 times its classic diagnosability. Furthermore, a fault diagnosis algorithm is proposed to identify each node in the system under the PMC model. For Qn, we prove that the proposed algorithm is the time complexity of On2n.
展开▼
机译：在多处理器系统中，作为评估其可靠性的关键测量指标，诊断性吸引了大量的关注。已经广泛讨论了传统的诊断性和条件诊断性。但是，现有的诊断措施不够全面，以解决系统中大量故障的节点。本文介绍了一种新颖的诊断概念，称为两轮诊断性，这意味着所有故障的节点都可以通过最多的单轮替换（修复故障节点）来识别。提供了两轮T诊断系统的表征;此外，还提出了几个重要的属性。基于上述理论，对于N维超立体QN，我们表明其两轮诊断性是N2 + N / 2，其经典诊断的N + 1/2倍。此外，提出了故障诊断算法以在PMC模型下识别系统中的每个节点。对于QN，我们证明了所提出的算法是ON2N的时间复杂性。
展开▼
