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

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