Diagnosability Of Two Kinds Of Cubes

Diagnosability is defined as the maximum number of faulty processors which the sys-tem can guarantee to identify, which plays a role in measuring the reliability and the fault tolerance of interconnection networks. The concept of conditional diagnosability has been introduced by claiming the property that any faulty set cannot contain all neighbors of any processor in a system. The g-good-neighbor conditional diagnosability and the g-extra conditional diagnosability are two new diagnosabilities that have been introduced in recent years, which are more accurate than traditional diagnosability. Hypercube is a famous underlying topology of interconnection networks, n-dimensional folded hypercube FQ_n is obtained by adding some complementary edges from n-dimensional hypercube Q_n, n-dimensional hypercube Q_n and n-dimensional folded hypercube FQ_n are two of the most attractive interconnection networks of large scale multiprocessor systems. When we in-vestigate the fault diagnosis of a system, the PMC model and the MM model are widely adopted, where the MM* model is a special case of the MM model. In this paper, we mainly investigate the g-good-neighbor conditional diagnosability of n-dimensional hypercube Q_n under the MM* model and the g-extra conditional diagnosabilities of n-dimensional folded hypercube FQ_n under the PMC model and the MM* model. More details as follows:In the first chapter, we briefly introduce research background and research status, some concepts of graph theory, the definitions of n-dimensional hypercube and n-dimensional folded hypercube, and also two famous fault diagnosis models, i.e., PMC model and MM model.In the second chapter, we introduce the concept of g-good-neighbor conditional di-agnosability of multiprocessor systems, and prove that the g-good-neighbor conditional diagnosability of n-dimensional hypercube Q_n under the MM* model is (n - g+1)2~g - 1 for n≥ 5 and 0≤ g≤ n - 3.In the third chapter, we introduce the concept of g-extra conditional diagnosability of multiprocessor systems, and prove that the g-extra conditional diagnosability of n-dimensional folded hypercube FQ_n under the PMC model is (g+1)n - (2/g)+1 for n≥ 8 and 0≤ g< n ≤ 4. Meanwhile, we also show that the g-extra conditional diagnosability of n-dimensional folded hypercube FQ_n under the MM* model is (g+1)n - (2/g)+ 1 in some cases.