Fault tolerance of Möbius cubes under two forbidden fault set models

Abstract

An n-dimensional Möbius cube, 0MQ_n or 1MQ_n , is a variation of n-dimensional cube Q_n which possesses many attractive properties such as significantly smaller communication delay and stronger graph-embedding capabilities. In some practical situations, the fault tolerance of a distributed memory multiprocessor system can be measured more precisely by the connectivity of the underlying graph under forbidden fault set models. This article addresses the connectivity of 0MQ_n /1MQ_n under two typical forbidden fault set models. We first prove that the connectivity of 0MQ_n /1MQ_n is 2n − 2 when the fault set does not contain the neighborhood of any vertex as a subset. We then prove that the connectivity of 0MQ_n /1MQ_n is 3n − 5 provided that the neighborhood of any vertex as well as that of any edge cannot fail simultaneously. These results demonstrate that 0MQ_n /1MQ_n has the same connectivity as Q_n under either of the previous assumptions.

E-mail: [email protected]

Keywords:

• Multiprocessor system
• Möbius cube
• Fault tolerance
• Connectivity
• Forbidden fault set model

Acknowledgement

This research was supported by the Visiting Scholar's Funds of the National Education Ministry and the Key Laboratory of Electro-Optical Techniques and Systems, Chongqing University.

Notes

E-mail: [email protected]