Global State Estimates for Distributed Systems

Abstract : We consider distributed systems modeled as communicating finite state machines with reliable unbounded FIFO channels. As an essential sub-routine for control, monitoring and diagnosis applications, we provide an algorithm that computes, during the execution of the system, an estimate of the current global state of the distributed system for each local subsystem. This algorithm does not change the behavior of the system; each subsystem only computes and records a symbolic representation of the state estimates, and piggybacks some extra information to the messages sent to the other subsystems in order to refine their estimates. Our algorithm relies on the computation of reachable states. Since the reachability problem is undecidable in our model, we use abstract interpretation techniques to obtain regular overapproximations of the possible FIFO channel contents, and hence of the possible current global states. An implementation of this algorithm provides an empirical evaluation of our method.
Type de document :
Communication dans un congrès
Roberto Bruni; Juergen Dingel. 13th Conference on Formal Methods for Open Object-Based Distributed Systems (FMOODS) / 31th International Conference on FORmal TEchniques for Networked and Distributed Systems (FORTE), Jun 2011, Reykjavik, Iceland. Springer, Lecture Notes in Computer Science, LNCS-6722, pp.198-212, 2011, Formal Techniques for Distributed Systems. 〈http://www.springerlink.com/content/v5n7713364t83022/〉. 〈10.1007/978-3-642-21461-5_13〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00581259
Contributeur : Hervé Marchand <>
Soumis le : mercredi 30 mars 2011 - 15:15:17
Dernière modification le : mercredi 11 avril 2018 - 01:55:09
Document(s) archivé(s) le : samedi 3 décembre 2016 - 21:24:36

Fichier

forte-hal.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Gabriel Kalyon, Tristan Le Gall, Hervé Marchand, Thierry Massart. Global State Estimates for Distributed Systems. Roberto Bruni; Juergen Dingel. 13th Conference on Formal Methods for Open Object-Based Distributed Systems (FMOODS) / 31th International Conference on FORmal TEchniques for Networked and Distributed Systems (FORTE), Jun 2011, Reykjavik, Iceland. Springer, Lecture Notes in Computer Science, LNCS-6722, pp.198-212, 2011, Formal Techniques for Distributed Systems. 〈http://www.springerlink.com/content/v5n7713364t83022/〉. 〈10.1007/978-3-642-21461-5_13〉. 〈inria-00581259〉

Partager

Métriques

Consultations de la notice

211

Téléchargements de fichiers

147