Global State Estimates for Distributed Systems

Research Publications
08/31/2011

Global State Estimates for Distributed Systems

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, Reykjavik, Iceland, June 2011.

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.

bibtex

@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},
    Address = {Reykjavik, Iceland},
    Month = {June},
    Year = {2011}
} 

Files

main.pdf - Forte'11 (484.5 kB) Tristan Le Gall, 08/31/2011 06:14 pm