Skip to Main content Skip to Navigation
Conference papers

An Optimized Algorithm for Diagnosability of Component-based Systems

Lina ye 1, 2 Philippe Dague 1, 2 
2 LEO - Distributed and heterogeneous data and knowledge
UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : Diagnosability is a crucial system property that determines at design stage how accurate any diagnosis algorithm can be on a partially observable system. The existence of two indistinguishable behaviors, i.e. holding the same observations, with exactly one of them containing the fault violates the diagnosability property. A classical approach for diagnosability verification consists in constructing a finite state machine called twin plant to search for a path representing such indistinguishable behaviors, called a critical path. To avoid the unrealistic hypothesis about the monolithic model of a complex system, recent work constructs local twin plants and then incrementally synchronizes some of them until diagnosability is decided without computing the impractical global twin plant. In this paper, we optimize the distributed approach by abstracting necessary and sufficient diagnosability information from local twin plants to check the existence of critical paths. Thus diagnosability can be analyzed with as small search space as possible. Furthermore, our approach describes how to improve the diagnosis algorithm by using our diagnosability results in a formal way when the system is verified to be diagnosable. Finally, when the system is not diagnosable, the algorithm returns some useful information about its indistinguishable behaviors, which can help in upgrading system diagnosable level.
Document type :
Conference papers
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download
Contributor : Philippe Dague Connect in order to contact the contributor
Submitted on : Monday, November 29, 2010 - 11:20:44 AM
Last modification on : Sunday, June 26, 2022 - 11:52:41 AM
Long-term archiving on: : Saturday, December 3, 2016 - 3:03:29 AM


Files produced by the author(s)


  • HAL Id : inria-00540764, version 1



Lina ye, Philippe Dague. An Optimized Algorithm for Diagnosability of Component-based Systems. 10th International Conference on Discrete Event Systems WODES'10, Aug 2008, Berlin, Germany. ⟨inria-00540764⟩



Record views


Files downloads