Branching cells as local states for event structures and nets: probabilistic applications

Samy Abbes (1) , Albert Benveniste (2)

1 PPS - Preuves, Programmes et Systèmes
2 DISTRIBCOM - Distributed and Iterative Algorithms for the Management of Telecommunications Systems

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. 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.

Mots clés: Probabilistic event structure; branching cell; Markov net

Domaines: Réseaux et télécommunications [cs.NI]

Samy Abbes, Albert Benveniste. Branching cells as local states for event structures and nets: probabilistic applications. Foundations of Software Science and Computation Structures, Apr 2005, Edinburgh, United Kingdom. pp.95-109. ⟨hal-00350930⟩