Communicating Event Loops and transactional turns

[Mark Miller]

[cc'ing friam and cap-talk because e-lang has been so idle lately. But e-lang is the right place for this, so further discussion on this topic should continue on e-lang.]

In E, if code in a turn went into an infinite loop, that vat was hosed. 

Separately, within our model of persistence, if a vat crashed, then it was restarted from the last checkpointed state, which was ideally the beginning of the current turn. When it restarted, it might retry the same event. If it always retries that event, and if that event always causes a crash, then the vat would also be hosed.

Previously we've always said that an ocap vat defends only integrity at object granularity, but that a vat is the minimal unit for defending availability. If Alice is to protect her availability from Bob going into an infinite loop, then Bob must be in a separate vat, and Alice and Bob may interact only asynchronously.

We are now rebuilding the Communicating Event Loops model to run on blockchains. On blockchains, all computation is resource constrained. It must be paid for in a finite amount of some unit, now universally called "gas". Thus, infinite loops are reliably turned into transaction abort. For blockchains, the bookkeeping needed to rewind to the previous turn boundary is not optional; nor is it expensive when compared to the rest of the platform. For non-blockchains where we still do this bookkeeping, we can use a non-deterministic watchdog timer instead of gas.

Such transactional rewind gives us new degrees of freedom. 

Imagine that Alice wishes to use Bob within the same vat, invoking Bob only asynchronously with some kind of enforced budget, to protect Alice's availability. But Alice passes some of her own objects to Bob that Bob can invoke Alice's objects synchronously during such a turn. The constraint is that Bob's stack frames may only appear when the frame at the bottom of the call stack is a Bob frame, and that everything that happens during that turn draws on the limited budget Alice set up. Within such a turn, Alice and Bob can call back and fourth synchronously, since there's still a Bob frame at the bottom of that stack.

If that turn exhausts the budget Alice allocated for that turn, then the turn aborts and the vat goes back to the state right before Bob's turn started. 

Bob's turn might also send asynchronous messages, but we adopt the Waterken invariant that no messages are ever released from uncommitted turns. If the turn aborts, then it also did not send any messages. If the turn commits, then we need to think about what budget the turns caused by those messages draw on. But let's worry about that later.

Once Bob's turn itself aborts, say, from exhausting its budget, what should happen next? I propose that Bob's turn acts as if this first invocation throws an exception instead of doing anything else. IOW, rather than starting Bob's turn, the promise for the result of the turn becomes a rejected (broken) promise, reducing this case to the normal asynchronous exception handling coordination.

With all that mechanism, we could support transactional abort of a turn for other purposes. We could provide an abort(error) operation that, in general, aborts the turn, reverts to the state before the turn starts, and immediately rejects the promise for the turn's result with that error. Alice can let Bob call her objects synchronously while still protecting her availability from Bob's profligacy.

Does this seem like a good idea?

--

  Cheers,
  --MarkM

[Ben Laurie]

Adding blockchains and calling it gas doesn't really alter the fact that you're using timeouts, which is not exactly a new idea.

The argument against timeouts, AFAIK, is that it's hard to set them right. But clearly they are widely used, so I guess it's not impossible.

--
You received this message because you are subscribed to the Google Groups "cap-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cap-talk+u...@googlegroups.com.
To post to this group, send email to cap-...@googlegroups.com.
Visit this group at https://groups.google.com/group/cap-talk.
To view this discussion on the web visit https://groups.google.com/d/msgid/cap-talk/CAK5yZYiq_BnOd4WovGEccxYvpULgar9YKXNrbZA0G01XE4oTBA%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.

[Ben Laurie]

BTW, I appear not to be able to post to e-lang.

[Alan Karp]

I'm a bit confused about the conditions.  You say, "everything that happens during that turn draws on the limited budget Alice set up."  How is that enforced?  Is Bob an object that Alice passes some budget on invocation?  Is Bob an object with a budget of its own?  Does Bob have another source of budget, perhaps something left over from Carol's invocation?  

Ben Laurie's comment about timeouts is on the mark.  A timeout is a heuristic, as is the amount of budget Alice sets up.  It appears that Alice has an incentive to over provision Bob, because she loses everything she allocated to Bob if he doesn't finish the task.  Might Bob use that extra budget to do Bob's task at Alice's expense?  

The problem always is setting the right value of a heuristic.  In this example, Bob might be within epsilon of having enough budget to complete the task.  Would Alice be willing to provide it?  Could Alice provide an object Bob can invoke synchronously to get a bit more budget?  If so, that might be a better mechanism.  Say that Alice gives Bob a small amount of budget to get started.  Bob can then ask for more, perhaps proving progress toward completing Alice's task.  Alice's object could then allocate a bit more budget to Bob, and so on.  To me, this approach feels like the way Digital Silk Road bootstrapped trust.

--------------
Alan Karp

--

[Chip Morningstar]

I don't understand how this avoids the problem we've forever grappled with, which is that if this failure mode happens the objects that Alice passed to Bob (plus any other objects transitively reachable from those) are now in an indeterminate state just like the rest of Bob is, which is to say that Alice is now in an indeterminate state too.  I don't understand how to program defensively in such a case.  How is this operationally different from killing a thread in shared memory, with all of the issues that entails?

Chip

[David Nicol]

The new thing, or the potentially new/old thing, in my estimation, is accounting for the gas: Bob's code runs using Bob's gas, and if Bob tries to foist an infinite loop (or a rabbit, whatever) on the commons all he uses up is his own gas. Is that or is it not still a timeout? An out-of-gas condition should be handled similarly to a timeout, raising the appropriate exception or issuing the appropriate signal, if gas is designed in from the start it would be a first-class error type -- http://man7.org/linux/man-pages/man3/errno.3.html would get extended with EOUTOFGAS or such -- a good system might persist the out-of-gas process for a few cycles and alert Bob that it must be topped off or have its resources recycled.

On Sun, Aug 12, 2018 at 8:13 AM 'Ben Laurie' via cap-talk <cap-...@googlegroups.com> wrote:

Adding blockchains and calling it gas doesn't really alter the fact that you're using timeouts, which is not exactly a new idea.

The argument against timeouts, AFAIK, is that it's hard to set them right. But clearly they are widely used, so I guess it's not impossible.

--

"At this point, given the limited available data, certainty about only a very small number of things can be achieved." -- Plato, and others