Day 11 – Counting up concurrency

by Hillel Wayne

Consider the 4-step process S = abcd and the 3-step process T = xyz. The processes run concurrently and can interleave at any point, but must execute in sequence.

So abxcyzd is a valid interleaving, but baxcyzd is not. Also, steps in different processes can occur simultaneously: abxcyzd is different from a[bx]cyzd. How many valid interleavings are there?

I ran into this problem while studying models of communicating processes. I looked for an elegant mathematical formula for this, and not finding any, decided to brute force it in Raku instead.

Solving the problem

The first insight is that we’re that the actual names of the steps don’t matter. We’re not trying to list all of the interleavings, just count them. So we can represent the starting state of the system as (4, 3): abcd has four steps remaining and xyz has three. Let ct(S, T) be the total number of interleavings of processes of S and T.

1. S takes a step. The new state is (3, 3).
2. T takes a step. The new state is (4, 2).
3. S and T take simultaneous steps. The new state is (3, 2).

From there, we recursively repeat the process: ct(4, 3) = ct(3, 3) + ct(4, 2) + ct(3, 2).

Now for the base cases. If S and T are empty, there’s only one possible program execution: the one where nothing happens. ct(0, 0) = 1.

What if S=1000 and T=0? While we still have a lot of steps to go, there’s only one possible way to “interleave it”: execute S sequentially. ct(x, 0) = ct(0, x) = 1.

Now let’s put it all into a script:

multi sub gc($s, $t) {
  if $s|$t == 0 {
    1
  }
  else {
    sum samewith( $s-1, $t-1 ),
        samewith( $s-1, $t   ),
        samewith( $s,   $t-1 );
  }
}

The only “Raku tricks” here is samewith, which is just an easy way to do self recursion, and that $S|$T == 0 is a junction. Let’s try it!

> put (gc(1, 1), gc(1, 2), gc(1, 3));
3 5 7
> put (gc(2, 2), gc(2, 3), gc(2, 4));
13 25 41
> put (gc(3, 3), gc(3, 4), gc(3, 5));
63 129 231

Isn’t this the advent calendar?

You’re not here for a math problem, you’re here to see Raku. So let’s make the problem more complicated. Instead of two processes, we have N, and any number of them can take a set simultaneously. The same overall logic applies: for ct(3, 2, 1)we’d calculate:

ct(3, 2, 1) = 
  sum ct(3, 2, 0),
      ct(3, 1, 1),
      ct(2, 2, 1),
      ct(3, 1, 0),
      ct(2, 2, 0),
      ct(2, 0, 1),
      ct(2, 1, 0);

Whew! So there’s a couple new problems here. The first is that for N processes, we have to sum 2^N – 1 terms. That’s not something we can hardcode. Second, some processes are “exhausted early”. But if there’s more than one process left, we can’t just replace it with a 1. ct(2, 1, 0) still needs to be computed, and we shouldn’t sum in a ct(2, 1, -1) term.

Instead, we need to find every possible combination of processes with at least one step left. As we’ll see later, we specifically want the indices of these processes. Fortunately, Raku makes this easy:

> [3, 0, 1, 2].grep(* > 0, :k).combinations(1..*)
((0) (2) (3) (0 2) (0 3) (2 3) (0 2 3))

There’s a lot going on here, so let’s break it down:

• .grep filters a list.
  • * > 0 is a Whatevercode, so this is lifted into the block { $_ > 0 }.
  • Passing the :k argument makes it return indices instead of values (the “k” is short for “keys”).
• .combinations(1..n) returns every unordered combination of 1, 2, … n values.
  • 1..* is equivalent to 1..Inf, aka all possible combinations

Now given a possible combination of indices, how can we decrement just those indices? One way:

my $proc = [3, 1, 0, 2];
say gather for $proc.grep(* > 0, :k).combinations(1..*) {
  my $new = $proc.clone;
  $new[$_]>>--;
  take $new;
}
# ([2 1 0 2] [3 0 0 2] [3 1 0 1] [2 0 0 2] [2 1 0 1] [3 0 0 1] [2 0 0 1])

Again, a lot going on in a small space.

• gather and take turn a block into a sequence generator. The for loop now returns every value that’s taken as a single sequence.
• $new[$_] takes advantage of takes advantage of “slices”: positional lookups can take a list of values, and then returns those elements in order. Critically, this returns element references, meaning we can mutate the original (cloned) array.
  • >>-- is a hyperoperator over postfix --, decrementing each element corresponding to the combination.

In the actual algorithm we don’t need to retrieve the new values, just their gcs, so we can instead take the samewith and sum over them.

Finally, we can’t just check $S|$T > 0. We instead want to check at most one process length is greater than 0. This is easy with junctions:

> (<0 0 0>, <1 0 0>, <1 2 0>).map: {so $_.one | $_.none > 0}
(True True False)

multi sub gc($val) {
  if $val.none|$val.one > 0 {
   return 1
  } 
  sum gather for $val.grep(* > 0, :k).combinations(1..*) {
      my $new = $val.clone;
      $new[$_]>>--;
      take samewith($new);
    }
}

We can make this cleaner and more robust, but this is already a good showcase of what Raku can do.

> put (gc([1, 1]), gc([1, 1, 1]), gc([1, 1, 1, 1]));
3 13 75
> put (gc([2, 1]), gc([2, 1, 1]), gc([2, 1, 1, 1]));
5 31 233
> put (gc([2, 2]), gc([2, 2, 1]), gc([2, 2, 1, 1]));
13 101 919

Why this matters

As mentioned before, this matters for estimating the number of behaviors of a concurrent system. This will always be an upper bound: most systems have additional restrictions on how processes may interleave (such as mutexes).

If we restrict ourselves to two processes, the number of interleavings are described by the Delannoy numbers (OEIS). For more than two processes, this paper describes how to calculate “higher-dimension Delannoy paths”. Looking at it, I’m not surprised I couldn’t find a simple equation!