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.
Type de document :
Communication dans un congrès
10th International Conference on Discrete Event Systems WODES'10, Aug 2008, Berlin, Germany. 2010
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00540764
Contributeur : Philippe Dague <>
Soumis le : lundi 29 novembre 2010 - 11:20:44
Dernière modification le : jeudi 5 avril 2018 - 12:30:08
Document(s) archivé(s) le : samedi 3 décembre 2016 - 03:03:29

Fichier

wodes2010_paper63.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00540764, version 1

Collections

Citation

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. 2010. 〈inria-00540764〉

Partager

Métriques

Consultations de la notice

275

Téléchargements de fichiers

160