Still updating.

When Concurrency Matters: Behaviour-Oriented Concurrency

OOPSLA at 2023.

TLDR; The paper introduces BoC a new concurrency paradigm akin to actor model, while being able to update multiple actors in a single transaction. From the formal semantics BoC is guaranteed to be deadlock free.

This blog post will be about how to use Verona runtime and it’s scheduling mechanisms.

Simple Example

There are two main repos for Verona:

• verona → this the language implementation, backed with LLVM
• verona-rt → this the runtime implemented in c++

In this writing we’ll mostly focus on the runtime. To make a simple example just clone this repo:

git clone https://github.com/m8/verona-skeleton

Build

mkdir build; cd build
cmake ..
make
./bench

Now we can see a Hello World message in our terminal

Dive

Verona runtime exposes it’s headers to cpp programs. So you can use Verona runtime in your cpp programs. First, basically include these headers.

#include <verona.h>
#include <cpp/when.h>

After that you need to initialize the verona runtime, and it’s scheduler to do that:

auto& sched = Scheduler::get();
sched.init(1);

You can add several parameter while starting the runtime as well (This section will be detailed a bit more):

Scheduler::set_detect_leaks(true);
sched.set_fair(true);

Now we come to essential part of the Verona runtime. Verona defines these concepts: - Cown: concurrent owners, protect data for accessed by concurrently. - Behaviour: async unit of work. which explicitly takes it resources. Constructed with when keyword.

From the paper: > BoC program is a collection of behaviours that each acquires zero or more resources, > performs computation on them, which typically involves reading and updating them, and spawning new behaviours, before releasing the resources.

Basically BoC = ⋃_iB_i

You can create behaviours with when statement like this:

when() << [=]() {
    std::cout << "Hello World" << std::endl;
};

And create cown with:

auto a = make_cown<Account>();
auto b = make_cown<Account>();
a.balance = 100; // This will throw an error

And to modify a cown you need to use when statement

when(a) << [&](auto _a) {
    _a->balance = 100;
};

You can define multiple cown s into when statement as well.

void transfer(cown_ptr<Account> from, cown_ptr<Account> to, int amount)
{
  when(from, to) << [from = std::move(from), to = std::move(to), amount](auto f, auto t) {
    if (f->balance >= amount)
    {
      f->balance -= amount;
      t->balance += amount;
    }
  };
}

These behaviors (when statements) are async operations however there are some rules which BoC defines:

• Rule 1: A behaviour Z will happen before another behaviour Y iff Z and Y require overlapping set of cown AND Z spawned before Y.

To understand the rule let’s make an example where: - Initially account A has 100, B has 50 - After account A sends 50 to account B - After account B sends 25 to account A

---
(A)
======
| when(a) << [=](auto a) {
|     a->balance = 100;
|   printf("A balance: %d\n", a->balance);
| };
======
(B)
======
| when(b) << [=](auto b) {
|   b->balance = 100;
|   printf("B balance: %d\n", b->balance);
| };
=======
(C)
transfer(a, b, 50);
(D)
transfer(b, a, 25);

So from the Rule 1 there might two different executions for this program. A and B do not share common cowns so they can be scheduled in different orders. However C and D shares the overlapping cowns with the states. So their order will be the same with respected to how they called in a source code. In our example C called before D that it will be executed before D as well.

## Execution Timeline

 1    2   
(A)  (B)
(B)  (A)
(C)  (C)
(D)  (D)

Another example, let’s suppose we have 2 threads we have such cowns:

cowns: a, b, c

1) when(a)
2) when(b)
3) when(b,c)
4) when(a,b)
5) when(a,b,c)

Now in two threads we can execute like that:

 Thread 1    Thread 2
   (1)         (2)
   (3)          x
   (4)          x
   (5)          x

How it works? Verona runtime implements Directed acylic graph (DAG) to keep track the dependencies. Similar to example 2, we can see nice visualization from the BoC paper. [[Pasted image 20240203105122.png]]