Necessary and sufficient conditions for <Emphasis Type="Italic">t</Emphasis>-diagnosability of multiprocessor computer systems for various models of nonreliable testing established using the system graph-theoretical model

Consideration was given to the graph-theoretical model of self-diagnosis at the system level under multiple permanent faults. A group of testing models based on complete unreliable tests was analyzed. For the models of this group, the necessary and sufficient conditions for t-diagnosability without repair were established. A critical review of the results obtained in the publications of various authors was given, and the noticed errors concerning the proof of the conditions for t-diagnosability without repair were corrected.     

Intermittent Fault Diagnosability of Interconnection Networks

An interconnection network’s diagnosability is an important metric for measuring its self-diagnostic capability. Permanent fault and intermittent fault are two different fault models that exist in an interconnection network. In this paper, we focus on the problem pertaining to the diagnosability of interconnection networks in an intermittent fault situation. First, we study a class of interconnection networks called crisp three-cycle networks, in which the cn _in -number (the number of common vertices each pair of vertices share) is no more than one. Necessary and sufficient conditions are derived for the diagnosability of crisp three-cycle networks under the PMC (Preparata, Metze, and Chien) model. A simple check can show that many well-known interconnection networks are crisp three-cycle networks. Second, we prove that an interconnection network S is a t _i -fault diagnosable system without repair if and only if its minimum in-degree is greater than t _i under the BGM (Barsi, Grandoni, and Masetrini) model. Finally, we extend the necessary and sufficient conditions to determine whether an interconnection network S is t _i -fault diagnosable without repair under the MM (Maeng and Malek) model from the permanent fault situation to the intermittent fault situation.     

Conditional diagnosability and strong diagnosability of shuffle-cubes under the comparison model

The growing size of multiprocessor systems increases the vulnerability to component failures. It is crucial to locate and replace faulty processors to maintain the system's high reliability. Processor fault diagnosis is essential to the reliability of a multiprocessor system and the diagnosabilities of many well-known networks (such as hierarchical hypercubes and crossed cubes [S. Zhou, L. Lin and J.-M. Xu, Conditional fault diagnosis of hierarchical hypercubes, Int. J. Comput. Math. 89(16) (2012), pp. 2152–2164 and S. Zhou, The conditional diagnosability of crossed cubes under the comparison model, Int. J. Comput. Math. 87(15) (2010), pp. 3387–3396]) have been investigated in the literature. A system is t-diagnosable if all faulty nodes can be identified without replacement when the number of faults does not exceed t, where t is some positive integer. Furthermore, a system is strongly t-diagnosable if it is t-diagnosable and can achieve (t+1)-diagnosability except for the case where a node's neighbours are all faulty. In addition, conditional diagnosability has been widely accepted as a new measure of diagnosability by assuming that any fault-set cannot contain all neighbours of any node in a multiprocessor system. In this paper, we determine the conditional diagnosability and strong diagnosability of an n-dimensional shuffle-cube SQ_n, a variant of hypercube for multiprocessor systems, under the comparison model. We show that the conditional diagnosability of shuffle-cube SQ_n (n=4k+2 and k≥2) is 3n?9, and SQ_n is strongly n-diagnosable under the comparison model.     

A new method to test system diagnosability

A new necessary and sufficient condition for t-diagnosability of a system is proposed. It is shown that the new scheme is computationally more efficient than the existing one for checking the diagnosability of a system.     

One-step t-fault diagnosis for hypermesh optical interconnection multiprocessor systems

To maintain high reliability and availability, system-level diagnosis should be considered for the multiprocessor systems. The self-diagnosis problem of hypermesh, emerging potential optical interconnection networks for multiprocessor systems, is solved in this paper. We derive that the precise one-step diagnosability of kⁿ-hypermesh is n(k − 1). Based on the principle of cycle decomposition, a one-step t-fault diagnosis algorithm for kⁿ-hypermesh which runs in O(kⁿn(k − 1)) time also is described.     

Partial and complete local diagnosis in computer systems with circulant structure

System diagnosis at multiple faults of multiplicity not greater than t is considered. The conditions when the state of each system module is only determined by the testing rusults of the physically connected modules (self-determination conditions) are analysed. The diagnosability conditions are established for the case when the self-determination conditions are not satisfied for any module. A new class of locally (t _r /t)-diagnosable systems is introduced, where t is the fault multiplicity and t _r is the multiplicity of faults at which the states of all system modules can be determined correctly and completely. The values of t _r are estimated. It is shown that the local t-diagnosability can be achieved by the system test redundancy.     

A necessary and sufficient condition for diagnosability of stochastic discrete event systems

Stochastic discrete event systems (SDES) are systems whose evolution is described by the occurrence of a sequence of events, where each event has a defined probability of occurring from each state. The diagnosability problem for SDES is the problem of determining the conditions under which occurrences of a fault can be detected in finite time with arbitrarily high probability. (IEEE Trans Autom Control 50(4):476–492 2005) proposed a class of SDES and proposed two definitions of stochastic diagnosability for SDES called A- and A A-diagnosability and reported a necessary and sufficient condition for A-diagnosability, but only a sufficient condition for A A-diagnosability. In this paper, we provide a condition that is both necessary and sufficient for determining whether or not an SDES is A A-diagnosable. We also show that verification of A A-diagnosability is equivalent to verification of the termination of the cumulative sum (CUSUM) procedure for hidden Markov models, and that, for a specific class of SDES called fault-immediate systems, the sequential probability ratio test (SPRT) minimizes the expected number of observable events required to distinguish between the normal and faulty modes.     

Three-valued diagnosable systems: Diagnosability,optimal design and fault identification algorithm

A three-valued model for computer system diagnosis is proposed in this paper. A subsystem is regurded as composed of two components, a task processor and a communication processor. Accordingly, subsystem faults are classified as type 1 or type 1/2 faults, representing subsystem faults with communication processors being faulty or those with communication processors being fault-free, The concepts of virtual tests andt ¹ /t ^1/2 fault diagnosis are introduced. Andt ¹ /t ^1/2 fault diagnosis with centralized control and that with distributed control are studied respectively. The problems addressed here include diagnosability, optimal design and fault identification algorithm. The results show clearly thatt ¹ /t ^1/2 fault diagnosis can afford to identify significantly more faults thant-fault diagnosis under the same structural constraint.     

On‐the‐Fly and Incremental Technique for Fault Diagnosis of Discrete Event Systems Modeled by Labeled Petri Nets

In this paper, we develop an on‐the‐fly and incremental technique for fault diagnosis of discrete event systems modeled by labeled Petri nets, in order to tackle the combinatorial explosion problem. K‐diagnosability, diagnosability, K_min (the minimum K ensuring diagnosability) and on‐line diagnosis are solved on the basis of the on‐the‐fly and incremental building of two structures, called respectively fault marking graph and fault marking set graph, in parallel. We build on existing results, namely those establishing necessary and sufficient conditions for diagnosability, but we bring mechanisms to make the checking of such conditions potentially more efficient. We show that, in general, analyzing or even building the whole reachability graph is unnecessary to analyze diagnosability and build an on‐line diagnoser. Our technique was implemented in a prototype tool called OF‐PENDA, and a railway level crossing benchmark is used to make a comparative discussion pertaining to efficiency in terms of time and memory relative to some existing approaches.     

Syndrome-decoding algorithms for static-diagnosis models

The problem of finding fault patterns consistent with a given syndrome is discussed for graph-theoretical diagnosis models such as the fault-diagnosis and self-diagnosis models. The fault-diagnosis model consists of two types of vertices, fault units and measurements, and is expressed by a bipartite graph. Faulty states of a fault unit always imply abnormal states of all the measurements which are adjacent to the unit, otherwise a measurement remains normal. A self-diagnosis model consists of one type of unit which has the capability of testing other units and being tested itself. The testing relation is represented by a directed arc; this produces test outcomes which are invalid if the testing unit is faulty. The inverse system which yields a fault pattern from a corresponding syndrome for fault-diagnosis models is studied and a syndrome-decoding algorithm is proposed which works for some class of diagnosis models with observation noise. The algorithm uses a similar measure to the syndrome-decoding algorithm of error-correcting codes which use the Hamming distance. Another measure is presented for the self-diagnosis model expressed by a directed graph and this measure is characterized by a ranking method.     

Conditional local self-regulation rules and a diagnostic algorithm for a multiprocessor system with circulant diagnostic structure based on these rules

We consider local testing on the system level for multiprocessor (modular) computational systems (CS) with multiple faults. CS has a circulant diagnostic structure. Outcomes of the tests performed by faulty units correspond to a well-known model of Preparata, Metze, and Chien. The testing problem is formulated as the problem of finding at least one actually operational unit with which one can diagnose the state of the system as a whole. We introduce the conditions for finding a set of units that includes all faulty units present in the system. We present a system self-testing algorithm. We show that using this algorithm, one can reach local t-diagnosability of a CS with circulant diagnostic structure for any number of units N and fault multiplicity t that satisfy N ≥ 2t + 1.     

基于MMD的故障可诊断性定量评价方法

提出一种基于最大均值差异(maximum mean discrepancy,MMD)的故障可诊断性定量评价方法.该方法无需构建任何系统模型,通过度量不同故障模式下测量数据之间的距离定量评价故障可诊断性,适用于结构复杂、不易于建模且能够获取测量数据的复杂系统.首先,将测量数据通过特征核映射到可再生核希尔伯特空间(reproducing kernel Hilbert space,RKHS)中,以MMD作为多元分布距离度量指标,将故障可诊断性定量评价问题转换为多元分布在RKHS中的距离度量问题;然后,利用数学推导分析测量噪声强度对故障可诊断性评价结果的影响;最后,通过仿真实例验证所提出方法的有效性.     

Design of light weight exact discrete event system diagnosers using measurement limitation: case study of electronic fuel injection system

Employing a state-based Discrete Event System (DES) modelling framework, this paper proposes a new fault diagnosis approach called measurement limitation-based abstract DES diagnosis (MLAD), which attempts to reduce state space complexity of the diagnosis process while simultaneously preserving full diagnosability. The MLAD approach carefully applies a set of distinct measurement limitation operations on the state variables of the original DES model based on fault compartmentalisation to obtain separate behaviourally abstracted DES models and corresponding abstract diagnosers with far lower state spaces. The set of measurement limitation operations are so designed that although, any single abstract diagnoser may compromise diagnosability in seclusion, the additive combination of all diagnosers running in parallel always ensures complete diagnosability. Effective measurement limitation also ensures that the combined state space of the abstract diagnosers is much lower than that of the single full diagnoser that may be derived from the original DES model. As a case study, we have employed MLAD to incorporate failure diagnosability in a practical electronic fuel injection system. Evaluations on standard practical benchmarks show that MLAD achieves significant reduction in state space as compared to conventional monolithic full diagnosis approaches.     

An analysis of self-diagnosis model by conditional fault set

Diagnosability and syndrome decoding of a self-diagnosis model is studied with a conditional fault set. The conditional fault set is a fault set which is induced under such a condition that some subset of units are faulty (or fault-free).The diagnosability defined on the model is generalized to include such information as (1) the maximum number of units to be identified as faulty; (2) the maximum number of units to be identified as fault-free; and (3) the maximum number of units whose states are definitely identified, when the upper bound on the number of faulty units is assumed.Furthermore, we discuss the problem of finding minimal fault set. This problem is formulated in mathematical programming with the conditional fault set. A syndrome decoding algorithm is also presented which uses the conditional fault set in a similar manner to Hamming distance used in syndrome decoding of error-correcting codes.     

An Online Diagnosable Fault-Tolerant Redundancy System

This paper presents an online diagnosable fault-tolerant system: N-unit t-fault tolerablesystem. The number of units N in the system can be either odd or even. The relationshipbetween N and t (the number of faulty units which can be tolerated) is presented. The approachof an optimum N- unit t-fault tolerable system is also given. As an example, a 4-unit 2-faulttolerable system is discussed. The reliability and mean time to failure of 4-unit 2-fault tolerablesystem are shown to be higher than 5MR (5-modular redundancy) and TMR (Triple ModulerRedundancy) system reliabilities. The amount of hardware components in a 4-unit t-faulttolerable system is simpler than 5MR. The complexity of switching circuit for N-unit t-faulttolerable system increases only linearly with respect of the number of modules. Our scheme isalso simpler than the hybrid redundancy system. Some theorems for the online diagnosis of N-unit t-fault systems are given and proved.     

控制系统可诊断性的内涵与研究综述

作为表征控制系统故障诊断能力的属性, 故障可诊断性揭示了故障诊断深层次的内涵.将可诊断性分析纳入控制系统与诊断方案的设计环节, 可以从根本上提高系统对故障的诊断能力, 为研究故障诊断提供新的思路.本文分别从可诊断性的内涵、研究现状以及潜在发展趋势三个角度系统地对可诊断性进行分析.首先, 从定义、影响因素、与已有概念的关系以及应用四个方面剖析了控制系统可诊断性的内涵和研究意义.其次, 分别从可诊断性评价与设计两个方面对可诊断性的研究现状进行分析.最后, 通过对可诊断性已有成果进行总结归纳, 探讨了可诊断性研究存在的不足以及未来发展的趋势.     

Diagnosability Analysis of Intermittent Faults in Discrete Event Systems Using a Twin-plant Structure

Most research in fault diagnosis of discrete event systems has been focused on permanent failures. However, experience with monitoring of dynamic systems shows that intermittent faults are predominant, and that their diagnosis constitutes one of the most challenging tasks for surveillance activities. Among the main existing approaches to deal with permanent faults, two were widely investigated while considering different settings: the Diagnoser based approach, and the Twin-plant based approach. The latter was developed to cope with some complexity limitations of the former. In the present paper, we propose a twin-plant based approach to deal with diagnosability of intermittent faults. Firstly, we discuss various notions of diagnosability, while considering the occurrence of faults, their recovery, and the identification of the system status. Then, we establish the necessary and sufficient conditions for each notion, and develop on-the-fly algorithms to check these properties. The discussed approach is implemented in a prototype tool that is used to conduct experiments on a railway control benchmark.

     

A novel sth‐order observer for linear system: Application to state and fault estimation of spacecraft control system

In this paper, a fault estimation problem for linear system is considered. A novel sth‐order observer is proposed to cope with this problem. The advantages of the proposed observer are that (i) the observer matching condition is not required to be satisfied in practical systems, (ii) if the sth derivative of fault is unknown and/or unbounded and the (s + 1)th derivative of fault f (t) is naught or bounded, it can simultaneously estimate the state and fault. The sufficient existence condition of the proposed observer is given by a linear matrix inequality. In addition, a feasible method to obtain the design parameters is discussed. Finally, two numerical examples are presented to illustrate the effectiveness of the proposed method.     

The conditional diagnosability of crossed cubes under the comparison model

The growing size of the multiprocessor systems increases their vulnerability to component failures. It is crucial to locate and replace the faulty processors to maintain the system's high reliability. The fault diagnosis is the process of identifying faulty processors in a system through testing. The conditional diagnosis requires that for each processor v in a system, all the processors that are directly connected to v do not fail simultaneously. In this paper, we show that the conditional diagnosability of the crossed cubes CQ _n under the comparison diagnosis model is 3n?5 when n≥7. Hence, the conditional diagnosability of CQ _n is three times larger than its classical diagnosability.