超立方体在对称PMC模型下的g-好邻条件诊断度和g-额外条件诊断度

g-Good-Neighbor Conditional Diagnosability and g-Extra Conditional Diagnosability of Hypercubes Under Symmetric PMC Model

故障诊断在维持多处理器系统的可靠性中起到了至关重要的作用,而诊断度是系统诊断能力的一个重要度量参数。除经典诊断度外还有条件诊断度,如g-好邻条件诊断度、g-额外条件诊断度等。其中g-好邻条件诊断度是在每个无故障顶点至少有g个无故障邻点的条件下定义的一种条件诊断度,g-额外条件诊断度是在每个无故障分支包含超过g个顶点的条件下定义的一种条件诊断度。故障诊断需要在特定的诊断模型下进行,如PMC模型、对称PMC模型等。对称PMC模型是在PMC模型的基础上通过添加两个假设而提出的一种新的诊断模型。n维超立方体因具有多种优越性质而被研究者们广泛研究。目前有不少在PMC模型下的诊断度研究,但缺乏在对称PMC模型下的诊断度研究。文中首先证明了超立方体在对称PMC模型下的g-好邻条件诊断度的上界和下界,当n≥4且0≤g≤n-4时上界为2^(g+1)(n-g-1)+2^(g)-1,当g≥0且n≥max{g+4,2^(g+1)-2^(-g)-g-1}时下界为(2n-2^(g+1)+1)2^(g-1)+(n-g)2^(g-1)-1。还证明了超立方体在对称PMC模型下的g-额外条件诊断度的上界和下界,当n≥4且0≤g≤n-4时上界为2n(g+1)-5g-2C_(g)^(2)-2,当n≥4且0≤g≤min n-4,23 n时下界为3/2n(g+1)-g-5/2C_(g+1)^(2)-1。最后通过模拟实验验证了相关理论结果的正确性。

Fault diagnosis plays a very important role in maintaining the reliability of multiprocessor systems,and the diagno-sability is an important measure of the diagnosis capability of the system.Except for the traditional diagnosability,there are also conditional diagnosability,such as g-good-neighbor conditional diagnosability,g-extra conditional diagnosability,etc.Where g-good-neighbor conditional diagnosability is defined under the condition that every fault-free vertex has at least g fault-free neighbors,and g-extra conditional diagnosability is defined under the condition that every fault-free component contains more than g vertices.Fault diagnosis needs to be performed under a specific diagnosis model,such as PMC model,symmetric PMC model,in which the symmetric PMC model is a new diagnosis model proposed by adding two assumptions to the PMC model.The n-dimensional hypercube has many excellent properties,so it has been widely studied by researchers.At present,there are a number of diagnosability studies under the PMC models,but there is a lack of diagnosability studies under the symmetric PMC models.This paper first investigates the upper and lower bounds for the g-good-neighbor conditional diagnosability of hypercubes under the symmetric PMC model,with an upper bound of 2^(g+1)(n-g-1)+2^(g)-1 when n≥4 and 0≤g≤n-4 and a lower bound of(2n-2^(g+1)+1)2^(g)-1+(n-g)2^(g)-1-1 when g≥0 and n≥max{g+4,2^(g+1)-2-g-g-1}.Also study the upper and lower bounds for the g-extra conditional diagnosability of hypercubes under the symmetric PMC model,the upper bound is 2n(g+1)-5g-2C_(g)^(2)-2 when n≥4 and 0≤g≤n-4,and the lower bound is 3/2n(g+1)-g-5/2C_(g+1)^(2)-1 when n≥4 and 0≤g≤min{n-4,[2/3n]}.Finally,the correctness of the relevant theoretical conclusions is verified by simulation experiments.