Markov Nets: Probabilistic Models for distributed and concurrent systems


Albert Benveniste, Eric Fabre, Stefan Haar

For distributed systems, i.e.  large networked complex systems,  there is a drastic difference between a local view and knowledge of the system, and its global view. Distributed systems have local state and time, but do not possess global state and time in the usual sense : it is simply not possible to determine, at any given instant,  what the current global state of a telecommunication network is !

In this paper, motivated by the monitoring of distributed systems and in particular of telecommunications network, we develop an extension of Markov chains and hidden  Markov models (HMM) for distributed and
concurrent systems. By a concurrent system, we mean a system in which components may evolve independently, with sparse synchronizations.

We follow a so-called trueconcurrency approach, in which no global state and no global time is available. Instead, we use only local states in combination with a partial order model of time, in which local events
are ordered if they are either generated on the same site, or related via some causality relation. Our basic mathematical tool is that of Petri net unfoldings.

This work is partially supported by RNRT (National Research Network in Telecommunication) through the MAGDA  project (Modelling and Learning for a Distributed Management of Alarms). The paper was prepared in honour of Alain Bensoussan, for his 60th birthday.

   Extended version - report (pdf)
  IEEE Trans. on AC paper (pdf)
 transparents (postscript)