# Failure Diagnosis for Distributed Stochastic Discrete Event Systems

Authors: Xuena Geng; Dantong Ouyang; Xiangfu Zhao
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

Because of the complexity of the failure diagnosis for large-scale discrete event systems (DESs), DESs with decentralized information have received a lot of attention. DESs with communication events are defined as distributed DESs. Stochastic discrete event systems (SDESs) are DESs with a probabilistic structure. A-diagnosability is an important property in failure diagnosis of SDES. In this paper, we investigate A-diagnosability in distributed SDESs. We define a local model and global model. Moreover, we construct a synchronized stochastic diagnoser to check A-diagnosability in distributed SDESs. We also propose a necessary and sufficient condition for a distributed SDES to be A-diagnosable. Some examples are described to illustrate our algorithms.


---

## Body

## 1. Introduction

Discrete event system (DES) is a discrete-state, event-driven system, the states evolution of which depends entirely on the occurrence of asynchronous discrete events over time. Failure diagnosis of DES has received considerable attention to guarantee the performance of a reliable system [1–5]. Most of the previous work concerned the DES as a global system, where there is only a site for collecting all the information about the system [1, 2]. However, in many complex systems, such as communication networks, power systems, and manufacturing systems, information is decentralized among many physically separated sites [6]. According to the decentralized information, the global system can be partitioned into a set of local models.DESs with decentralized information can be classified into distributed DESs [3, 7, 8] and decentralized DESs [4, 9]. Meanwhile, the methods of diagnosis are classified into distributed diagnosis and decentralized diagnosis. The distinction is not exactly between distributed DESs and decentralized DESs in the previous literature. In this paper, the difference between distributed DESs and decentralized DESs is summarized as follows: in distributed DESs, the local models communicate with each other by the communication events between them; however, communication events do not exist between the local models in decentralized DESs, and a coordinator is constructed to exchange the local diagnosis information. Briefly speaking, the diagnosis is performed locally in distributed DESs. Figures 1 and 2, respectively, depict the procedures of verifying diagnosability in distributed DESs (Algorithm 1) and decentralized DESs.Algorithm 1:VerDia: verifying A-diagnosability of distributed SDES.
inputs: local models {G1,…,Gm};
output: A-diagnosability;
(1)for all Gi∈{G1,…,Gm}  do
(2)Gid = ConDia(Gi)
(3)if  Gid satisfies Theorem 10  then
(4)returnf is A-diagnosable
(5)else
(6)n=1
(7)while  (n≤m)  do
(8)for  all G⊆{G1,…,Gm}∖{Gi}∧G=n  do
(9)Gsd = ConSSDia(Gi, G)
(10)if  Gsd satisfies Theorem 17  then
(11)return   f is A-diagnosable
(12)end for
(13)n++
(14)end while
(15)return  f is not A-diagnosable
(16)end forFigure 1
Verifying diagnosability in distributed DESs.Figure 2
Verifying diagnosability in decentralized DESs.To deal with the diagnosis problem of DESs precisely, stochastic discrete event systems (SDESs) were proposed by Lunze and Schroder [10]. SDESs extend DESs by probabilistic transitions. A-diagnosability is an important property in failure diagnosis of SDES. References [11–13] have investigated A-diagnosability in SDESs. In some complex SDESs, the information is also decentralized. Inspired by the DESs with decentralized information, SDESs with decentralized information are partitioned into decentralized SDESs and distributed SDESs. Failure diagnosis in decentralized SDESs was investigated in [14, 15]. However, the previous literature only focused on the decentralized SDESs. The approach for diagnosis in decentralized SDESs is not adapted to the distributed SDESs, because the structure of distributed SDESs is different from that of the decentralized SDESs. Distributed SDESs exchange the local diagnosis information by the communication events. In this paper, we contributed by checking A-diagnosability in distributed SDESs. We define the local models in distributed SDESs and verify the A-diagnosability in local models. Furthermore, we propose a synchronized stochastic diagnoser to diagnose the failure events which are not A-diagnosable in the local models. Based on the synchronized stochastic diagnoser, we describe a necessary and sufficient condition for a distributed SDES to be A-diagnosable.This paper is organized as follows. Some definitions and frequently used terms are introduced in Section2. In Section 3, A-diagnosability in distributed SDES is presented. In Section 4, we construct a synchronized stochastic diagnoser and propose a necessary and sufficient condition for a distributed SDES to be A-diagnosable. We give an example to illustrate the condition of the A-diagnosability for distributed SDES in this section. In Section 5, we analyze the complexity of the algorithm. Section 6 describes the related work. Finally, Section 7 presents a summary of the results in the paper and gives the concluding remarks.


## 2. Preliminaries

In this section, we review some definitions and frequently used terms of SDES, A-diagnosability, and stochastic diagnoser.


### 2.1. SDES

We first introduce some basic concepts in SDES. SDES is usually modeled as astochastic automaton (SA), which is a finite state machine with probabilistic structure [12].Definition 1 (SA).
An SA is defined as a tupleG=(X,Σ,p,x0), where X is the state space, Σ is the set of events, p:X×Σ×X→[0,1] is the partial state transition probability function, and x0 is the initial state of the SDES.The event setΣ is partitioned as Σ=Σo∪Σuo, where Σo and Σuo denote the sets of observable and unobservable events, respectively. Note that Σf⊆Σuo⊆Σ denotes the set of failure events to be diagnosed. Let Σ∗ denote the set of all sequences formed by events in Σ, including ε (empty event). The behavior of the system is described by the prefix-closed language L, where L is a subset of Σ∗. Apath denotes an arbitrary element of L. Suppose s is a path of G; projection Pj(s) removes the unobservable events from s. Formally, projection is defined as follows [1].Definition 2 (projection).
A projectionPj:Σ∗→Σo∗ is defined as Pj(ε)=ε, for any e∈Σ, s∈Σ∗, Pj(se)=Pj(s)Pj(e), where(1)Pje=eife∈Σoεotherwise.The inverse operation of projection isPjL-1(s0)={s∈L:Pj(s)=s0}. L/s denotes the set of possible continuations of a path s. Let |s| represent the number of events in s.According to different failure types, the set of failure events can be partitioned into disjoint sets; that is,Σf=Σf1∪⋯∪Σfm. Let sf denote the final event of a path s. Define(2)ΨΣfi=s∈L:sf∈Σfi.The result of functionΨ(Σfi) represents the set of paths whose final event is the failure event of a specific type. Hereafter, Fi denotes the failure events whose type is Σfi. For the sake of simplicity, we introduce our algorithms by the systems with only a single failure type. In Section 4, we extend our algorithms to multiple failure types.In SA,p(x,e,x′) is a state transition probability of the system evolution from x to x′ driven by event e, where x,x′∈X, and e∈Σ. To facilitate the solution to the diagnosis problems, we formulate three assumptions about the transition probability [1, 12]:(A1)
At most onex′∈X exists, such that p(x,e,x′)>0 for a given x∈X and a given e∈Σ.(A2)
For every state inX, the probability of a transition occurring from that state is one or, equivalently, ∀x∈X,(3)∑x′∈X∑e∈Σpx,e,x′=1.(A3)
There does not exist any cycle of unobservable events; that is,(4)s∈Σuo∗⟹s≤n0∃n0∈N∀ust∈L.Intuitively, assumptions (A1) and (A2) indicate that transitions will continue to occur in any state. Assumption (A3) ensures that the DES does not exhibit an arbitrarily long path of unobservable events.The probability transition function presents the probability of the partial transition function, which is defined astran:X×Σ→X, where(5)tranx,e=x′⟹px,e,x′>0.Ifp(x,e,x′)=0, then tran(x,e) is undefined. Furthermore, the transition function can be extended to the sequence of events as follows:(6)tranx,se=trantranx,s,e.Particularly,tran(x,ε)=x.The probability of a sequence between two states is defined asps:X×Σ∗×X→[0,1]. For example, the probability from xm to xj through path e1e2 can be calculated as(7)psxm,e1e2,xj=pxm,e1,xipxi,e2,xj,where tran(xm,e1)=xi.On the basis of (7), the probability of a path, which is from state x to x′, can be calculated recursively as follows:(8)psx,se,x′=psx,s,tranx,sptranx,s,e,x′.Following [12], if no confusion results, Pr(e∣x) and Pr(se∣x) can be denoted by Pr(e) and Pr(se), respectively.Example 3.
Consider the SAG represented in Figure 3 and let s=fo1. Thus, the probability of s from state 0 to 1 is ps(0,s,1)=0.1×0.2=0.02. We suppose t=u1o1n, and then Pr(st∣0)=0.02×0.8×1n=0.016.Figure 3
An SAG, where the observable events set is Σo={o1}, Σuo={u1,f}, and the failure events set is Σf={f}.


### 2.2. A-Diagnosability and Stochastic Diagnoser of SDES

The approach for distributed diagnosis is based on the related definitions in [12]. In this subsection, we review the definitions of A-diagnosability and stochastic diagnoser of SDES in [12].Assessing the diagnosability of a system is crucial in diagnosis. The definition of diagnosability in DES was proposed in [1]. However, diagnosability cannot distinguish between paths highly probable and less probable. Therefore, A-diagnosability was proposed in [12]. A-diagnosability requires an error bound ϵ and a delay bound n such that, for any failure path, its extensions, which are longer than n, occur with a probability smaller than ϵ [12].Definition 4 (A-diagnosability).
A live, prefix-closed languageL is Fi-A-diagnosable with respect to a projection Pj and a set of transition probabilities p if(9)Prt:Dst=0∣t∈Ls∧t=n<ϵ∀ϵ>0∃N∈N∀s∈ΨΣfi∧n≥N,where the diagnosability condition function D is as follows:(10)Dst=1ifω∈PjL-1Pjst⟹Σfi∈ω0otherwise.In (9), path s ends with a failure event whose type is Σfi. t is an arbitrary sufficiently long continuation of s. L is not logical diagnosable (referred to as diagnosability in [1]). L is Fi-A-diagnosable,if and only if (iff) the probability of t is smaller than ϵ.An SA is A-diagnosable iff every failure eventf in SA is A-diagnosable.Example 5.
Consider the SDESG in Figure 3 as an example; the path s=f∈Ψ(Σf1). We take ϵ = 0.1. The continuation of s is t=o1n or t=u1o1n-1. For both continuations, we have Pj(st)=o1n. However, the inverse projection PjL-1(o1n)={fo1n-1,fu1o1n-2,o1n}. Therefore, D(st) = 0. When t=u1o1n-1, the probability of t is Pr(u1o1n-1)=0.8×1n-1=0.8>ϵ. We can conclude that f is not A-diagnosable in G.A necessary and sufficient condition was proposed to check the A-diagnosability of the failure events in [12]. The condition is based on stochastic diagnoser. Stochastic diagnoser, which is used either online or offline to describe the behavior of the stochastic system G, is constructed as follows [12].Definition 6 (stochastic diagnoser).
A stochastic diagnoser is defined as a tupleGd=(Xd,Σo,pd,x0d,Φ,ϕ0), where Xd is the set of logical elements with the initial logical element x0d={(x0,N)}, Σo is the set of observable events, pd is the transition function of the stochastic diagnoser, Φ is the set of probability transition matrices, and ϕ0 is the initial probability mass function on x0d.More details of the stochastic diagnoser can be found in [12]. Figure 4 shows the stochastic diagnoser Gd of the SDES G in Figure 3. Two logical elements exist in Gd; that is, x0d={(0,{N})} and x1d={(1,{F}),(2,{F}),(3,{N})}. {(0,{N})} is the initial logical element. Let (1,{F}) denote a component of x1d. If all the components in a logical element xd bear Fi, then xd is Fi-certain. Otherwise, xd is Fi-uncertain. x1d is an F-uncertain logical element.Figure 4
A stochastic diagnoserGd.The condition of A-diagnosability is based on the theory of Markov chains. Letx and y be states of a Markov chain. ρxy (0<ρxy≤1) represents the probability that if the Markov chain is in state x, it will go back to state y at some point in the future. If ρxx=1, then x is called a recurrent state. Otherwise, x is called a transient state.The condition for a languageL to be A-diagnosable is described as follows.Theorem 7 (see [12]).
A language L generated by an SA G isFi-A-diagnosable iff every logical element of its stochastic diagnoser Gd containing a recurrent component bearing the label Fi is Fi-certain.The proof of Theorem7 can be found in [12].We conclude this section with an example that illustrates the stochastic diagnoser in Figure4. Components (2,{F}) and (3,{N}) are two recurrent components in x1d. Moreover, (2,{F}) is a recurrent component bearing failure event. However, x1d={(1,{F}),(2,{F}),(3,{N})} is F-uncertain. Therefore, f is not A-diagnosable in G.


## 2.1. SDES

We first introduce some basic concepts in SDES. SDES is usually modeled as astochastic automaton (SA), which is a finite state machine with probabilistic structure [12].Definition 1 (SA).
An SA is defined as a tupleG=(X,Σ,p,x0), where X is the state space, Σ is the set of events, p:X×Σ×X→[0,1] is the partial state transition probability function, and x0 is the initial state of the SDES.The event setΣ is partitioned as Σ=Σo∪Σuo, where Σo and Σuo denote the sets of observable and unobservable events, respectively. Note that Σf⊆Σuo⊆Σ denotes the set of failure events to be diagnosed. Let Σ∗ denote the set of all sequences formed by events in Σ, including ε (empty event). The behavior of the system is described by the prefix-closed language L, where L is a subset of Σ∗. Apath denotes an arbitrary element of L. Suppose s is a path of G; projection Pj(s) removes the unobservable events from s. Formally, projection is defined as follows [1].Definition 2 (projection).
A projectionPj:Σ∗→Σo∗ is defined as Pj(ε)=ε, for any e∈Σ, s∈Σ∗, Pj(se)=Pj(s)Pj(e), where(1)Pje=eife∈Σoεotherwise.The inverse operation of projection isPjL-1(s0)={s∈L:Pj(s)=s0}. L/s denotes the set of possible continuations of a path s. Let |s| represent the number of events in s.According to different failure types, the set of failure events can be partitioned into disjoint sets; that is,Σf=Σf1∪⋯∪Σfm. Let sf denote the final event of a path s. Define(2)ΨΣfi=s∈L:sf∈Σfi.The result of functionΨ(Σfi) represents the set of paths whose final event is the failure event of a specific type. Hereafter, Fi denotes the failure events whose type is Σfi. For the sake of simplicity, we introduce our algorithms by the systems with only a single failure type. In Section 4, we extend our algorithms to multiple failure types.In SA,p(x,e,x′) is a state transition probability of the system evolution from x to x′ driven by event e, where x,x′∈X, and e∈Σ. To facilitate the solution to the diagnosis problems, we formulate three assumptions about the transition probability [1, 12]:(A1)
At most onex′∈X exists, such that p(x,e,x′)>0 for a given x∈X and a given e∈Σ.(A2)
For every state inX, the probability of a transition occurring from that state is one or, equivalently, ∀x∈X,(3)∑x′∈X∑e∈Σpx,e,x′=1.(A3)
There does not exist any cycle of unobservable events; that is,(4)s∈Σuo∗⟹s≤n0∃n0∈N∀ust∈L.Intuitively, assumptions (A1) and (A2) indicate that transitions will continue to occur in any state. Assumption (A3) ensures that the DES does not exhibit an arbitrarily long path of unobservable events.The probability transition function presents the probability of the partial transition function, which is defined astran:X×Σ→X, where(5)tranx,e=x′⟹px,e,x′>0.Ifp(x,e,x′)=0, then tran(x,e) is undefined. Furthermore, the transition function can be extended to the sequence of events as follows:(6)tranx,se=trantranx,s,e.Particularly,tran(x,ε)=x.The probability of a sequence between two states is defined asps:X×Σ∗×X→[0,1]. For example, the probability from xm to xj through path e1e2 can be calculated as(7)psxm,e1e2,xj=pxm,e1,xipxi,e2,xj,where tran(xm,e1)=xi.On the basis of (7), the probability of a path, which is from state x to x′, can be calculated recursively as follows:(8)psx,se,x′=psx,s,tranx,sptranx,s,e,x′.Following [12], if no confusion results, Pr(e∣x) and Pr(se∣x) can be denoted by Pr(e) and Pr(se), respectively.Example 3.
Consider the SAG represented in Figure 3 and let s=fo1. Thus, the probability of s from state 0 to 1 is ps(0,s,1)=0.1×0.2=0.02. We suppose t=u1o1n, and then Pr(st∣0)=0.02×0.8×1n=0.016.Figure 3
An SAG, where the observable events set is Σo={o1}, Σuo={u1,f}, and the failure events set is Σf={f}.


## 2.2. A-Diagnosability and Stochastic Diagnoser of SDES

The approach for distributed diagnosis is based on the related definitions in [12]. In this subsection, we review the definitions of A-diagnosability and stochastic diagnoser of SDES in [12].Assessing the diagnosability of a system is crucial in diagnosis. The definition of diagnosability in DES was proposed in [1]. However, diagnosability cannot distinguish between paths highly probable and less probable. Therefore, A-diagnosability was proposed in [12]. A-diagnosability requires an error bound ϵ and a delay bound n such that, for any failure path, its extensions, which are longer than n, occur with a probability smaller than ϵ [12].Definition 4 (A-diagnosability).
A live, prefix-closed languageL is Fi-A-diagnosable with respect to a projection Pj and a set of transition probabilities p if(9)Prt:Dst=0∣t∈Ls∧t=n<ϵ∀ϵ>0∃N∈N∀s∈ΨΣfi∧n≥N,where the diagnosability condition function D is as follows:(10)Dst=1ifω∈PjL-1Pjst⟹Σfi∈ω0otherwise.In (9), path s ends with a failure event whose type is Σfi. t is an arbitrary sufficiently long continuation of s. L is not logical diagnosable (referred to as diagnosability in [1]). L is Fi-A-diagnosable,if and only if (iff) the probability of t is smaller than ϵ.An SA is A-diagnosable iff every failure eventf in SA is A-diagnosable.Example 5.
Consider the SDESG in Figure 3 as an example; the path s=f∈Ψ(Σf1). We take ϵ = 0.1. The continuation of s is t=o1n or t=u1o1n-1. For both continuations, we have Pj(st)=o1n. However, the inverse projection PjL-1(o1n)={fo1n-1,fu1o1n-2,o1n}. Therefore, D(st) = 0. When t=u1o1n-1, the probability of t is Pr(u1o1n-1)=0.8×1n-1=0.8>ϵ. We can conclude that f is not A-diagnosable in G.A necessary and sufficient condition was proposed to check the A-diagnosability of the failure events in [12]. The condition is based on stochastic diagnoser. Stochastic diagnoser, which is used either online or offline to describe the behavior of the stochastic system G, is constructed as follows [12].Definition 6 (stochastic diagnoser).
A stochastic diagnoser is defined as a tupleGd=(Xd,Σo,pd,x0d,Φ,ϕ0), where Xd is the set of logical elements with the initial logical element x0d={(x0,N)}, Σo is the set of observable events, pd is the transition function of the stochastic diagnoser, Φ is the set of probability transition matrices, and ϕ0 is the initial probability mass function on x0d.More details of the stochastic diagnoser can be found in [12]. Figure 4 shows the stochastic diagnoser Gd of the SDES G in Figure 3. Two logical elements exist in Gd; that is, x0d={(0,{N})} and x1d={(1,{F}),(2,{F}),(3,{N})}. {(0,{N})} is the initial logical element. Let (1,{F}) denote a component of x1d. If all the components in a logical element xd bear Fi, then xd is Fi-certain. Otherwise, xd is Fi-uncertain. x1d is an F-uncertain logical element.Figure 4
A stochastic diagnoserGd.The condition of A-diagnosability is based on the theory of Markov chains. Letx and y be states of a Markov chain. ρxy (0<ρxy≤1) represents the probability that if the Markov chain is in state x, it will go back to state y at some point in the future. If ρxx=1, then x is called a recurrent state. Otherwise, x is called a transient state.The condition for a languageL to be A-diagnosable is described as follows.Theorem 7 (see [12]).
A language L generated by an SA G isFi-A-diagnosable iff every logical element of its stochastic diagnoser Gd containing a recurrent component bearing the label Fi is Fi-certain.The proof of Theorem7 can be found in [12].We conclude this section with an example that illustrates the stochastic diagnoser in Figure4. Components (2,{F}) and (3,{N}) are two recurrent components in x1d. Moreover, (2,{F}) is a recurrent component bearing failure event. However, x1d={(1,{F}),(2,{F}),(3,{N})} is F-uncertain. Therefore, f is not A-diagnosable in G.


## 3. A-Diagnosability for Distributed SDESs

In Section2, we have already introduced A-diagnosability in SDES. In this section, A-diagnosability property will be taken into account when the SDES is modeled as a distributed SDES.


### 3.1. SDES with Decentralized Information

DESs with decentralized information are partitioned into decentralized DESs and distributed DESs. Similarly, we separate the SDESs with decentralized information into decentralized SDESs and distributed SDESs. In distributed SDESs, the local models communicate with each other by the communication events. The main task of the communication events is to deliver the diagnosis information. A distributed stochastic systemG is composed of interacting SDESs G={G1,G2,…,Gm}. G is called global model. G is obtained by the synchronization of the local models Gi (i=1,…,m), which are defined as follows.Definition 8 (local model).
A local model is defined as a tupleGi=(Xi,Σi,pi,x0i), where Xi is the local state space, Σi is the set of local events, pi:Xi×Σi×Xi→[0,1] is a partial local state transition probability function, and x0i is the initial state of the local model.Σ
i can be divided into three disjoint sets:(1)
Σio are the observable events. If an event oi∈Σio occurs on the local model, then this event cannot be observed by other local models. Therefore, suppose Gi and Gj are two arbitrary local models of G. Σio and Σjo represent the observable event sets of Gi and Gj, respectively. We have Σio∩Σjo = ϕ.(2)
Σiuo are the unobservable events. If the failure event f∈Σif∈Σiuo, then f can only occur on this local model.(3)
Σic are the communication events. If a communication event ci∈Σic, then ci occurs at least on another local model. Note that communication events are unobservable.The communication events are used to exchange the local diagnosability information. Therefore, if a communication eventc has been triggered in a local model, then c should be triggered in other local models at the same time. In order to guarantee assumption (A2) and avoid deadlock state, we make the following assumptions:(A4)
If there existsp(x,e,x′)>0 such that e∈Σc, then, ∀p(x,σ,xn)>0, we have σ∈Σc.(A5)
If there is a local modelGi=(Xi,Σi,pi,x0i) such that p(x0i,e,x′)=1 and e∈Σc, then, ∀j∈{1,…,m}∖i, the event σ from the initial state x0j of local model Gj, s.t. σ∉Σc or σ=e.Assumption (A4) implies that if there exists a communication event from statex, then all the other events from x belong to Σc. Assumption (A5) avoids the deadlock state during synchronization.After defining the local models, we introduce some properties in distributed SDESs. We defineXioc={x0i}∪{xi∈Xi:x has an observable event or a communication event into  it}.LetL(Gi,xi) denote the set of all paths that originate from state xi of Gi. We define(11)LocGi,xi=s∈LGi,xi:s=ue,u∈Σiuo∗,e∈Σio∪Σic.LσGi,xi=s∈LocGi,xi:sf=σ.For the sake of simplicity, we first illustrate a distributed SDES with two local models as an example. It is not difficult to extend to the case of a finite number of local models.Example 9.
A distributed stochastic systemG composed of local models {G1,G2} is shown in Figure 5. In the system, {c1,c2} is the set of communication events. Event o1 is observable in G1. Events o2 and o3 are observable in G2. f1 is a failure event. p(x1,f1,x2) = 0.2 is a probability transition in G1.Figure 5
A distributed SDESG.
(a)
Local modelG1
(b)
Local modelG2A local model is an SA. Therefore, based on Theorem7, we can similarly obtain the A-diagnosability of the failure events in local models. The proof of Theorem 10 is the same as Theorem 7’s.Theorem 10.
A languageL generated by a local model is Fi-A-diagnosable iff every logical element of its diagnoser containing a recurrent component bearing the label Fi is Fi-certain.A local model is locally A-diagnosable iff every failure event occurring on that local model is locally A-diagnosable.


### 3.2. Global Model

Supposef is a failure event in a local model Gi. The purpose of failure diagnosis in distributed SDES is to verify the A-diagnosability of f in the global model. Given a set of local models, the global model can be obtained by the synchronization of transitions among the local models. The synchronization is based on the communication events.Before introducing the global model, we make the following assumption:(A6)
The delay among the observable events in different local models can be omitted.Assumption (A6) ensures that the local states from different local models can be triggered together by the local events.Definition 11 (global model).
Given a set of local models{G1,…,Gm}, the global model of {G1,…,Gm} is defined by(12)Ggl=G1⋯Gm.The operator∥ represents synchronization operation. The result of synchronization is a tuple Ggl=(Xgl,Σgl,pgl,x0gl), where one has the following:(1)Xgl⊆∏i=1mXi is the set of global states, where Xi is the set of states of local model Gi. For all xgl∈Xgl,xgl=(x1,…,xm), where xi∈Xi.(2)Σgl⊆∏i=1mΣ¯i is the set of global events, where Σ¯ = Σ∪{ε}. The element in Σgl is of the form egl=(e1,…,em), where, for each i=1,2,…,m,(13)ei=cife1=⋯=em=c∈Σceiftranxi,eistriggeredinGi,e∉Σcεotherwisewhere e represents the event from the local event set Σi. If an observable event does not exist after a state, then we use event ε to guarantee the synchronization of the local models.(3)pgl:Xgl×Σgl×Xgl→[0,1] is the probability transition function of the global model (to be defined later).(4)x0gl∈Xgl is the initial state of the global model, defined as x0gl=(x01,…,x0m), where (x01,…,x0m) are the initial states of the local models {G1,…,Gm} separately.The synchronization of the transitions is described as follows:(14)Synchx1,…,xm,e1,…,em=tranx1,e1,…,tranxm,em,and the results can be separated into two cases:(1)
If∃i∈{1,…,m} such that ei∈Σc, then all the events in (e1,…,em) which are ei are triggered.(2)
If there does not exist communication event among(e1,…,em), then all the events in (e1,…,em) which are not ε are triggered.Based on the definition of local model, only communication events can occur in different local models. Therefore, if an evente is a communication event, then all the transitions including e should be triggered.Meanwhile, when a new transitiontrangl is generated, its probability is calculated according to different cases. Let pgl(xgl,egl,xgl′) denote the probability of transition trangl from global state xgl to xgl′ driven by global event egl.(15)pglxgl,egl,xgl′=1iftranxgl,eglisanuniquetransitionfromxgl∏j=1mpjPrtempxglotherwise,where pj denotes the probability of the triggered transition in local model Gj. Moreover, we suppose p(x,ε,x)=1. Based on the definition of global model, the event egl is the Cartesian product of the local events. Therefore, a temporary probability of pgl(xglegl,xgl′) can be calculated recursively by pj. For example, we choose two transitions p(x4,o1,x4)=1 in G1 and p(z2,o3,z4)=0.1 in G2, and then the temporary probability of transition p((x4,z2),(o1,o3),(x4,z4))=p(x4,o1,x4)×p(z2,o3,z4)=1×0.1=0.1. However, some results of the Cartesian product are redundant (suppose two outgoing transitions from x1 labeled by c1 and c2 exist in G1; then the result of Cartesian products (c1,c2) and (c2,c1) is redundant). Let Prtemp(xgl) represent the sum of the probabilities of the transitions which are not redundant. In order to guarantee that the sum of the probabilities is equal to 1, we need to divide ∏j=1m‍pj by Prtemp(xgl).Figure6 presents the global model Ggl of the local models {G1,G2} shown in Figure 5.Figure 6
The global modelGgl.Then, we verify A-diagnosability of the failure event in the global model. The global eventegl can be seen as an ordinary event in SDES. Similarly, the global state xgl can be seen as an ordinary state in SDES. Thus, the global model is equivalent in formalism to an SA. According to Definition 4, we can obtain the A-diagnosability of the failure event in the global model.Consider the global modelGgl in Figure 6 as an example; the sequence s=(f1,ε)∈Ψ(Σfi). One of the continuations of s is t=(o1,ε)(c2,c2)(o1,o2)n-2. We have Pj(st)=(o1,ε)(o1,o2)n-2. However, the inverse projection PjL-1(st)={(f1,ε)(o1,ε)(c2,c2)(o1,o2)n-2,(o1,ε)(c1,c1)(o1,o2)n-2}. Therefore, D(st) = 0. Meanwhile, Pr(t)=1×1×0.9n-2. When |t| becomes large, the probability of t approaches zero. We can conclude that f1 is A-diagnosable in global model Ggl.


## 3.1. SDES with Decentralized Information

DESs with decentralized information are partitioned into decentralized DESs and distributed DESs. Similarly, we separate the SDESs with decentralized information into decentralized SDESs and distributed SDESs. In distributed SDESs, the local models communicate with each other by the communication events. The main task of the communication events is to deliver the diagnosis information. A distributed stochastic systemG is composed of interacting SDESs G={G1,G2,…,Gm}. G is called global model. G is obtained by the synchronization of the local models Gi (i=1,…,m), which are defined as follows.Definition 8 (local model).
A local model is defined as a tupleGi=(Xi,Σi,pi,x0i), where Xi is the local state space, Σi is the set of local events, pi:Xi×Σi×Xi→[0,1] is a partial local state transition probability function, and x0i is the initial state of the local model.Σ
i can be divided into three disjoint sets:(1)
Σio are the observable events. If an event oi∈Σio occurs on the local model, then this event cannot be observed by other local models. Therefore, suppose Gi and Gj are two arbitrary local models of G. Σio and Σjo represent the observable event sets of Gi and Gj, respectively. We have Σio∩Σjo = ϕ.(2)
Σiuo are the unobservable events. If the failure event f∈Σif∈Σiuo, then f can only occur on this local model.(3)
Σic are the communication events. If a communication event ci∈Σic, then ci occurs at least on another local model. Note that communication events are unobservable.The communication events are used to exchange the local diagnosability information. Therefore, if a communication eventc has been triggered in a local model, then c should be triggered in other local models at the same time. In order to guarantee assumption (A2) and avoid deadlock state, we make the following assumptions:(A4)
If there existsp(x,e,x′)>0 such that e∈Σc, then, ∀p(x,σ,xn)>0, we have σ∈Σc.(A5)
If there is a local modelGi=(Xi,Σi,pi,x0i) such that p(x0i,e,x′)=1 and e∈Σc, then, ∀j∈{1,…,m}∖i, the event σ from the initial state x0j of local model Gj, s.t. σ∉Σc or σ=e.Assumption (A4) implies that if there exists a communication event from statex, then all the other events from x belong to Σc. Assumption (A5) avoids the deadlock state during synchronization.After defining the local models, we introduce some properties in distributed SDESs. We defineXioc={x0i}∪{xi∈Xi:x has an observable event or a communication event into  it}.LetL(Gi,xi) denote the set of all paths that originate from state xi of Gi. We define(11)LocGi,xi=s∈LGi,xi:s=ue,u∈Σiuo∗,e∈Σio∪Σic.LσGi,xi=s∈LocGi,xi:sf=σ.For the sake of simplicity, we first illustrate a distributed SDES with two local models as an example. It is not difficult to extend to the case of a finite number of local models.Example 9.
A distributed stochastic systemG composed of local models {G1,G2} is shown in Figure 5. In the system, {c1,c2} is the set of communication events. Event o1 is observable in G1. Events o2 and o3 are observable in G2. f1 is a failure event. p(x1,f1,x2) = 0.2 is a probability transition in G1.Figure 5
A distributed SDESG.
(a)
Local modelG1
(b)
Local modelG2A local model is an SA. Therefore, based on Theorem7, we can similarly obtain the A-diagnosability of the failure events in local models. The proof of Theorem 10 is the same as Theorem 7’s.Theorem 10.
A languageL generated by a local model is Fi-A-diagnosable iff every logical element of its diagnoser containing a recurrent component bearing the label Fi is Fi-certain.A local model is locally A-diagnosable iff every failure event occurring on that local model is locally A-diagnosable.


## 3.2. Global Model

Supposef is a failure event in a local model Gi. The purpose of failure diagnosis in distributed SDES is to verify the A-diagnosability of f in the global model. Given a set of local models, the global model can be obtained by the synchronization of transitions among the local models. The synchronization is based on the communication events.Before introducing the global model, we make the following assumption:(A6)
The delay among the observable events in different local models can be omitted.Assumption (A6) ensures that the local states from different local models can be triggered together by the local events.Definition 11 (global model).
Given a set of local models{G1,…,Gm}, the global model of {G1,…,Gm} is defined by(12)Ggl=G1⋯Gm.The operator∥ represents synchronization operation. The result of synchronization is a tuple Ggl=(Xgl,Σgl,pgl,x0gl), where one has the following:(1)Xgl⊆∏i=1mXi is the set of global states, where Xi is the set of states of local model Gi. For all xgl∈Xgl,xgl=(x1,…,xm), where xi∈Xi.(2)Σgl⊆∏i=1mΣ¯i is the set of global events, where Σ¯ = Σ∪{ε}. The element in Σgl is of the form egl=(e1,…,em), where, for each i=1,2,…,m,(13)ei=cife1=⋯=em=c∈Σceiftranxi,eistriggeredinGi,e∉Σcεotherwisewhere e represents the event from the local event set Σi. If an observable event does not exist after a state, then we use event ε to guarantee the synchronization of the local models.(3)pgl:Xgl×Σgl×Xgl→[0,1] is the probability transition function of the global model (to be defined later).(4)x0gl∈Xgl is the initial state of the global model, defined as x0gl=(x01,…,x0m), where (x01,…,x0m) are the initial states of the local models {G1,…,Gm} separately.The synchronization of the transitions is described as follows:(14)Synchx1,…,xm,e1,…,em=tranx1,e1,…,tranxm,em,and the results can be separated into two cases:(1)
If∃i∈{1,…,m} such that ei∈Σc, then all the events in (e1,…,em) which are ei are triggered.(2)
If there does not exist communication event among(e1,…,em), then all the events in (e1,…,em) which are not ε are triggered.Based on the definition of local model, only communication events can occur in different local models. Therefore, if an evente is a communication event, then all the transitions including e should be triggered.Meanwhile, when a new transitiontrangl is generated, its probability is calculated according to different cases. Let pgl(xgl,egl,xgl′) denote the probability of transition trangl from global state xgl to xgl′ driven by global event egl.(15)pglxgl,egl,xgl′=1iftranxgl,eglisanuniquetransitionfromxgl∏j=1mpjPrtempxglotherwise,where pj denotes the probability of the triggered transition in local model Gj. Moreover, we suppose p(x,ε,x)=1. Based on the definition of global model, the event egl is the Cartesian product of the local events. Therefore, a temporary probability of pgl(xglegl,xgl′) can be calculated recursively by pj. For example, we choose two transitions p(x4,o1,x4)=1 in G1 and p(z2,o3,z4)=0.1 in G2, and then the temporary probability of transition p((x4,z2),(o1,o3),(x4,z4))=p(x4,o1,x4)×p(z2,o3,z4)=1×0.1=0.1. However, some results of the Cartesian product are redundant (suppose two outgoing transitions from x1 labeled by c1 and c2 exist in G1; then the result of Cartesian products (c1,c2) and (c2,c1) is redundant). Let Prtemp(xgl) represent the sum of the probabilities of the transitions which are not redundant. In order to guarantee that the sum of the probabilities is equal to 1, we need to divide ∏j=1m‍pj by Prtemp(xgl).Figure6 presents the global model Ggl of the local models {G1,G2} shown in Figure 5.Figure 6
The global modelGgl.Then, we verify A-diagnosability of the failure event in the global model. The global eventegl can be seen as an ordinary event in SDES. Similarly, the global state xgl can be seen as an ordinary state in SDES. Thus, the global model is equivalent in formalism to an SA. According to Definition 4, we can obtain the A-diagnosability of the failure event in the global model.Consider the global modelGgl in Figure 6 as an example; the sequence s=(f1,ε)∈Ψ(Σfi). One of the continuations of s is t=(o1,ε)(c2,c2)(o1,o2)n-2. We have Pj(st)=(o1,ε)(o1,o2)n-2. However, the inverse projection PjL-1(st)={(f1,ε)(o1,ε)(c2,c2)(o1,o2)n-2,(o1,ε)(c1,c1)(o1,o2)n-2}. Therefore, D(st) = 0. Meanwhile, Pr(t)=1×1×0.9n-2. When |t| becomes large, the probability of t approaches zero. We can conclude that f1 is A-diagnosable in global model Ggl.


## 4. Conditions of A-Diagnosability for Distributed SDESs

In this section, we present the conditions for a distributed SDES to be A-diagnosable.


### 4.1. A-Diagnosable Local Model

In local models, two cases exist: the failure event is A-diagnosable and the failure event is not A-diagnosable. For the failure event which is A-diagnosable in the local model, we have the following theorem.Theorem 12.
Iff is locally A-diagnosable in a local model, then f is A-diagnosable in the global system.Proof.
Sincef is locally A-diagnosable in Gi, by Definition 4, for any ϵ>0, there exists N∈N, for any s∈Ψ(Σfi) and t∈L/s (where n≥N), such that (16)Prt:Dist=0∣t∈Ls∧t=n<ϵ.We determine the A-diagnosability through the global model. The probability of the transition is computed by (15). Suppose s′∈Ψ(Σfi) is the path ended with failure event in the global model. There exists t′∈L/s′. According to (15), we have Prt′≤Pr(t)<ϵ.
By contrast, assumef is not A-diagnosable in the global system. Then,(17)Prt′:DGgls′t′=0∣t∈Ls∧t=n>ϵ∃ϵ>0∃N∈N∃s∈ΨΣfi∧n≥N.
BecausePr(t)≥Prt′, there exists Pr(t)≥Prt′>ϵ. Therefore, there exists s∈Ψ(Σfi) and t∈L/s (where n≥N), such that(18)Prt:Dist=0∣t∈Ls∧t=n>ϵ.
The assumption violates the known conditions. Therefore, iff is locally A-diagnosable in a local model, then f is A-diagnosable in the global system.In Example9, f1 is A-diagnosable in the local model G1. Moreover, we have already presented that f1 is A-diagnosable in the global model shown in Figure 6. The result also demonstrates the correction of Theorem 12.However, if the failure eventf is not A-diagnosable in the local model, we cannot verify whether f is A-diagnosable or not in the global model. Furthermore, we construct a synchronized stochastic diagnoser to test the A-diagnosability of the failure event which is not locally A-diagnosable.


### 4.2. Construction of Synchronized Stochastic Diagnoser

In this subsection, we describe the construction of a synchronized stochastic diagnoser used to state the condition that ensures A-diagnosability. We need to first define the set of possible failure labels, which are similar to the failure labels in stochastic diagnoser in [12].Definition 13 (local failure label).
Δ
i
=
{
N
}
∪
2
Σ
i
f is a set of possible local failure labels, where Σif is the set of failure events in the local model Gi and label {N} represents the normal behavior of Gi.Similarly,Δ={N}∪2Σf is a set of possible global failure labels, where Σf=⋃i=1mΣif (m is the number of the local models).The local label propagation function isLP:Xioc×Δi×Σi∗→Δi. Given xi∈Xi, li∈Δi, and s∈Loc(Gi,xi), LP propagates the label li over s. It is defined as follows:(19)LPxi,li,s=Nifli=N∧∀kΣfk∉sFk:Σfk∈s∨Fk∈liotherwise.For the sake of describing the synchronized stochastic diagnoser clearly, we first present a prediagnoser including communication events.Definition 14 (prediagnoser).
Given a set of local models{G1,…,Gm}, the prediagnoser of local models {G1,…,Gm} is a tuple Gp=(Xp,Σoc,tranp,x0p), where one has the following:(1)Xp is a set of logical elements. The logical element in Xp is of the form xp={(q1,l1),…,(qn,ln)}, where state qi is an m-tuple (qi1,…,qim) of m local states. For each j∈{1,2,…,m},qij∈Xjoc and li∈Δ.(2)Σoc⊆∏i=1mΣ¯oci is the set of synchronized events, where Σ¯oci = Σio∪Σic∪{ε}. The element in Σoc is of the form eoc=(e1,…,em), where, for each i=1,2,…,m,(20)ei=cife1=⋯=em=c∈Σceiftranxi,eistriggeredinGi,e∉Σcεotherwise.where e represents the event from the local event set Σi.(3)tranp:Xp×Σoc→Xp is the transition function of the prediagnoser (to be defined later).(4)x0p∈Xp is the initial logical element of the prediagnoser, defined as x0p=((q01,…,q0m),{N}), where (q01,…,q0m) are the initial states of the local models {G1,…,Gm} separately.Given a logical element of the prediagnoserxp={(q1,l1),…,(qn,ln)}, a pair (qi,li) is called a diagnoser component of xp. In (qi,li), qi is an m-tuple (qi1,…,qim) of m local states. In order to define tranp, we first introduce the evolution of the diagnoser component driven by the synchronized events. Given a synchronized event eoc=(e1,…,em)∈Σoc, we use Evo((qi,li),eoc) to define the evolution, where qi = (qi1,…,qim):(21)Evoqi,li,eoc=⋃j=1m⋃s∈LejGj,qij∧j=1mtranqij,s,LPqij,li,s.Figure7 presents the prediagnoser of local models {G1,G2} in Figure 5.Figure 7
Prediagnoser of{G1,G2}.Definition 15 (synchronized stochastic diagnoser).
Synchronized stochastic diagnoser removes the communication events fromGp and adds probability transition matrices. Synchronized stochastic diagnoser is a tuple Gsd = (Obs(Gp),Φsd,ϕ0sd), where one has the following:(1) The result ofObs(Gp) is a 4-tuple (Xsd,Σsd,transd,x0sd), which removes communication events from Σoc and removes transitions including communication events.(2)Φsd is the set of probability transition matrices. A set of probability transition matrices is defined as Φsd:Xsd×Σsd→M[0,1]:(22)Φijxsd,esd=∏k=1mPrksek,xk,where s∈Σkuo and xk∈xsd.(3)ϕ0sd=[1] represents the initial probability mass function on x0sd.Example 16.
We take the prediagnoser in Figure7 as an example. Figure 8 shows the synchronized stochastic diagnoser of local models G1 and G2.Figure 8
Synchronized stochastic diagnoser of{G1,G2}.


### 4.3. Necessary and Sufficient Condition of A-Diagnosability for Distributed SDES

In this subsection, we present a necessary and sufficient condition of A-diagnosability for distributed SDESs which are not A-diagnosable in local models. Before determining the condition, we introduce a property of the synchronized stochastic diagnoser.Letxsd be a logical element of the synchronized stochastic diagnoser. If all the diagnoser components in a logical element xsd bear Fi, then xsd is Fi-certain. Otherwise, xsd is Fi-uncertain.Theorem 17.
LetGsd=(Xsd,Σsd,transd,x0sd,Φsd,ϕ0sd) be a synchronized stochastic diagnoser of the local models Gi, where i=1,2,…,m. L is A-diagnosable iff every logical element in Gsd containing a recurrent diagnoser component bearing the label Fi is Fi-certain.The logical elements inXsd can be viewed as a whole state and the synchronized events in Σsd can be viewed as a whole event. Thus, the synchronized stochastic diagnoser is equivalent to a stochastic diagnoser in formalism. Therefore, the proof of Theorem 17 is the same as the proof of Theorem 3 in [12].Consider the synchronized stochastic diagnoser in Figure8; {(x4,z3),{N}} and {(x4,z4),{F}} are two recurrent diagnoser components. The label of {(x4,z3),{N}} is {N}. We only consider the logical element of component {(x4,z4),{F}}. The logical element of {(x4,z4),{F}} is F-certain. Therefore, there does not exist a logical element containing a recurrent diagnoser component bearing the label Fi which is Fi-uncertain in Figure 8. We can conclude that f is A-diagnosable in the global model.When a distributed SDESG has more than two local models {G1,…,Gm} (i.e., m>2) and a failure event f is not A-diagnosable in a local model Gi, computing the synchronized stochastic diagnoser of all the local models is complex. Theorem 12 has stated that a failure event f is A-diagnosable in the global model if f is A-diagnosable in the local model. Moreover, Theorem 12 can be extended as follows.Theorem 18.
Iff is A-diagnosable in a synchronized stochastic diagnoser of local models {Gp,…,Gq}, where {Gp,…,Gq}⊆{G1,…,Gm}, then f is A-diagnosable in the global model.The proof of Theorem18 is the same as the proof of Theorem 12. Therefore, if f is not A-diagnosable in Gi, we do not need to compute the synchronized stochastic diagnoser of all the local models. We first compute the synchronized stochastic diagnoser of Gi and Gj (j∈{1,…,m}∖{i}). We use Gsd to denote the synchronized stochastic diagnoser of Gi and other local models. If there exists a logical element in Gsd containing a recurrent diagnoser component bearing the label Fi which is Fi-certain, then f is A-diagnosable in the global model. We present an algorithm, called VerDia, to present the process of testing A-diagnosability in distributed SDESs. For the sake of simplicity, we consider the distributed SDES with a failure event. It is not difficult to extend the algorithm to the case of multiple failures.LetG=(X,Σ,p,x0) be a distributed stochastic system composed of m local models {G1,…,Gm}, where Gi=(Xi,Σi,pi,x0i). The set of local models is the input of VerDia. Lines (1)–(4) check the A-diagnosability of each local model. In line (2), function ConDia(Gi) computes the stochastic diagnoser of local model Gi. If the failure event f is A-diagnosable in Gi, then f is A-diagnosable in the global model G and the algorithm is finished. Otherwise, we compute the synchronized stochastic diagnoser of Gi with other local models. In line (8), G represents the set of local models except Gi. G presents the number of local models in G. We first construct the synchronized stochastic diagnoser of Gi with one local model Gj; that is, G={Gj}. Therefore, the initial value of n is equal to one. If all the synchronized stochastic diagnosers of Gi and Gj (j∈{1,…,m}∖{i}) do not satisfy Theorem 17, then we construct the synchronized stochastic diagnoser of Gi with two local models. In line (9), the result of function ConSSDia(Gi,G) represents the synchronized stochastic diagnoser of Gi and the local models in G. The algorithm is finished until we have found a synchronized stochastic diagnoser which satisfies Theorem 17.If all the synchronized stochastic diagnosers do not satisfy Theorem17, then the failure event is not A-diagnosable.Example 19.
Figure9 presents a distributed SDES including three local models {G1′,G2′,G3′}. Event o1 is observable in G1′. Events o2 and o3 are observable in G2′. Event o4 is observable in G3′. Event u1 is unobservable in G3′. Events f1 and f2 are failure events and they belong to different failure types. {c1,c2} is the set of communication events. G1′ is the same as the local model G1 in Figure 5, and thus G1′ is not A-diagnosable. In G2′, suppose the path ended with a failure event is s=f2. One of the continuations of s is t=o2n. The projection of st is Pj(f2o2n)=o2n. However, the inverse projection PjL-1(o2n)={fo2n,o2c2o2n-2}. Therefore, D(st)=0. The probability of t is Pr(o2n)=0.2n. When |t| becomes large, the probability of t approaches zero. Therefore, f2 is A-diagnosable in G2′. Based on Theorem 12, we can conclude that f2 is A-diagnosable in the global model.Figure 9
A distributed SDESG′.
(a)
Local modelG1′
(b)
Local modelG2′
(c)
Local modelG3′In order to verify the A-diagnosability off1 in the global model, we compute the synchronized stochastic diagnoser of G1′ and G3′. Figure 10 shows the result. Diagnoser components ((x4,z2),{F1}) and ((x4,z4),{F1}) are recurrent diagnoser components bearing a failure label {F1}. However, logical element {((x4,z2),{F1}), ((x4,z3),{N}), ((x4,z4),{F1})} is F1-uncertain. Therefore, f1 is not A-diagnosable in the synchronized stochastic diagnoser of G1′ and G3′. f1 is also not A-diagnosable in the synchronized stochastic diagnoser of G1′ and G2′ (the synchronized stochastic diagnoser of G1′ and G2′ is omitted). Then, we compute the synchronized stochastic diagnoser of {G1′,G2′,G3′}. The result is shown in Figure 11. ((x4,y4,z1),{F1,F2}) and ((x4,y4,z1),{F1}) are recurrent diagnoser components bearing failure label F1. Moreover, logical element {((x4,y4,z1),{F1,F2}), ((x4,y4,z1),{F2}), ((x4,y4,z1),{F1}), ((x4,y4,z1),{N})} is F1-uncertain. Therefore, f1 is not A-diagnosable in the synchronized stochastic diagnoser of G1′, G2′, and G3′. Based on Theorem 17, f1 is not A-diagnosable in the global model.Figure 10
The synchronized stochastic diagnoser ofG1′ and G3′.Figure 11
The synchronized stochastic diagnoser ofG1′, G2′, and G3′.f
1 is not A-diagnosable and f2 is A-diagnosable. Therefore, the distributed SDES G′ is not A-diagnosable.


## 4.1. A-Diagnosable Local Model

In local models, two cases exist: the failure event is A-diagnosable and the failure event is not A-diagnosable. For the failure event which is A-diagnosable in the local model, we have the following theorem.Theorem 12.
Iff is locally A-diagnosable in a local model, then f is A-diagnosable in the global system.Proof.
Sincef is locally A-diagnosable in Gi, by Definition 4, for any ϵ>0, there exists N∈N, for any s∈Ψ(Σfi) and t∈L/s (where n≥N), such that (16)Prt:Dist=0∣t∈Ls∧t=n<ϵ.We determine the A-diagnosability through the global model. The probability of the transition is computed by (15). Suppose s′∈Ψ(Σfi) is the path ended with failure event in the global model. There exists t′∈L/s′. According to (15), we have Prt′≤Pr(t)<ϵ.
By contrast, assumef is not A-diagnosable in the global system. Then,(17)Prt′:DGgls′t′=0∣t∈Ls∧t=n>ϵ∃ϵ>0∃N∈N∃s∈ΨΣfi∧n≥N.
BecausePr(t)≥Prt′, there exists Pr(t)≥Prt′>ϵ. Therefore, there exists s∈Ψ(Σfi) and t∈L/s (where n≥N), such that(18)Prt:Dist=0∣t∈Ls∧t=n>ϵ.
The assumption violates the known conditions. Therefore, iff is locally A-diagnosable in a local model, then f is A-diagnosable in the global system.In Example9, f1 is A-diagnosable in the local model G1. Moreover, we have already presented that f1 is A-diagnosable in the global model shown in Figure 6. The result also demonstrates the correction of Theorem 12.However, if the failure eventf is not A-diagnosable in the local model, we cannot verify whether f is A-diagnosable or not in the global model. Furthermore, we construct a synchronized stochastic diagnoser to test the A-diagnosability of the failure event which is not locally A-diagnosable.


## 4.2. Construction of Synchronized Stochastic Diagnoser

In this subsection, we describe the construction of a synchronized stochastic diagnoser used to state the condition that ensures A-diagnosability. We need to first define the set of possible failure labels, which are similar to the failure labels in stochastic diagnoser in [12].Definition 13 (local failure label).
Δ
i
=
{
N
}
∪
2
Σ
i
f is a set of possible local failure labels, where Σif is the set of failure events in the local model Gi and label {N} represents the normal behavior of Gi.Similarly,Δ={N}∪2Σf is a set of possible global failure labels, where Σf=⋃i=1mΣif (m is the number of the local models).The local label propagation function isLP:Xioc×Δi×Σi∗→Δi. Given xi∈Xi, li∈Δi, and s∈Loc(Gi,xi), LP propagates the label li over s. It is defined as follows:(19)LPxi,li,s=Nifli=N∧∀kΣfk∉sFk:Σfk∈s∨Fk∈liotherwise.For the sake of describing the synchronized stochastic diagnoser clearly, we first present a prediagnoser including communication events.Definition 14 (prediagnoser).
Given a set of local models{G1,…,Gm}, the prediagnoser of local models {G1,…,Gm} is a tuple Gp=(Xp,Σoc,tranp,x0p), where one has the following:(1)Xp is a set of logical elements. The logical element in Xp is of the form xp={(q1,l1),…,(qn,ln)}, where state qi is an m-tuple (qi1,…,qim) of m local states. For each j∈{1,2,…,m},qij∈Xjoc and li∈Δ.(2)Σoc⊆∏i=1mΣ¯oci is the set of synchronized events, where Σ¯oci = Σio∪Σic∪{ε}. The element in Σoc is of the form eoc=(e1,…,em), where, for each i=1,2,…,m,(20)ei=cife1=⋯=em=c∈Σceiftranxi,eistriggeredinGi,e∉Σcεotherwise.where e represents the event from the local event set Σi.(3)tranp:Xp×Σoc→Xp is the transition function of the prediagnoser (to be defined later).(4)x0p∈Xp is the initial logical element of the prediagnoser, defined as x0p=((q01,…,q0m),{N}), where (q01,…,q0m) are the initial states of the local models {G1,…,Gm} separately.Given a logical element of the prediagnoserxp={(q1,l1),…,(qn,ln)}, a pair (qi,li) is called a diagnoser component of xp. In (qi,li), qi is an m-tuple (qi1,…,qim) of m local states. In order to define tranp, we first introduce the evolution of the diagnoser component driven by the synchronized events. Given a synchronized event eoc=(e1,…,em)∈Σoc, we use Evo((qi,li),eoc) to define the evolution, where qi = (qi1,…,qim):(21)Evoqi,li,eoc=⋃j=1m⋃s∈LejGj,qij∧j=1mtranqij,s,LPqij,li,s.Figure7 presents the prediagnoser of local models {G1,G2} in Figure 5.Figure 7
Prediagnoser of{G1,G2}.Definition 15 (synchronized stochastic diagnoser).
Synchronized stochastic diagnoser removes the communication events fromGp and adds probability transition matrices. Synchronized stochastic diagnoser is a tuple Gsd = (Obs(Gp),Φsd,ϕ0sd), where one has the following:(1) The result ofObs(Gp) is a 4-tuple (Xsd,Σsd,transd,x0sd), which removes communication events from Σoc and removes transitions including communication events.(2)Φsd is the set of probability transition matrices. A set of probability transition matrices is defined as Φsd:Xsd×Σsd→M[0,1]:(22)Φijxsd,esd=∏k=1mPrksek,xk,where s∈Σkuo and xk∈xsd.(3)ϕ0sd=[1] represents the initial probability mass function on x0sd.Example 16.
We take the prediagnoser in Figure7 as an example. Figure 8 shows the synchronized stochastic diagnoser of local models G1 and G2.Figure 8
Synchronized stochastic diagnoser of{G1,G2}.


## 4.3. Necessary and Sufficient Condition of A-Diagnosability for Distributed SDES

In this subsection, we present a necessary and sufficient condition of A-diagnosability for distributed SDESs which are not A-diagnosable in local models. Before determining the condition, we introduce a property of the synchronized stochastic diagnoser.Letxsd be a logical element of the synchronized stochastic diagnoser. If all the diagnoser components in a logical element xsd bear Fi, then xsd is Fi-certain. Otherwise, xsd is Fi-uncertain.Theorem 17.
LetGsd=(Xsd,Σsd,transd,x0sd,Φsd,ϕ0sd) be a synchronized stochastic diagnoser of the local models Gi, where i=1,2,…,m. L is A-diagnosable iff every logical element in Gsd containing a recurrent diagnoser component bearing the label Fi is Fi-certain.The logical elements inXsd can be viewed as a whole state and the synchronized events in Σsd can be viewed as a whole event. Thus, the synchronized stochastic diagnoser is equivalent to a stochastic diagnoser in formalism. Therefore, the proof of Theorem 17 is the same as the proof of Theorem 3 in [12].Consider the synchronized stochastic diagnoser in Figure8; {(x4,z3),{N}} and {(x4,z4),{F}} are two recurrent diagnoser components. The label of {(x4,z3),{N}} is {N}. We only consider the logical element of component {(x4,z4),{F}}. The logical element of {(x4,z4),{F}} is F-certain. Therefore, there does not exist a logical element containing a recurrent diagnoser component bearing the label Fi which is Fi-uncertain in Figure 8. We can conclude that f is A-diagnosable in the global model.When a distributed SDESG has more than two local models {G1,…,Gm} (i.e., m>2) and a failure event f is not A-diagnosable in a local model Gi, computing the synchronized stochastic diagnoser of all the local models is complex. Theorem 12 has stated that a failure event f is A-diagnosable in the global model if f is A-diagnosable in the local model. Moreover, Theorem 12 can be extended as follows.Theorem 18.
Iff is A-diagnosable in a synchronized stochastic diagnoser of local models {Gp,…,Gq}, where {Gp,…,Gq}⊆{G1,…,Gm}, then f is A-diagnosable in the global model.The proof of Theorem18 is the same as the proof of Theorem 12. Therefore, if f is not A-diagnosable in Gi, we do not need to compute the synchronized stochastic diagnoser of all the local models. We first compute the synchronized stochastic diagnoser of Gi and Gj (j∈{1,…,m}∖{i}). We use Gsd to denote the synchronized stochastic diagnoser of Gi and other local models. If there exists a logical element in Gsd containing a recurrent diagnoser component bearing the label Fi which is Fi-certain, then f is A-diagnosable in the global model. We present an algorithm, called VerDia, to present the process of testing A-diagnosability in distributed SDESs. For the sake of simplicity, we consider the distributed SDES with a failure event. It is not difficult to extend the algorithm to the case of multiple failures.LetG=(X,Σ,p,x0) be a distributed stochastic system composed of m local models {G1,…,Gm}, where Gi=(Xi,Σi,pi,x0i). The set of local models is the input of VerDia. Lines (1)–(4) check the A-diagnosability of each local model. In line (2), function ConDia(Gi) computes the stochastic diagnoser of local model Gi. If the failure event f is A-diagnosable in Gi, then f is A-diagnosable in the global model G and the algorithm is finished. Otherwise, we compute the synchronized stochastic diagnoser of Gi with other local models. In line (8), G represents the set of local models except Gi. G presents the number of local models in G. We first construct the synchronized stochastic diagnoser of Gi with one local model Gj; that is, G={Gj}. Therefore, the initial value of n is equal to one. If all the synchronized stochastic diagnosers of Gi and Gj (j∈{1,…,m}∖{i}) do not satisfy Theorem 17, then we construct the synchronized stochastic diagnoser of Gi with two local models. In line (9), the result of function ConSSDia(Gi,G) represents the synchronized stochastic diagnoser of Gi and the local models in G. The algorithm is finished until we have found a synchronized stochastic diagnoser which satisfies Theorem 17.If all the synchronized stochastic diagnosers do not satisfy Theorem17, then the failure event is not A-diagnosable.Example 19.
Figure9 presents a distributed SDES including three local models {G1′,G2′,G3′}. Event o1 is observable in G1′. Events o2 and o3 are observable in G2′. Event o4 is observable in G3′. Event u1 is unobservable in G3′. Events f1 and f2 are failure events and they belong to different failure types. {c1,c2} is the set of communication events. G1′ is the same as the local model G1 in Figure 5, and thus G1′ is not A-diagnosable. In G2′, suppose the path ended with a failure event is s=f2. One of the continuations of s is t=o2n. The projection of st is Pj(f2o2n)=o2n. However, the inverse projection PjL-1(o2n)={fo2n,o2c2o2n-2}. Therefore, D(st)=0. The probability of t is Pr(o2n)=0.2n. When |t| becomes large, the probability of t approaches zero. Therefore, f2 is A-diagnosable in G2′. Based on Theorem 12, we can conclude that f2 is A-diagnosable in the global model.Figure 9
A distributed SDESG′.
(a)
Local modelG1′
(b)
Local modelG2′
(c)
Local modelG3′In order to verify the A-diagnosability off1 in the global model, we compute the synchronized stochastic diagnoser of G1′ and G3′. Figure 10 shows the result. Diagnoser components ((x4,z2),{F1}) and ((x4,z4),{F1}) are recurrent diagnoser components bearing a failure label {F1}. However, logical element {((x4,z2),{F1}), ((x4,z3),{N}), ((x4,z4),{F1})} is F1-uncertain. Therefore, f1 is not A-diagnosable in the synchronized stochastic diagnoser of G1′ and G3′. f1 is also not A-diagnosable in the synchronized stochastic diagnoser of G1′ and G2′ (the synchronized stochastic diagnoser of G1′ and G2′ is omitted). Then, we compute the synchronized stochastic diagnoser of {G1′,G2′,G3′}. The result is shown in Figure 11. ((x4,y4,z1),{F1,F2}) and ((x4,y4,z1),{F1}) are recurrent diagnoser components bearing failure label F1. Moreover, logical element {((x4,y4,z1),{F1,F2}), ((x4,y4,z1),{F2}), ((x4,y4,z1),{F1}), ((x4,y4,z1),{N})} is F1-uncertain. Therefore, f1 is not A-diagnosable in the synchronized stochastic diagnoser of G1′, G2′, and G3′. Based on Theorem 17, f1 is not A-diagnosable in the global model.Figure 10
The synchronized stochastic diagnoser ofG1′ and G3′.Figure 11
The synchronized stochastic diagnoser ofG1′, G2′, and G3′.f
1 is not A-diagnosable and f2 is A-diagnosable. Therefore, the distributed SDES G′ is not A-diagnosable.


## 5. Evaluations

LetG=(X,Σ,p,x0) be a distributed stochastic system composed of m local models {G1,G2,…,Gm}, where Gi=(Xi,Σi,pi,x0i). |Xi| and |Σi| denote the number of states and events of Gi, respectively, where i=1,2,…,m. Table 1 lists the maximum numbers of states and transitions of Gi. Gid is the stochastic diagnoser of Gi. The logical element space of the stochastic diagnoser is a subset of 2|Xi|×Δi. Therefore, each local stochastic diagnoser has at most 22|Xi| logical elements and 22|Xi|×|Σio| transitions. Gsdij represents the synchronized stochastic diagnoser of Gi and Gj. Similarly, the logical element of Gsdij is at most 24|Xi×Xj| and the transition is at most 24|Xi×Xj|×|Σio×Σjo|. Let |Xmax| = max(|Xi|) be the largest number of the states of the local models. If the failure event is A-diagnosable in the local models, then the complexity of the computing process is O(m×22|Xmax|×22|Xmax|×|Σo|). However, if the local models are not A-diagnosable, the synchronized stochastic diagnosers should be constructed to verify the A-diagnosability of the distributed SDES. The worst case is that we verify the A-diagnosability through the global model. The number of states of the global model is 22m|Xmax|m and the number of transitions is 22m|Xmax|m×|Σo|m. Therefore, the overall complexity of the computing process of verifying A-diagnosability is O(22m|Xmax|m×22m|Xmax|m×|Σo|m).Table 1
Complexity of verifying A-diagnosability in distributed SDES.
Automaton
Number of states
Number of transitions
Gi
|
X
i
|
|
X
i
|
×
|
Σ
i
|
Gid
2
2
|
X
i
|
2
2
|
X
i
|
×
|
Σ
i
o
|
Gsdij
2
4
|
X
i
|
×
|
X
j
|
2
4
|
X
i
|
×
|
X
j
|
×
|
Σ
i
o
×
Σ
j
o
|
G
2
2
m
|
X
m
a
x
|
m
2
2
m
|
X
m
a
x
|
m
×
|
Σ
o
|
m
Complexity
O
(
2
2
m
|
X
m
a
x
|
m
×
2
2
m
|
X
m
a
x
|
m
×
|
Σ
o
|
m
)


## 6. Related Work

Since Sampath et al. proposed diagnosability in DESs [1], many algorithms about failure diagnosis were proposed. In order to reduce the complexity in central diagnosis, DESs with decentralized information were investigated. References [4, 9] described the diagnosis in decentralized DES and [3, 7, 8] described the diagnosis in distributed DES. SDES can present the system more precisely. In the context of testing diagnosability of SDES, a number of approaches have been proposed, including [11–17]. Reference [16] has defined safe diagnosability for SDES, in which failure detection occurs before any given forbidden string in the failed mode of system is executed. References [11–13, 17] have presented the algorithms of testing diagnosability of SDES. The methods in [12] constructed a diagnoser and used Markov matrix to test diagnosability of the SDES. The complexity of the methods in [12] is O(2×22|X|×|X|2×|Σ|+22|X|×|X|3), which is exponential in the number of states of the system. To improve the efficiency, [11, 17] proposed a polynomial test to verify the diagnosability. The complexity of the methods in [11] is O(|X|6+2|X|4×|Σ|). Reference [11] is based on the twin-plant structure and does not construct a diagnoser. Reference [13] has used probabilistic logic to diagnose SDES. The complexity of [13] is also polynomial and the power of the algorithms is 4. Because of the large number of states in a global SDES, SDESs with decentralized information were proposed. Similarly, SDESs with decentralized information are separated into decentralized SDESs and distributed SDESs. A-diagnosability of decentralized SDESs has been presented in [15]. In order to improve the complexity of diagnosis in decentralized SDESs, [14] proposed a polynomial algorithm to check the A-diagnosability of decentralized SDESs.To the best of our knowledge, there is no work about A-diagnosability in a distributed SDES. Therefore, the question of A-diagnosability in a distributed SDES is investigated in this paper.


## 7. Conclusion

A-diagnosability is an important property in SDES. SDESs with decentralized information are partitioned into decentralized SDES and distributed SDES. In this paper, we investigate the A-diagnosability in distributed SDES. We introduce the local model and global model in distributed SDES. In order to verify the A-diagnosability of the global model, A-diagnosability of every local model should be verified first. For the local models which are not A-diagnosable, we have proposed a necessary and sufficient condition to ensure A-diagnosability of distributed SDES. A synchronized stochastic diagnoser has been constructed to determine the condition.Incremental diagnosis is another approach to diagnose the system locally. In the future, we intend to investigate the incremental diagnosis in SDES.



---

*Source: 7680698-2017-10-02.xml*