Branching cells as local states for event structures and nets:
probabilistic appplications
Samy Abbes and Albert Benveniste
We study the concept of choice for true
concurrency models such as prime event structures and safe Petri nets.
We propose a dynamic variation of the notion of cluster previously
introduced for nets. This new object is defined for event structures,
it is called a branching cell.
Our aim is to bring an interpretation of branching cells as a right
notion of ``local state'', for concurrent systems.
We illustrate the above claim through applications
to probabilistic concurrent models. In this respect, our results
extends in part previous work by Varacca-Völzer-Winskel on
probabilistic confusion free event structures. We propose a
construction for probabilities over so-called locally finite event structures
that makes concurrent processes probabilistically independent -- simply
attach a dice to each branching cell; dices attached to concurrent branching cells are
thrown independently. Furthermore, we provide a true concurrency
generalization of Markov chains, called Markov nets. Unlike in existing
variants of stochastic Petri nets, our approach randomizes Mazurkiewicz
traces, not firing sequences. We show in this context the Law of Large
Numbers (LLN), which confirms that branching cells deserve the status
of local state.
Our study was motivated by the stochastic modeling
of fault propagation and alarm correlation in telecommunications
networks and services. It provides the foundations for probabilistic
diagnosis, as well as the statistical distributed learning of such
models.
pdf