SBAM Algorithm Overview

From PLSwiki

This page attempts to give an overview of the algorithms in SBAM. The main algorithm is a variation of the Gillespie algorithm.

Note that we prioritize as follows:

• we aim at fast simulation possibly at the cost of memory usage
• initialization is allowed to be costly, if it improves the simulation speed

Main Algorithm (Gillespie)

We assume given a concrete Stochastic BRS = (Κ , R = {r_i = (R_i , R'_i, ρ_i)}) and a concrete agent a, and a stop time t_stop.

First, we give a naive version of the algorithm to illustrate the basic ideas. Afterwards, we will refine the algorithm incrementally, until we reach a description of the algorithm that is used in SBAM.

Basic algorithm

1. Initialization
   1. Set the time variable t := 0

   2. For each rule r_i ∈ R
      1. Find and store all distinct injections (up to automorphisms) of the redex into the agent: M(i,a) = {φ_i,j : |R_i|_V → |a|_V | φ_i,j(R) ⊆ a}

   3. Set the system activity variable α := ∑_i |M(i,a)| ⋅ ρ_i

2. Monte Carlo step
   1. Choose a rule at random according to the distribution P(r_i) = ^{|M(i,a)| ⋅ ρ_i} / _α

   2. Choose an injection φ_i,j ∈ M(i,a) at random according to a uniform distribution

3. Update
   1. For all injections φ_i',j' that rely on the part of the agent to be rewritten: cod(φ_i',j') ∩ cod(φ_i,j) ≠ ∅
      1. remove φ_i',j' from M(i',a)
      2. decrease the system activity accordingly: α := α - ρ_i'

   2. Rewrite the agent: a[^φ(R'_i) / _φ(Ri)]

   3. For each rule r_i' ∈ R
      1. Find and store all distinct injections (up to automorphisms) of the redex into the changed part of the agent: M(i',a) += {φ_i',j' : |R_i'|_V → |a|_V | φ_i',j'(R) ⊆ a and cod(φ_i',j') ∩ cod(φ_i,j) ≠ ∅}

   4. Update time: t -= log(random) / α

      where random is uniformly distributed on the interval (0,1].

4. Iterate

   If t > t_stop stop the simulation; otherwise repeat from step 2.

Improvements to the basic algorithm

Edit-scripts instead of substitutions

When applying a rule, we can execute an edit-script instead of substituting reactum for redex. This enables us to change the agent minimally.

Minimal edit-scripts can be computed from the abstract reaction rules in the initialization phase ([Zhang 1996] might provide the basis for an efficient algorithm).

Lifts

By maintaining a map from agent nodes and edges to injections, we can quickly identify the injections that will be invalidated by a change to the agent.

Wake-up map

For each rule r_i we can pre-compute the set W(r_i) = {r_j} of rules which might have new injections after a rewrite using r_i.

Square approximation

To reduce the number of injections that must be stored, we can attempt to factor families of injections into products of injections.

E.g. instead of representing all injections of K || L explicitly, it would be more space-efficient to store the injections of K and L separately (though this might create some non-events, e.g. if some K's are decendants of L's or vice-versa).