The Beacon Calculus​

Download and Installation

bcs is hosted on Github.  To clone bcs into your current directory, run​

git clone https://github.com/MBoemo/bcs.git

Navigate to the bcs directory and run

make

This will compile bcs and put a binary into the bcs/bin directory.  bcs was written in C++11 and uses OpenMP for parallel computation.  These are both standard on most systems and there are no other thirdparty dependencies.  bcs was tested to compile on both Linux systems and OSX.

Simulating a First Model

bcs models should be written and saved in a separate file.  These files are passed to the bcs binary on the command line.  A few models are included with the software; let's run one.  Navigate to the bcs directory and run

bin/bcs -s 50 -t 1 -o firstSimulation tests/beacons/basic_beacons.bc

Here, we've specified the path to a model file (tests/beacons/basic_beacons.bc), the number of simulations we want to run (50), and the number of threads to use (1).  There should now be a file called firstSimulation.simulation.bcs in your current directory.  If we open this file, the first few lines should look like this:

>=======

0.015743        msg     proc2   j       3
0.151068        action2 proc2   j       3
0.160805        msg     proc1   j       3
1.14175e+06     longAction      proc1   j       3
>=======
0.202562        msg     proc2   j       3
0.231809        action2 proc2   j       3
0.315113        msg     proc1   j       3
303730  longAction      proc1   j       3
>=======
0.0960461       msg     proc2   j       3
0.11236 msg     proc1   j       3
0.229927        action2 proc2   j       3
569664  longAction      proc1   j       3

bcs output files all have the same format, where the start of each new simulation is marked with ">=======" and each row contains information about an action that a process performed during the simulation.  From left to right, the tab-delimited columns specify the following information:​ the time when an action was done, the action name (if it was a non-messaging action) or channel name (if it was a handshake or beacon action), the process name that performed the action, the value of that process's parameters (if it has any) when the action was performed. Now that we have something working, let's go through the structure of a beacon calculus model.

Variable Definitions, Line Termination, and Whitespace

A bcs model, from top to bottom, consists of three sections:

definition of static variables,

definition of processes,

system line (that is, the initial processes that are in the system at t=0).

In bcs, lines must be terminated by semicolons and any whitespace/newlines are ignored.  If we want to define some variable x that will be used by a process, the three lines 

x = 5;

x                 = 5;

x

=

5;

are all acceptable.  Variables may be assigned either a float or an int, so assigning 

x = 3.452;

 

is certainly acceptable.  Variable names must either lead with an underscore or a letter.  Thereafter, they can contain letters and numbers.  However, leading with a number is not acceptable.  The following variable names are valid:

myVar

_myVar

__myVar

m1yVar99

But a variable name such as 99myVar is not.

Process Definitions and Basic Combinators

In the beacon calculus, components within a biological system are modelled as processes that can perform actions.  An action is an ordered pair that specifies the action name followed by the rate.  For example, we might define a process P as follows:

P[] = {exampleAction, 5};

This process can perform a single action called "exampleAction" at rate 5, where rates are always the parameters of an exponential distribution.  Once this process performs exampleAction, it cannot perform any other actions.  It is therefore said to be deadlocked and is removed from the system.

A process that can only perform one action isn't particularly useful, especially for biological systems.  We need a way to stitch series of actions together so that processes can perform complex behaviours.  We define the following three combinators:

  • Prefix ".", where P[] = {a,ra}.{b,rb} is a process that performs action a at rate ra and then, once it has finished, performs action b at rate rb.  Prefix is therefore used for actions that should happen in sequence.

  • Choice "+", where P[] = {a,ra} + {b,rb} is a process that makes an exclusive choice between performing action a at rate ra and action b at rate rb; it cannot perform both.  Note that the probability of picking action a is equal to ra/(ra+rb), so we can bias which outcome is more likely by scaling the actions' relative rates.

  • Parallel "||", where P[] = {a,ra} || {b,rb} is a process where actions a and b are performed in parallel at their respective rates.

Using these three combinators, we can now define more complex processes.  In the following example,

P[] = {a,ra}.{b,rb} || {c,rc}.{d,rd} + {e,re}.({f,rf} + g,rg})

we make an exclusive choice between actions c and e.  If we pick c, then we perform action d.  If we pick e, then we make another choice between f and g.  All the while, in parallel, we perform action a followed by action b.

Parameters and Gates

Oftentimes, processes need to keep track of certain quantities.  For example, if a process models the amount of a certain chemical reactant in a system, the process must be able to keep a count of how many molecules of this reactant are present over time.  If a process models a DNA replication fork, it has to keep track of where the replication fork is on the chromosome.  This is achieved through parameters, which are values that a process keeps track of.  Parameters are specified between square brackets, and processes can increase or decrease the value of their parameters over time.  They can also use the value of their parameters in the computation of rates.

Suppose there is a car which is at a particular location.  We can express this as Car[i], where the Car process has parameter i which specifies the car's location.  We can specify movement of the car through recursion.  The following process models a car that drives at rate 0.1, and increases its parameter value as it moves.

Car[i] = {drive,0.1}.Car[i+1]

 

This car, as it is modelled above, will keep driving without stopping.  We may wish to specify, for example, that the car should stop when it reaches a bus stop at i=10.  To express this, we use a gate:

 

Car[i] = [i < 10] -> {drive,0.1}.Car[i+1]

 

The gate in front of the drive action specifies that this action can only be performed if the gate's condition is satisfied.  In this case, the value of the car's parameter i must be less than 10.  If the car starts at i=0, then the car continues driving until i=10 at which time the gate's condition is no longer satisfied.  The car can no longer perform any actions, so the process deadlocks and the simulation stops.

In addition to the less than comparison used here, bcs supports the following logical operators:

  • <=, less than or equal to,

  • ==, equal to,

  • !=, is not equal to,

  • >, greater than,

  • >=, greater than or equal to,

  • &, logical and,

  • |, logical or.

 

Note that the above example only made sense when we considered the car's starting location of i=0.  What if the car were to start at i=15?  Then the Car process would deadlock immediately.  Clearly, we need some way of specifying the initial state of the system if we're going to make useful models.

The System Line

The initial state of a beacon calculus system is specified using a system line.  The system line specifies the processes present in the system at t=0, how many of each process we have, and their parameter values.  For example, to finish the car model above, a complete piece of beacon calculus simulator source code is:

driveRate = 0.1;

Car[i] = [i < 10] -> {drive,0.1}.Car[i+1];

Car[0];

The first line specifies a variable definition.  The second line specifies the process definition for a car as we've done previously.  The third and final line is the system line which specifies that at t=0, there is one copy of a car process in the system and the value of its parameter is i=0.  Suppose instead we wanted 50 cars, each of which start at i=0.  Then we can write:

driveRate = 0.1;

initialCars = 50;

Car[i] = [i < 10] -> {drive,0.1}.Car[i+1];

initialCars*Car[0];

If we wanted 50 cars to start at i=0 and 20 cars to start at i=5, we can write:

driveRate = 0.1;

initialCars = 50;

Car[i] = [i < 10] -> {drive,0.1}.Car[i+1];

initialCars*Car[0] || 20*Car[5];

Communication via Handshakes

Processes need to be able to interact with one another.  In doing so, they can change their actions in response to other processes.  In the beacon calculus, two processes can communicate synchronously (at the same time) via handshake actions:

  • A handshake send action {@chan![i], rs} sends value i on channel chan at rate rs.

  • A handshake receive action {@chan?[S](x), rr} receives one of a set of values S on channel chan at rate rr and binds the result to x.

If the handshake happens, the handshake receive and handshake send actions happen together at rate rs*rr. 

 

Let's clear the air with an example.  A surveyor has been tasked to count the number of cars that travel down a road over time.  They surveyor is located at i=5, and performs a handshake with each car as it goes by.

driveRate = 0.1;

initialCars = 50;

fast = 10000;

Car[i] = [i < 10 & i!= 5] -> {drive,driveRate}.Car[i+1]

       + [i==5] -> {@count![0],fast}.{drive,driveRate}.Car[i+1];

Surveyor[c] = {@count?[0],1}.Surveyor[c+1];

initialCars*Car[0] || Surveyor[0];

This model beings with 50 cars at i=0 and a surveyor that has counted 0 cars.  If a car isn't at i=0 then it steps as normal.  If the car is at i=0 then it handshakes with the surveyor at a fast rate using channel count.  Both the actions {@count![0],fast} and {@count![0],fast} happen simultaneously at rate fast*1 = fast.  Once both a car and the surveyor perform the handshake, the surveyor increases their count by one by incrementing parameter c and recursing. The car carries on driving as normal.

In the above example, the handshake could receive a single value (0) on channel count.  However, as mentioned above, handshakes can accept a set of values on a particular channel.  Suppose the surveyor wants to keep a separate count of cars that are red.   Consider the following model:

driveRate = 0.1;

nonRed= 25;

red= 25;

fast = 10000;

Car[i,r] = [i < 10 & i!= 5] -> {drive,driveRate}.Car[i+1]

         + [i==5] -> {@count![r],fast}.{drive,driveRate}.Car[i+1];

Surveyor[c,cr] = {@count?[0..1](x),1}.Surveyor[c+1,cr+x];

nonRed*Car[0,0] || red*C[0,1] || Surveyor[0,0];

The Surveyor process has two parameters, c and cr, which keeps track of the total count and red cars, respectively. Car has an additional parameter r which is either 1 (red) or 0 (not red).  The range operator ".." in {@count?[0..1](x),1} means the set of all consecutive integers between 0 and 1 (inclusive).  In this case, this is the set {0,1}.  So the handshake receive action accepts one of two possible values and binds what it receives to x for later use.  If the car it handshakes with is red, it receives value 1.  When the surveyor process recurses, x=1 so it increments the red car count cr by one.  If the car was not red, then the value received would have been 0 so that x=0 when the the process recurses.  Therefore, cr+x = cr+0 = cr so the red car count is not increased.

In addition the range (..) operator used above, bcs supports the following set operations for both beacons and handshakes:

  • U, set union, 

  • I, set intersection,

  • \, set subtraction.

For example, the following beacon calculus operations (left hand side) correspond to these sets (right hand side):

  • -5..2 = {-5,-4,-3,-2,-1,0,1,2}

  • 1U8..10 = {1,8,9,10}

  • 1I8..10 = {}

  • 1\8..10 = {1}

  • 15..18\16 = {15,17,18}

  • 0..2U8..15I4..9 = {0,1,2,8,9}​

Communication via Beacons

Handshakes provide the means for synchronous communication between processes, whereby two processes each perform handshake actions at the same time.  The beacon calculus also allows processes to communicate via beacons, which is asynchronous communication.  Any process can launch a beacon that transmits a value on a channel.  The beacon stays active until it is explicitly killed by a process (not necessarily the same process that launched it).

  • A beacon launch, {chan![i],rs} launches a beacon that transmits value i on channel chan at rate rs.

  • A beacon kill, {chan#[i],rs} kills a beacon (if there is one) transmitting value i on channel chan at rate rs.

Once a beacon is launched, processes can interact with active beacons in two ways.

  • A beacon receive, {chan?[S](x),rr}, can only be performed if there is an active beacon on channel chan transmitting a value in set S.  If there is such a beacon, a process can perform the beacon receive action and bind the value it receives to x for later use.

  • A beacon check, {~chan?[S],rr}, is the inverse of a beacon receive.  This action can only be performed if there is no active beacon on chan transmitting any value in S.

While a beacon is active, it can be received any number of times by any number of processes.  Once a beacon has been killed, it can no longer be received.  

Let's consider an example.  Suppose there is a traffic light at i=5 that switches between red and green.  Cars can only pass through the intersection at i=5 when the light is green.  Otherwise, they have to wait.

driveRate = 0.1;

change = 0.001;

initialCars = 50;

fast = 10000;

Car[i] = [i < 10 & i!= 5] -> {drive,driveRate}.Car[i+1]

         + [i==5] -> {~red?[0],driveRate}.Car[i+1];

TrafficLight[g] = [g==1] -> {green#[0],change}.{red![0],fast}.TrafficLight[0]

                + [g==0] -> {red#[0],change}.{green![0],fast}.TrafficLight[1];

initialCars*Car[0] || TrafficLight[0];

In the above model, there is a process TrafficLight with a parameter g.  When g=1, the traffic light is showing green.  When g=0, the traffic light is showing red.  If the traffic light is showing green, it keeps a beacon active on channel green.  When the traffic light switches, it kills the beacon on green and launches a new one on channel red.  Switching from red back to green is similar.  In order for a car to move through the intersection at i=5, it performs a beacon check to make sure the light is not red.  If the light is red, the car has to wait until the light turns green as it cannot perform the beacon check action while there is an active beacon on channel red.  

In this example, we could have created a model where the traffic light handshakes with each car rather communicate via beacons.  However, this would have been slightly cumbersome.  Beacons make it easy and concise to communicate a state change to a (potentially large) number of other processes.

Functions and Operators

While some of these functions and operators were mentioned and used above, this section lists those that bcs currently supports. 

 

In rate expressions and gates:

  • max(x,y), the maximum of a and b,

  • min(x,y), the minimum of a and b,

  • abs(x), the absolute value of x,

  • sqrt(x), the square root of x.

In handshake receives and beacon receives:..

  • .., range,

  • U, set union, 

  • I, set intersection,

  • \, set subtraction.

In rate expressions, gates, and handshake/beacon receives:

  • +, sum,

  • -, difference,

  • *, product,

  • /, quotient,

  • ^, exponents.

Example: Chemical Reactions

Suppose we have molecule A that binds to molecule B rate k1 to form molecule AB.  The reverse reaction can occur at rate k2 whereby molecule AB unbinds into molecule A and molecule B.

A + B --> AB

AB --> A + B

In the Beacon Calculus, we can represent each chemical species as a process.  The reaction between two chemical species can be modelled using a handshake.

k1 = 0.1;

k2 = 0.01;

A[] = {bind![0],k1};

B[] = {bind?[0],1}.AB[];

AB[] = {unbind,k2}.(A[] || B[]);

100*A[] || 100*B[];

The above model starts by defining reaction rates k1 and k2 (Lines 1-2).  We define process A on Line 4, which only performs one action: it sends a handshake on channel bind at rate k1.  Process B is defined on Line 5, which can receive a handshake on channel bind at rate 1.  Recall that the rate of a handshake between to processes is the product of the rates of the handshake send and handshake receive actions.  Hence, the handshake between A and B will happen at 1*k1 = k1.  After the handshake, process B carries on as process AB, which we define on Line 6.  Process AB can only perform one action: it unbinds at rate k2.  When it unbinds, it carries on as processes A and B in parallel, thereby recreating molecules A and B.  The system line on Line 8 specifies that the initial state of the system is 100 of process A and 100 of process B.

We can download the above model and simulate the model 50 times over a time span of 0 to 500 using the Beacon Calculus Simulator by running:

bcs -s 50 -d 500 -o simple_reaction simple_reaction.bc

This will produce a file in the current directory called simple_reaction.simulation.bcs.  Let's plot the results to see the average amount of A, B, and AB over time.

logo.png
  • GitHub-Mark-Light-64px

© Copyright 2019 Michael A. Boemo

Capture2_transparent_50perc_edited.png