forte2011

G. Kalyon, T. Le Gall, H. Marchand, T. Massart. Global State Estimates for Distributed Systems. In 31th IFIP International Conference on FORmal TEchniques for Networked and Distributed Systems, FORTE, LNCS, Volume 6722, Pages 198-212, Reykjavik, Iceland, June 2011.

Download [help]

Download paper: Doi page

Download paper: Adobe portable document (pdf)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
This page is automatically generated by bib2html v216, © INRIA 2002-2007, Projet Lagadic

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

Contact

Hervé Marchand http://www.irisa.fr/prive/hmarchan

BibTex Reference

@InProceedings{forte2011,
   Author = {Kalyon, G. and Le Gall, T. and Marchand, H. and Massart, T.},
   Title = {Global State Estimates for Distributed Systems},
   BookTitle = {31th IFIP International Conference on FORmal TEchniques for Networked and Distributed Systems, FORTE},
   Volume = {6722},
   Pages = {198--212},
   Series = {LNCS},
   Publisher = {Springer},
   Address = {Reykjavik, Iceland},
   Month = {June},
   Year = {2011}
}

EndNote Reference [help]

Get EndNote Reference (.ref)