Research On The T/k Diagnosis Policy And The Genetic Diagnosis Algorithm

The rapid development in technology has resulted in development of systems incorporating a large number of processors. The larger number of the processors makes it more complicated and expensive to find the faulty ones. Furthermore, the high reliability and maintainability of these systems, however, is always a major concern, which is especially a case in such fields as military application, financial management etc.. Thus, it is crucial to locate the faulty processors therein efficiently and then replace them with spare ones. The process of identifying faulty processors in a system by conducting tests on various processors and interpreting the test outcomes is known as the system-level diagnosis, whose popularity roots in its appealing features such as automatism, efficiency and economization.The thesis is focused on the field of faulty processor diagnosis of multicomputer system by means of the method of the classical system-level diagnosis. The research work involves the four topics: the t/k-diagnosability and diagnosis algorithm of enhanced hypercubes(k≤2), the t/k-diagnosability of locally twisted cubes, the diagnosis algorithm for BC graphs on the t/k-diagnosis strategy, and a genetic algorithm for the fault diagnosis of t-diagnosable system. The work in the present thesis is outlined in the following four respects:1. the t/k-diagnosability and diagnosis algorithm of enhanced hypercubesThe t/k-diagnosis strategy, is proposed by Somani and Peleg, can greatly increases the degree of diagnosability of some famous regular topologies at the cost of some fault-free nodes included in the fault-set. It has been shown that enhanced hypercubes have very good improvements over regular hypercubes in many measurements such as mean internode distance, diameter and traffic density and diagnosability. In the literature, the diagnosability of enhanced hypercubes has been explored under t-diagnosable system and t/k-diagnosable system (k =1), but no diagnosis algorithm is given. We first prove that an enhanced hypercube with a set F of at most 2n– 1 failing processors (while 2n– 3 for hypercube) has a component of size≥2~n– |F|– 1. We then prove that an enhanced hypercube with a set F of at most 3n– 3 failing processors (while 3n– 6 for hypercube) has a component of size≥2n– |F|– 2. Based on above results, we prove the t/k-diagnosability (k =2) of enhanced hypercubes with N nodes is...