/ elib / concurrency

Game Turns as MicroTransactions

Taken together, E's Message Passing rules impose the familiar LIFO stack discipline within an turn. All synchronously accessible side effects brought about by the callee are done before the caller continues. In the example code above, result is not bound to a value until and unless the callee returns successfully, and the "stuff after call" will execute in the context of whatever synchronous side effects were caused by the callee.

The synchronous processing of a pending delivery, an event of our event loop, we call a turn. If the state of a vat is like the state of a game board, then in both cases, the state evolves only because of a sequence of turns, and each turn executes with mutually exclusive access to this state, and it executes to completion before before the next turn starts.

Although other Vats are executing concurrently, a caller will only see synchronous side effects caused by its callee. Because Vats are only asynchronously coupled to each other, an E turn implicitly has full mutual exclusion on all state to which it has synchronous access -- which is only state within its Vat. As a result, E execution is not observably distinguishable (except for timing and the effects of infinite loops) from an implementation in which, across the universe, only one Vat at a time takes a turn. E's turns are therefore atomic serializable micro-transactions, and E is strongly consistency preserving in the face of concurrency, without any error-prone fine-grained locking.

We say micro-transaction above because we purposely unbundle or avoid the features combined by the classic ACID transaction:

1. While a Vat is only committed to stable storage (checkpointed) between turns, because disk seeks are so expensive compared to computation, a Vat is checkpointed much less often than once per turn.

2. Unlike many systems, E doesn't claim to provide distributed atomic transactions. But seeing as how these are provably unimplementable (see the Coordinated Attack Problem), this might not be the loss it seems. Although one can build distributed mutual exclusion protocols on top of E, good E style is to avoid these like the plague. Indeed, we have so far only encountered one practical application that demanded it (ref ** The Communities.com Containership problem). Handling Partial Failures explains E's very different approach to recovering distributed consistency following network partitions or rollbacks.

3. There is no facility for aborting a turn and automatically undoing its side effects. Instead, one can manually use the try-finally expession to undo some side effects while unwinding a non-local exit.

Chronological Encapsulation

Event loops are better even than purely sequential programming at maintaining consistency

To illustrate this radical claim, consider the classic Observer pattern (or "Listener" in Java, "Dependent" in Smalltak). In the Observer pattern, an object interested in the occurrence of some condition (an observer) requests of some object in a position to know when that condition comes about (the observable), that the observable notify it when this happens. A simple example is an observable variant of the Slots used by E's scopes to hold the values of variables, and is written in E as follows:

def observableSlot {
    to makeSlot(var value, _) :near {
        var observers := []
        def self {
            to addObserver(observer) {
                observers += [observer]
            }
            to getValue() :any {value}
            to setValue(newValue) {
                for observer in observers {
                    observer <- valueChanged(newValue)
                }
                value := newValue
            }
        }
    }
}

observableSlot can be used for one-way eventual constraint programming, as it allows a perpetually evaluating expression to be informed when one of its inputs change. It's definition looks much as we'd expect in other object languages, but with differences. First, we are using a send rather than a call, even though the problem we're trying to solve doesn't mention concurrency. If we wrote it as a call, then the side effects produced by the observers would occur before the observable variable's assigner returned from the assignment. The code containing the assignment was likely written without taking the possibility of such side effects in mind, and this is as it should be.

When Alice passes a message to Bob in order to subcontract part of her plan to Bob, she is invoking Bob on her own behalf, and so would often want to wait for Bob's side effects and outcome. The immediate call does precisely this. When Alice passes a message to Bob on Bob's behalf, as when Alice is an observable and Bob is an observer, this courtesy provided to Bob should be minimally disruptive to Alice. The send above queues, on the queue of the observer's vat, a pending delivery of a valueChanged() message to this observer. This delivery will happen in its own separate turn, and cannot affect the turn from which it was sent.

We can now understand why the other peculiar thing in the above code is harmless: To illustrate our point, we put the actual assignment after the loop notifying the observers. If we were calling the observers instead, we'd need to remember to be careful to change to the new state first, before allowing any of the observers to run, lest they interact with the observable prior to this internal assignment. Even without concurrency in the picture, this worry still has the form "but what if, while I'm proceeding with plan X, someone else proceeds with a conflicting plan Y which messes me up?" Whether it comes from concurrency or not, the need for such worries just makes programming too hard. (It also makes it much harder for security reviews to check for TOCTTOU errors.)

The eventual send enables us to isolate conceptually separate plans into separate atomic turns, enabling us to avoid more cases of plan interference. We term this the principle of chronological encapsulation.