PMC与MM^*模型下交叉立方体的非包含g好邻诊断度

The Non-Inclusive g-Good-Neighbor Diagnosability of Crossed Cubes under the PMC and MM^* Models

摘要: 多处理器系统的故障诊断是保障系统稳定运行的核心技术。g好邻条件限制每个无故障顶点都与至少g个无故障顶点相邻，非包含g好邻诊断度限制满足g好邻条件的故障集对互不包含。本文以n维交叉立方体$C{Q}_n$ 为研究对象，证明了在PMC模型下当$1\le g\le n-3$ 时$C{Q}_n$ 的非包含g好邻诊断度上界为$\left[2\left(n-g\right)+1\right]2^g-1$ ，当$n-2\le g\le n-1$ 时上界为$2^{n-1}-1$ ；在PMC模型下当$n\ge 4$ 时非包含1好邻诊断度为$4n-7$ 。在MM^*模型下当$n\ge 4$ 时$C{Q}_n$ 的非包含1好邻诊断度为$3n-5$ 。

Abstract: Fault diagnosis is a core technology to guarantee the stable operation of multiprocessor systems. The g-good-neighbor constraint requires every fault-free vertex to be adjacent to at least g fault-free vertices, while the non-inclusive constraint restricts that any pair of g-good-neighbor faulty sets cannot contain one another. This paper takes the n-dimensional crossed cube $C{Q}_n$ as the research object. Under the PMC model, we prove that the upper bound of the non-inclusive g-good-neighbor diagnosability of $C{Q}_n$ is $\left[2\left(n-g\right)+1\right]2^g-1$ for $1\le g\le n-3$ , and the upper bound is $2^{n-1}-1$ for $n-2\le g\le n-1$ . When $n\ge 4$ , the non-inclusive g-good-neighbor diagnosability of $C{Q}_n$ under the PMC model equals $4n-7$ . Under the MM^* model, the non-inclusive 1-good-neighbor diagnosability of $C{Q}_n$ is $3n-5$ where $n\ge 4$ .