Abstract: In order to evaluate the reliability and fault-tolerant ability of multi-processor system which takes hypercubes as underlying networks, combining the fact that structural faults often occur when the system is invaded by computer viruses, three-length-path structure connectivity and substructure connectivity of the n-cube network were investigated. Firstly, by using the three-length-path structure-cut of the n-cube network, an upper bound of three-length-path structure connectivity of the network was obtained. Secondly, by using an equivalent transformation or a reductive transformation of the three-length-path substructure-set of the n-cube network, a lower bound of three-length-path substructure connectivity of the network was obtained. Finally, combining with the property that three-length-path structure connectivity of a network is not less than its three-length-path substructure connectivity, it was proved that both three-length-path structure connectivity and substructure connectivity of a n-cube network were half of n. The results show that to destroy the enemy's multi-processor system which take the n-cubes as underlying networks under three-length-path structure fault model, at least half of n three-length-path structures or substructures of the system should be attacked.

Key words: multi-processor system, hypercube network, fault tolerance, reliability, structure connectivity

摘要： 针对以超立方体网络为蓝本的多处理机系统的可靠性和容错能力的精准度量问题，结合多处理机系统遭受计算机病毒攻击时常常发生结构性故障的特点，研究了n维超立方体网络的结构连通性和子结构连通性评价问题。首先，使用构造n维超立方体网络的3路结构割的方法得到其3路结构连通度的一个上界；然后，使用构造n维超立方体网络的3路子结构集的等价变换或约简变换的方法，得到其3路结构子连通度的一个下界；最后，利用任意网络的3路结构连通度不小于3路子结构连通度的性质，证实了超立方体网络的3路结构连通度和子结构连通度均为该超立方体网络维数的一半。这一结果表明，在3路结构故障模型下，破坏敌方以超立方体网络为底层拓扑的多处理系统至少需要攻击该系统中维数一半的3路结构或子结构。

关键词: 多处理机系统, 超立方体网络, 容错, 可靠性, 结构连通度