Conditional Diagnosability Of Multiprocessor System Based On Dual-Cubes

Fault tolerance is especially important for multiprocessor systems, since the growing size of the networks increases its vulnerability to component failures. Processor fault diagnosis plays an important role in multiprocessor systems for reliable computing, and the diagnosabilities of many well-known networks have been explored.In the introduction, we present the research significance and background of system level diagnosis theory, some common diagnosis models and different diagnosis strategies. There are four chapters in the thesis.The first chapter prepares some basic knowledge of the paper, it mainly introduces basis conceptions and notions of graph theory and combinatorial network theory. It also systematically introduces the architecture of multiprocessor as well as the differences between its two kinds of systems. Finally, it shows the construction and some basic properties of the network structure based on Dual Cube, which will be investigated in this thesis.The second chapter presents the fault tolerant analysis of Dual Cubes. Fault tolerant analysis is an important topic of interconnection networks studied today. Restricted connectivity has been proposed as an important parameter to estimate the fault tolerance of interconnection networks. This chapter presents characterization of fault tolerance on Dual Cube, which lays a foundation for diagnosability. In detail, this chapter studies restricted connectivity of Dual Cube DCn (n≥3), and establishes that κτ1(DCn)=2n and κτ2(DCn)=4n-4, respectively. Finally we also solve the generalized conditional connectivity of Dual Cube network DCn (n≥3), which will be for us to explore the generalized conditional diagnosability.The third chapter first prepares some lemmas, and then determines that the con-ditional diagnosability of Dual Cube DCn(n≥3) is tc(DCn)=4n-3. Finally, it also establishes that the generalized g-conditional diagnosability DCn is tg(DCn)=29(n+1-g)+29-1,0≤g≤n.Finally, Chapter four gives concluding remarks and proposes some constructive but unsolved problems.