Global State Estimates for Distributed Systems
International audience 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 e...
Main Authors: | , , , |
---|---|
Other Authors: | , , , , , , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2011
|
Subjects: | |
Online Access: | https://hal.inria.fr/inria-00581259 https://hal.inria.fr/inria-00581259/document https://hal.inria.fr/inria-00581259/file/forte-hal.pdf https://doi.org/10.1007/978-3-642-21461-5_13 |
id |
ftccsdartic:oai:HAL:inria-00581259v1 |
---|---|
record_format |
openpolar |
spelling |
ftccsdartic:oai:HAL:inria-00581259v1 2023-05-15T16:49:32+02:00 Global State Estimates for Distributed Systems Kalyon, Gabriel Le Gall, Tristan Marchand, Hervé Massart, Thierry Université libre de Bruxelles (ULB) Laboratoire d'Intégration des Systèmes et des Technologies (LIST) Direction de Recherche Technologique (CEA) (DRT (CEA)) Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA) Verification models and techniques applied to testing and control of reactive systems (VERTECS) Inria Rennes – Bretagne Atlantique Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria) Roberto Bruni Juergen Dingel TC 6 WG 6.1 Reykjavik, Iceland 2011-06-06 https://hal.inria.fr/inria-00581259 https://hal.inria.fr/inria-00581259/document https://hal.inria.fr/inria-00581259/file/forte-hal.pdf https://doi.org/10.1007/978-3-642-21461-5_13 en eng HAL CCSD Springer info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-642-21461-5_13 inria-00581259 https://hal.inria.fr/inria-00581259 https://hal.inria.fr/inria-00581259/document https://hal.inria.fr/inria-00581259/file/forte-hal.pdf doi:10.1007/978-3-642-21461-5_13 http://creativecommons.org/licenses/by/ info:eu-repo/semantics/OpenAccess Lecture Notes in Computer Science 13th Conference on Formal Methods for Open Object-Based Distributed Systems (FMOODS) / 31th International Conference on FORmal TEchniques for Networked and Distributed Systems (FORTE) https://hal.inria.fr/inria-00581259 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. pp.198-212, ⟨10.1007/978-3-642-21461-5_13⟩ http://www.springerlink.com/content/v5n7713364t83022/ [INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE] info:eu-repo/semantics/conferenceObject Conference papers 2011 ftccsdartic https://doi.org/10.1007/978-3-642-21461-5_13 2021-10-24T17:56:07Z International audience 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. Conference Object Iceland Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) 198 212 |
institution |
Open Polar |
collection |
Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
op_collection_id |
ftccsdartic |
language |
English |
topic |
[INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE] |
spellingShingle |
[INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE] Kalyon, Gabriel Le Gall, Tristan Marchand, Hervé Massart, Thierry Global State Estimates for Distributed Systems |
topic_facet |
[INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE] |
description |
International audience 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. |
author2 |
Université libre de Bruxelles (ULB) Laboratoire d'Intégration des Systèmes et des Technologies (LIST) Direction de Recherche Technologique (CEA) (DRT (CEA)) Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA) Verification models and techniques applied to testing and control of reactive systems (VERTECS) Inria Rennes – Bretagne Atlantique Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria) Roberto Bruni Juergen Dingel TC 6 WG 6.1 |
format |
Conference Object |
author |
Kalyon, Gabriel Le Gall, Tristan Marchand, Hervé Massart, Thierry |
author_facet |
Kalyon, Gabriel Le Gall, Tristan Marchand, Hervé Massart, Thierry |
author_sort |
Kalyon, Gabriel |
title |
Global State Estimates for Distributed Systems |
title_short |
Global State Estimates for Distributed Systems |
title_full |
Global State Estimates for Distributed Systems |
title_fullStr |
Global State Estimates for Distributed Systems |
title_full_unstemmed |
Global State Estimates for Distributed Systems |
title_sort |
global state estimates for distributed systems |
publisher |
HAL CCSD |
publishDate |
2011 |
url |
https://hal.inria.fr/inria-00581259 https://hal.inria.fr/inria-00581259/document https://hal.inria.fr/inria-00581259/file/forte-hal.pdf https://doi.org/10.1007/978-3-642-21461-5_13 |
op_coverage |
Reykjavik, Iceland |
genre |
Iceland |
genre_facet |
Iceland |
op_source |
Lecture Notes in Computer Science 13th Conference on Formal Methods for Open Object-Based Distributed Systems (FMOODS) / 31th International Conference on FORmal TEchniques for Networked and Distributed Systems (FORTE) https://hal.inria.fr/inria-00581259 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. pp.198-212, ⟨10.1007/978-3-642-21461-5_13⟩ http://www.springerlink.com/content/v5n7713364t83022/ |
op_relation |
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-642-21461-5_13 inria-00581259 https://hal.inria.fr/inria-00581259 https://hal.inria.fr/inria-00581259/document https://hal.inria.fr/inria-00581259/file/forte-hal.pdf doi:10.1007/978-3-642-21461-5_13 |
op_rights |
http://creativecommons.org/licenses/by/ info:eu-repo/semantics/OpenAccess |
op_doi |
https://doi.org/10.1007/978-3-642-21461-5_13 |
container_start_page |
198 |
op_container_end_page |
212 |
_version_ |
1766039675839971328 |