Markov Nets: Probabilistic Models for Distributed and Concurrent Systems

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 networks, 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 true concurrency 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