MOVES Seminar 26 April, 2011
Pure Probabilistic Models for Concurrent Systems
My former student Samy Abbes (now teaching assistant in Paris VI University) has developed a beautiful theory of probabilistic concurrent systems. By this we mean that executions are not sequences of events (as in interleaving semantics) but rather partial orders of events. By "pure" we mean that all the non-determinism is randomized. In particular, such models do not involve schedulers, unlike Probabilistic Automata (also known as Markov Decision Processes). I shall present two facets of the theory. In the second part I shall present the theory of probabilistic event structures and Markov nets, for which a comprehensive theory exists, including classic limit theorems of statistics (renewal, law or large numbers). In the first part, I shall focus on the problem of composing or synchronizing Markov chains to get a pure probabilistic model. I show that the framework of MDP does not provide the answer. Our answer is incomplete, however, since we only have a construct for the product of 2 chains. I shall be happy to discuss possible uses of those theories and the technical difficulties we are facing for its extensions.
My former student Samy Abbes (now teaching assistant in Paris VI University) has developed a beautiful theory of probabilistic concurrent systems. By this we mean that executions are not sequences of events (as in interleaving semantics) but rather partial orders of events. By "pure" we mean that all the non-determinism is randomized. In particular, such models do not involve schedulers, unlike Probabilistic Automata (also known as Markov Decision Processes). I shall present two facets of the theory. In the second part I shall present the theory of probabilistic event structures and Markov nets, for which a comprehensive theory exists, including classic limit theorems of statistics (renewal, law or large numbers). In the first part, I shall focus on the problem of composing or synchronizing Markov chains to get a pure probabilistic model. I show that the framework of MDP does not provide the answer. Our answer is incomplete, however, since we only have a construct for the product of 2 chains. I shall be happy to discuss possible uses of those theories and the technical difficulties we are facing for its extensions.
