Towards Scalable Simulation of Stochastic Bigraphs
TR-2011-148, Authors: Espen Højsgaard and Jean Krivine
Towards Scalable Simulation of Stochastic Bigraphs
Espen Højsgaard
Jean Krivine
December 2011
Abstract
We report on the progress of the development and implementation of an efficient and scalable simulation algorithm for stochastic bigraphical reactive systems (BRSs).
The starting point is the stochastic simulation algorithm for the κ-calculus by Danos et al. (henceforth KaSim). Since the κ-calculus is a graphical formalism with a straightforward BRS representation, we are hopeful that their algorithm generalizes to BRSs. The KaSim algorithm relies on a number of concepts that have not previously been developed for BRSs: embeddings, localized matching, redex and agent modifications, and fine-grained conflict/causality analysis at the level of rules exploiting the notion of modification. In this report, we rigorously develop bigraph embeddings and redex/agent modifications, give an algorithm for localized matching, and outline a fine-grained conflict/causality analysis.
Our implementation strategy is to represent the bigraphical structures as directly as possible, as we believe that this eases implementation and increases trust in correctness. However, it is difficult to directly represent the structures of the usual presentation of the theory of BRSs: any non-trivial BRS contains an infinite number of ground reaction rules, since the set of rules must be closed under support equivalence and a parametric reaction rules generates an infinite set of ground reaction rules. In addition, the usual presentation of the dynamic theory of BRSs combines poorly with the stochastic semantics: the stochastic semantics rely on support, i.e. concrete bigraphs, while dynamics are defined up to support equivalence. We therefore develop, and prove equivalent, an alternative dynamic theory for BRSs without these problems: (i) the set of rules need not be closed under support equivalence, (ii) parametric reaction rules are first-class citizens, and (iii) integrates a (generalized) stochastic semantics. The development is based on the more general theory of reactive systems, and is thus applicable in more settings than just (stochastic) BRSs.
The completed parts of our work have been implemented in a prototype called the Stochastic Bigraphical Abstract Machine (SBAM), which currently allows stochastic simulation of BRSs where each redex consists of a single connected component and is solid, i.e. matches are determined by support translations of its nodes.
Technical report TR-2011-148 in IT University Technical Report Series, December 2011.
Available as PDF.