speculative message passing

One of the pain when programming in an actor framework is that messages absolutely do not arrive in order.

Take this Pony code snippet as an example:

actor Main
  new create(env: Env) =>
    let a = A(env)
    let b = B(env)
    let c = C(env)
    a.start(b, c)

actor A
  let env: Env
  new create(env': Env) =>
    env = env'
  be start(b: B, c: C) =>
    b.start(c)
    c.start(0)

actor B
  let env: Env
  new create(env': Env) =>
    env = env'
  be start(c: C) =>
    c.start(1)

actor C
  let env: Env
  new create(env': Env) =>
   env = env'
  be start(x: I32) =>
   env.out.print("hello " + x.string())

It may as well act consistent in practice, but the language has no guarantee on the order of messages arriving at c. Say welcome to Heisenbug.

What does it mean to preserve order

If we treat message passing as causality links, it looks like a tree. We do not want any two edges to cross each other.

Reserve message slots to speed up communication

In this example, the tree is visible with static analysis, so the whole tree can be built right before the message a.start(b, c) is sent. After that, the messages are passed around along predetermined paths (edges of the tree). Every actor processes its inbox based on the speculative order laid out in the tree. If a messages hasn’t arrived, wait for it.

If you run the above program, you should get the following output:

hello 1
hello 0

Why do I call this a “speed up”? Well, the message sender can send the message and forget about it. Blocking happens on the receiver, who needs the message to do further calculation. This eliminates unnecessary blocking.

This makes me think of vector clock.

Branching, and the speculative part of the algorithm.

Suppose that the message from b to c may or may not happen.

use "time"

...

actor B
  let env: Env
  new create(env': Env) =>
    env = env'
  be start(c: C) =>
    if (Time.create().seconds() % 2) == 0 then
      c.start(1)
    end

We still reserve the slot. If the message happens, it happens. If it doesn’t, we send a “cancel” message to tell c that the message will not arrive. This cancels the subtree starting from the cancelled message, in case the speculated message has any speculated dependents.

This is like [a design pattern whose name i forgot] commonly used in payment processing: you first reserve all the slots in the task pipeline, and later confirms or cancels the whole pipeline at once. In this algorithm, the cancellation is more granular.

That’s it. That’s the whole algorithm.

In case of loops, unroll all loops or cry.