Coordinated decentralized protocols for failure diagnosis of discrete event systems

We address the problem of failure diagnosis in discrete event systems with decentralized information. We propose a coordinated decentralized architect ure consisting of local sites communicating with a coordinator that is resp onsible for diagnosing the failures occurring in the system. We extend the notion of diagnosability, originally introduced in Sampath et al. (1995) fo r centralized systems, to the proposed coordinated decentralized architectu re. We specify three protocols that realize the proposed architecture; each protocol is defined by the diagnostic information generated at the local s ites, the communication rules used by the local sites, and the coordinator' s decision rule. We analyze the diagnostic properties of each protocol. We also state and prove conditions for a language to be diagnosable under each protocol. These conditions are checkable off-line. The on-line diagnostic process is carried out using the diagnosers introduced in Sampath et al. (1 995) or a slight variation of these diagnosers. The key features of the pro posed protocols are: (i) they achieve, each under a set of assumptions, the same diagnostic performance as the centralized diagnoser; and (ii) they hi ghlight the "performance vs. complexity'' tradeoff that arises in coordinat ed decentralized architectures. The correctness of two of the protocols rel ies on some stringent global ordering assumptions on message reception at t he coordinator's site, the relaxation of which is briefly discussed.