AL Design Doc: A Proposal for Concurrent AL

[l4e21]

The purpose of this post is to convey current design thoughts about concurrent AL. Our concurrent AL needs to be able to express the following well and idiomatically, complex and useful distributed and concurrent algorithms such as:

• Heterogeneous Broadcast
• Heterogeneous Paxos
• Event Broker (Anoma/Anoma)

Since AL uses complex ideas like backtracking, we need to ensure that distribution and concurrency (historically grand problems for PROLOG) can be well-expressed in AL.

Processes

One natural way I have considered that processes could work in AL is that instead of having AL evaluation processes that run on user trigger is have them run whenever an event comes in. In the current Elixir prototype this means that a supervisor ought to exist to handle the OTP processes. I don’t think an extra Mnesia table needs to exist, since the processes would inherit from a certain class and the supervisor would simply check for this. Important to note that any process send would involve a cut, since backtracking would not really make sense for this.

Let’s say I have a watcher w1 that watches for an object of type counter being incremented. And now the user performs an AL program that updates the counter. This may look something like

send(c1, :inc)

As an effect of running :inc, the program would create a committed transaction containing some event like

set_slot(c1, :counter, n)

The AL process supervisor would send this event out to each of the processes it is responsible for. If the event matches (via unification) the shape of the event that the process waits for, the process triggers and runs its AL program. (1) This program is just a method taking in information from the event that runs AL and then, finally, performs some side effects. For example. Our process would likely want to check that c1 is a counter object, or maybe have a check on n to see whether it’s exceeded a certain amount. Then finally, its side effects go back into the event log and are able to trigger other processes.

In the case that a process’ list of goals fails, we would probably like to report this via the event log.

This way of running AL is, I think, a good trade-off between the pure monotonicity of BLOOM, and the supervisor model of Erlang. We still have monotonicity over the command log, but the object system is mutable. This should allow us to query historical state. Things can be fully monotone where desired. In fact we might be able to annotate certain processes as not requiring transactional guarantees if they are guaranteed to be monotonic, but this can be a future optimisation. On the other hand, non-monotone processes that involve updates should serialize through our ACID guarantees. Processes don’t have their own state as in the BEAM, but only know of the global command log. A process can therefore check the history of another process.

Multi-Node Participants

One lovely feature of the event broker, and essential element of consensus, is the ability to model participants on different VMs idiomatically (2). Ideally, we use an RPC style where possible as has been done in the past in Anoma. ‘Sends’ between nodes must therefore involve writing events to another person’s event log. Now there are a few questions that fall out. How do we abstract peer nodes? And how do we send and receive messages without blocking?

If we are preferring to stick to the event log style, then we should have some process that abstracts over sockets that is responsible for writing ‘received message’ events to our log. One thing that might be nice is to utilise the sorts of notation that Jamie and Isaac use for their epistemology of time in HBB- that is, events are associated with a ‘place’, instead of having a receive message wrapper. External sends ought to be understood as events that are picked up by the socket process, meaning steps ought to be short and reactive, with waits occuring between transactions. Here we see that the transaction model forces us into the correct approach regarding avoiding blocking.

We can store information about which peer we are accepting as slots on the socket process, and reject any message that doesn’t match.

Crashing

Since a process is an AL object, and since the state of an AL object can be reconstructed from the event log, this means that if an OTP process crashes, the process ought to be re-constructable from the log.

Process Creation

Given that a process is an AL object, creating a new process involves just creating a new AL object of that class. So naturally, the supervisor ought to be able to discover and set up processes.

Notes

(1) An alternative to this is that the supervisor performs this filter, which may be more work upfront but reduces the work of each process. This may be a better option. There are actually a few different options and in this way it is similar to the indexing problem.

(2) And to boot, represent different event logs on the same VM, which multihoming in local domain should make nice. As Ray has pointed out before, where possible we should want to make any one-to-one relation in our system a many-to-many relation.

[l4e21]

Want to add a couple notes that I hadn’t thought of when writing this post:

• The term ‘watcher’ just denotes and is defined as a guarded AL process. This plan was partially inspired by the literature on ‘Guarded Horn Clauses’ (GHCs) in concurrent prolog.

• This proposal is intentionally and-parallel and lacks any kind of or-parallel model. Whereas GHCs traditionally use committed-choice semantics, we do not have this. This makes the model simpler since there is no need to coordinate processes. Some kinds of parallel search are therefore require an extra step like spitting out certain events for another watcher to ‘decide’ on, which I think actually suits AL very well and prevents people from creating unnecessarily complex architectures.

• I would hope to bootstrap the supervisor and allow the user to metaprogram processes and their supervisors on this level.

[isheff]

There’s a lot I don’t understand here. I don’t know what the :inc notation means, or what a supervisor is, or what precisely you mean by “object,” “class,” or “process,” but I think I understand some of what is proposed. As discussed previously, it is crucial for concurrency that the “event log” is not some totally ordered thing such that only one process at a time can add events to it.

In fact we might be able to annotate certain processes as not requiring transactional guarantees if they are guaranteed to be monotonic, but this can be a future optimisation. On the other hand, non-monotone processes that involve updates should serialize through our ACID guarantees.

This seems like generally a good idea, although I’m not sure whose ACID guarantees you’re referring to: if we’re talking about purely “single domain” computation, this makes sense, but for distributed stuff, this gets more complicated.

we should have some process that abstracts over sockets that is responsible for writing ‘received message’ events to our log.

Once again I am wary of a single-process bottleneck. In general, when I hear “process,” I think of something that does stuff sequentially, but message receives should not be ordered unless some protocol actually requires it.

External sends ought to be understood as events that are picked up by the socket process, meaning steps ought to be short and reactive, with waits occuring between transactions.

I’m really not sure what you mean by “transaction” here. In the traditional “atomic” sense, anything that can reasonably be called a “wait” cannot be in a transaction, so it would have to be between them…

What I understand of this design makes sense to me, with caveats mentioned above.