Home // International Journal On Advances in Systems and Measurements, volume 6, numbers 3 and 4, 2013 // View article

Undecidable Case and Decidable Case of Joint Diagnosability in Distributed Discrete Event Systems

Authors:
Lina Ye
Philippe Dague

Keywords: joint diagnosability, self-observed systems, finite state machine, Post’s Correspondence Problem, undecidability

Abstract:
Diagnosability is an important property that determines at design stage how accurate any diagnosis algorithm can be on a partially observable system. Most existing approaches assumed that each observable event in the system is globally observed. Considering the cases where there is no global information, one of our recent work proposed a new framework to check diagnosability in a system where each component can only observe its own observable events to keep the internal structure private in terms of observations. However, we assumed that the local paths in each component can be exhaustively enumerated, which is not suitable in a general case where there are embedded cycles. In this paper, we get some new results about diagnosability in such a system in a general case, i.e., what we call joint diagnosability in a self-observed distributed system. First, we prove the undecidability of joint diagnosability with unobservable communication events by reducing the Post's Correspondence Problem to joint diagnosability problem. We also propose an algorithm to check a sufficient but not necessary condition of joint diagnosability, which is then adapted when the assumption of all communication events being unobservable is relaxed, i.e., communication events could be either observable or unobservable. Then, we discuss about the decidable case where communication events are all observable and develop a new efficient algorithm to test it. Finally, we also provide an important property of joint diagnosability after analyzing its relationship with classical diagnosability.

Pages: 287 to 299

Copyright: Copyright (c) to authors, 2013. Used with permission.

Publication date: December 31, 2013

Published in: journal

ISSN: 1942-261x