Connectivity And Diagnosability Of N-dimensional Crossed Cubes

Connectivity and diagnosability are important parameters in measuring the fault di-agnosis of multiprocessor systems. In order to maintain the reliability of the computer system, the fault processors in the system should be diagnosed and replaced by fault-free processors. The process of identifying the faulty processors is called the diagnosis of the system. Diagnosability is defined as the maximum number of faulty processors which the system can guarantee to identify, which plays a role in measuring the reliability and the fault tolerance of interconnection networks. In classical measures of system-level diagnos-ability, it has generally been assumed that the neighbor set of any processor may fail at the same time. However, the probability of this kind of failure is very small in large mul-tiprocessor systems. Therefore, Lai et al. proposed the conditional diagnosability of the network, which restrict any faulty set cannot contain all neighbors of any processor in a system. In 2012, Peng et al. proposed g-good-neighbor diagnosability that restrains every fault-free node containing at least g fault-free neighbors. In 2016, Zhang et al. proposed g-extra diagnosability, which requires that every fault-free component has at least (g+ 1)fault-free vertices. In 1996, J. Fabrega and M.A. Fiol introduced the g-extra connectivity,which is denoted by ?(g)(G). The n-dimensional crossed cube is an important variant of the hypercube. Preparata et al. first proposed a system level fault diagnosis model, called PMC model. It achieved the system diagnosis through two linked processors testing each other. Maeng and Malek proposed the MM model. In this model, a node sends the same task to two of its neighbors, and then compares their responses. Sengupta and Dahbura suggested a special case of the MM model, namely the MM* model and each node must test its any pair of adjacent nodes in the MM*. They also presented a polynominal algorithm for identifying faulty nodes in a system under the MM* model if the system is diagnosable.The following is the main content of this paper:In the first chapter, we briefly introduce research background and research status,some concepts of graph theory, the definitions of n-dimensional crossed cube CQn, and also two famous fault diagnosis models, i.e., PMC model and MM* model.In the second chapter, we first prove that the 1-good-neighbor connectivity of n-dimensional crossed cube CQn is 2n-2 for n?4. Then we also prove that the 1-good-neighbor diagnosability of n-dimensional crossed cube CQn is 2n -1 under the PMC model for n ? 4 and the MM* model for n ? 5.In the third chapter, we first prove that the 2-extra connectivity of n-dimensional crossed cube CQn is 3n-5 for n ? 5 and n-dimensional crossed cube CQn is tightly (3n-5)super 2-extra connected for n ? 5. Then we also prove that the 2-extra diagnosability of n-dimensional crossed cube CQn is 3n - 3 under the PMC model (n ? 5) and MM* model(n ? 6).In the fourth chapter, we first prove that the 2-good-neighbor connectivity of n-dimensional crossed cube CQn is 4n-8 for n?5 and n-dimensional crossed cube CQn is tightly (4n-8) super 2-good-neighbor connected for n?6. Then we also prove that the 2-good-neighbor diagnosability of n-dimensional crossed cube CQn is 4n -5 under the PMC model (n?5) and MM* model (n?5).In the fifth chapter, we first prove that the 3-extra connectivity of n-dimensional crossed cube CQn is 4n-9 for n ? 5 and n-dimensional crossed cube CQn is tightly(4n -9) super 3-extra connected for n ? 7. Then we also prove that the 3-extra diagnos-ability of n-dimensional crossed cube CQn is 4n-6 under the PMC model (n ? 5) and MM* model (n ? 7).