Fault diagnosis at the system level is an important aspect in fault-tolerant computing systems consisting of a large number of interconnected processors. In this thesis, we are concerned with fault diagnosis of a system in which each unit is capable of testing other units.
As an approach to fault diagnosis in a system, we introduce a problem of determining in a system with n units whether at least one out of given m(≤n) units can be identified as faulty or fault-free provided the number of faulty units present does not exceed t. We characterize such an identifiable set of m units for m≤2.
For the simple characterization of an identifiable set, we propose a new matching, called S-matching, in a digraph as an extension of a matching and develop an algorithm for finding a maximum S-matching in a digraph. This algorithm can be applied to finding a maximum matching in a bipartite graph. The proposed S-matching techniques greatly simplify the characterization of an identifiable set U with $\mid{U}\mid$ ≤ 2.
Using the identifiable set U with $\mid{U}\mid≤2$, we investigate measures of diagnosability such as one-step t-diagnosability, sequential t-diagnosability, t/t-diagnosability and intermittent t-diagnosability. We present simplified characterizations of one-step t-diagnosable systems and t/t-diagnosable systems, and algorithms for determining these diagnosabilities for a given system. For the sequentially t-diagnosable systems which have not been fully characterized, we extend the sufficient conditions by constructing these systems. We also give an alternative characterization of intermittently t-diagnosable systems.
본 논문은 n개의 unit들로 구성되어 있고 각 unit는 다른 unit들을 test할 수 있는 시스템에서의 고장진단에 대하여 연구하였다. 고장진단의 새로운 접근 방법으로서 시스템에서 주어진 $m(≤n)$개의 unit들 중에서 적어도 하나는 고장인지 정상인지 알 수 있는 문제를 formulate하였다. 그래프의 matching의 확장된 개념으로서 방향 그래프에 있어서 일종의 tree matching인 S-matching을 정의하여 위의 문제에 대하여 m이 2보다 같거나 적을 때 필요 충분 조건을 제시하였다. 또한 maximum S-matching 알고리즘을 개발하므로써 위의 조건을 polynomial time에 check할 수 있음을 보였다. 이 필요 충분 조건을 이용하여 one-step t-고장진단도 (t-diagnosability), sequential t-고장진단도, t/t-고장진단도 및 intermittent t-고장진단도를 분석하였다. One-step t-고장진단 시스템과 t/t-고장진단 시스템에 대한 새로운 필요 충분 조건을 각각 제시하고 또 이 고장진단도를 찾는 알고리즘을 각각 제시하였다. 현재 필요 충분조건이 알려져 있지 않은 sequentially t-고장진단 시스템에 대해 충분 조건을 확장하고, intermittently t-고장진단 시스템에 대해서 새로운 필요 충분 조건을 구했다.
