Skip to main content ITU
Logo
  • Programmes
    • BSc Programmes
    • BSc in Global Business Informatics
    • BSc in Digital Design and Interactive Technologies
    • BSc in Software Development
    • BSc in Data Science
    • Applying for a BSc programme
    • MSc Programmes
    • MSc in Digital Innovation & Management
    • MSc in Digital Design and Interactive Technologies
    • MSc in Software Design
    • MSc in Computer Science
    • MSc in Data Science
    • MSc in Games
    • Applying for an MSc programme
    • Student Life
    • Women in tech
    • Student organisations at ITU
    • Labs for students
    • Practical Information for International Students
    • Ask a student
    • Study Start
    • Study and Career Guidance
    • Guest Students
    • Who can be a Guest Student
    • ITU Summer University
    • Exchange Student
    • Become an exchange student at ITU
    • Open House
    • Open House - MSc programmes
    • Open House - BSc programmes
  • Professional Education
    • Master in IT
    • Master in IT Management
    • Single Subjects
    • About single subjects
    • Contact
    • Contact us here
  • Research
    • Departments
    • Business IT Department
    • Computer Science Department
    • Digital Design Department
    • Research entities
    • Research Groups
    • Labs
    • Research Centres
    • Centre for Digital Play
    • Center for Climate IT
    • Center for Computing Education Research
    • Centre for Digital Welfare
    • Centre for Information Security and Trust
    • European Blockchain Centre
    • Danish Institute for IT Program Management
    • ITU Research Portal
    • Find Researcher
    • Find Research
    • Research Ethics and Integrity
    • Good Scientific Practice
    • Technical Reports
    • Technical Reports
    • PhD Programme
    • About the PhD Programme
    • PhD Courses
    • PhD Defences
    • PhD Positions
    • Types of Enrolment
    • PhD Handbook
    • PhD Support
  • Collaboration
    • Collaboration with students
    • Project collaboration
    • Project Market
    • Student worker
    • Project postings
    • Job and Project bank
    • Employer Branding
    • IT Match Making
    • Hiring an ITU student or graduate
    • Make a post in the job bank
    • Research collaboration
    • Licensing Opportunities
    • Open Entrepreneurship
    • Research collaboration
    • Industrial PhD
    • Hire an Industrial PhD
    • Innovation and entrepreneurship
    • ITU Business Development
    • ITU Startup
  • About ITU
    • About ITU
    • Press
    • Vacancies
    • Contact
  • DK
ITU
ITU  /  Research  /  Technical Reports  /  Technical Reports Archive  /  2011  /  Towards Scalable Simulation of Stochastic Bigraphs
  • Research
    • Research Departments
    • Research Ethics and Integrity
    • Good Scientific Practice
    • Research Groups and Centers
    • Labs
    • Technical Reports
      • Technical Reports Archive
        • 2023
        • 2021
        • 2018
        • 2017
        • 2016
        • 2015
        • 2014
        • 2013
        • 2012
        • 2011
          • Linear Contextual Modal Type Theory
          • The lambda sigma-Calculus and Strong Normalization
          • Towards Scalable Simulation of Stochastic Bigraphs
            • Calculation in the Informatic Jungle
            • Mesh Mobs - Virtually augmented crowds
            • The BPL Tool: A Tool for Experimenting with Bigraphical Reactive Systems
            • Variability for You
            • Modeling Test Cases for Voting
            • Spreadsheet technology
            • Vellykkede vekselvirkninger? - Om arbejdspraksis og it-støtte i beskæftigelsesindsatsen
            • Core BPEL - Semantic Clarification of WS-BPEL 2.0 through Syntactic Simplification using XSL Transformations
          • 2010
          • 2009
          • 2008
          • 2007
          • 2006
          • 2005
          • 2004
          • 2003
          • 2002
          • 2001
          • 2000
      • PhD Programme

    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.

    Contact us

    Phone
    +45 7218 5000
    E-mail
    itu@itu.dk

    All contact information

    Web Accessibility Statement

    Find us

    IT University of Copenhagen
    Rued Langgaards Vej 7
    DK-2300 Copenhagen S
    Denmark
    How to get here

    Follow us

    ITU Student /
    Privacy /
    EAN-nr. 5798000417878/
    CVR-nr. 29 05 77 53 /
    P-nummer 1005162959

    This page is printed from https://itu.dk/