A Study of (t k)-Diagnosis Algorithms for Regular and Irregular Networks

Abstract

System-level diagnosis is a process of identifying faulty processors in a system by performing a number of tests among processors and interpreting the test results Di- agnosis model diagnosis strategy diagnosis algorithm and diagnosability are four important issues in system-level diagnosis In this dissertation we focus on the (t k)-diagnosis strategy MM* and PMC model (t k)-diagnosis algorithm and (t k)-diagnosability for some multiprocessor systems Assume that there are at most t faulty vertices A system is called random (t k)-diagnosable (or conditionally (t k)-diagnosable) if at least k faulty vertices can be identi?ed in each iteration under the assumption that there is no any restriction on the fault distribution (or every vertex is adjacent to at least one fault-free vertex) provided there are at most t faulty vertices where When the remaining the number of faulty vertices are fewer than k all of them can also be identifed Let (G) be the conditional vertex connectivity of G which measures the vertex connectivity of G according to the assumption that every vertex is adjacent to at least one fault-free vertex Let (G) be the maximum degrees of the given graph G When a graph G satisfes the condition that for each neighbor v1 of vertex u in G there is another neighbor v2 of u such that v1 and v2 have at least two common neighbors in G we show the following two results: 1) An r-regular network G containing N vertices is conditionally -diagnosable By applying the above results to multiprocessor systems we can measure conditional (t k)-diagnosabilities for augmented cubes folded hypercubes balanced hypercubes and exchanged hypercubes Under the PMC model we consider the (t k)-diagnosability of a hypercube under the random fault model and conditional fault model respectively We show that the sequential t-diagnosis algorithm for hypercube proposed by [62] can be extended to the (t k)-diagnosis algorithm for hypercube and we show that the n-dimensional hyper-cubes are random -diagnosable if n is even and random -diagnosable if n is odd where Moreover we propose a conditional (t k)-diagnosis algorithm for hypercubes by using some property of conditional fault model and show that the n-dimensional hypercubes are conditional -diagnosable if n is even and conditional -diagnosable if n is odd Furthermore under the PMC model our results improve the previous best low bounds on t under the random and conditional fault models respectively

Date of Award	2017 Feb 3
Original language	English
Supervisor	Sun-Yuan Hsieh (Supervisor)