Examples of E-Order being useful

[Christopher Lemmer Webber]

Prior to the "Lost Resolution Bug", E-Order appears to be something
delivered "for free", falling out of the implementation naturally. We
can jump up and down and say "look at this thing we got at no extra
cost!"

Post uncovering of the "Lost Resolution Bug", E-Order seems to be
something that has uncomfortable edges which either must be programmed
around or be understood not to be exactly what we thought (eg, oh, this
is a non-eq promise now by the time it arrives...) in order to be
preserved.

Is it worth going through the effort of preserving? I'm sure there are
good reasons to justify it, but I'd like to hear more.

Again, using the example:

// alice's perspective
carol~.x()
bob~.y(carol)
carol~.z()

// bob, after getting carol
carol~.w()

The argument seems to be "Alice and Bob are more likely to do the right
thing if the Carol that Bob gets is the post-x-Carol". Yet we know that
E-Order does not guarantee anything about arrival with respect to
.z()... particularly, carol~.z() may be called before even bob~.y(carol)
is.

I can see the case where a user may be surprised, without e-order, that
Bob received a Carol that existed before .x() was actually called.
However if bob~.y(carol) being called has interesting side effects, it
may seem just as confusing that carol~.z() may be received and handled
before bob~.y(carol) is. In a sense, we could possibly say: "providing
something stronger than bidirectional FIFO order might be more confusing
to users than not doing so at all."

I'm not convinced that what I am saying is true, but I'm not convinced
it isn't. An example given in MarkM's dissertation is of a distributed
database and that bob should get a post-x carol.

But another route would be to do (sorry, I am mangling multiple syntaxes
here):

when(carol~.x()) {
bob~.y(carol);
carol~.z();
}

This is even clearer, even if more verbose, and may be easier to
visually understand the guarantees of.

If an argument exists that coroutines can confuse users about just how
much danger there is from what is/isn't being promised, could we make
the same argument about E-Order... that it provides just a little too
much, and might be mistaken for providing more than it does?

And if the answer is "yes", is it worth going to the extra effort to get
something that we no longer have for free?

There may be clear examples where E-Order has solved someone's butt in
the past. Those would be good counter-points. But a good
counter-counter-point would be then where E-Order was misunderstood to
do more than it did too.

I know others have thought much more than I have about this, so...

Advocating for devils,
- Chris

[Christopher Lemmer Webber]

One response to this could be not a reduction of errors but efficiency:
E-Order reduces time delays similar to how promise pipelining does: we
do not have to wait for the carol~.x() to settle before we send a
message to Vat B... we can start sending a message to Vat B immediately.

[Alan Karp]

There is something (well, lots of things to be honest) that I don't understand about the handoff.

I assume that messages are received in the order sent.  The carol~.x() message is sent before bob~.y(carol).  But bob~.y(carol) must involve alice's vat sending a message to carol's vat so it can set up the bob-using-carol proxy.  Bob's carol~.w() message can't be processed until that proxy is ready.  The message to set up the proxy will arrive after alice's carol~.x() message.  If that's the case, it's only a problem if the proxy is ready before the carol~.x() turn starts.  Is the problem that setting up the proxy is done concurrently with the turns in carol's vat?  Is the solution then to simply consume a turn to set up the proxy?

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

--
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 view this discussion on the web visit https://groups.google.com/d/msgid/cap-talk/87r1v6wroy.fsf%40dustycloud.org.

[Ian Denhardt]

Note that even without the lost resolution bug, e-order doesn't come
totally for free; see the discussion of embargoes in rpc.capnp. But
without the necessary protocol bits needed to preserve E-order, even
basic promise piplining & resolution does some very strange things. In
particular, if you dropped the embargos for promise resolution, you
could end up in a scenario where in the following:

bob = alice.foo()
bob.x()
bob.y()

...`y` could end up being delivered before `x`. How this happens:

First, assume the above code is being run in Vat A, and `alice` lives in
Vat B. The sequence of events is this:

- foo() returns a promise for bob.
- Vat A pipelines the call to bob.x(), sending it to Vat B.
- Vat B sends Vat A a message resolving the promise to an object that
lives inside Vat A.
- Vat A now processes the `y` call. It sees that bob has resolved to a
local object, and just calls y() on that object.
- Vat B forwards the call to x() that was sent earlier on to bob, back
in Vat A.

So Cap'n proto's solution to this is on promise resolution, send a
"disembargo" message to the original promise, and block calls to the
resolved object until that message has gotten back to the object. This
also comes up with accept/provide.

So the above is a little fiddly, certainly not "free," but I don't
really think *not* enforcing x-before-y is a reasonable option. And the
disembargo logic can readily be re-used to handle the third party
handoff too.

---

Note that in capnproto, the lost resolution bug doesn't come up because
we don't have a transmissible hash table type. I think there are a
couple things that are reasonable to drop support for to dodge the
issue:

- Don't allow allowing using capabilities (non-data) as map keys
- Don't have protocol-transmissible hash tables.

-Ian

Quoting Christopher Lemmer Webber (2020-05-26 13:11:33)

> --
> 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 view this discussion on the web visit https://groups.google.com/d/msgid/cap-talk/87pnaqwri2.fsf%40dustycloud.org.

[Christopher Lemmer Webber]

Thanks for this example, Ian... I am convinced that you are right
without even fully having digested this yet. I am convinced that when I
finish digesting it I will be even further convinced.

[Mark S. Miller]

[+Dean]

This is an important question, and we need to continue examining the alternatives here. The criteria has to do with the models programmers form under various semantics, and then the mistakes they make even according to the semantics they tried to model. Existing comparable experiences, but without easily comparable data, from weakest to strongest orders:

Unorder: The original Actors, the early Joule, Belay, and most cert systems all had no ordering guarantees at all. Just eventual delivery.

   * I am not aware of enough experience of people programming directly in original Actors to form any conclusions

   * From the early Joule experience, we concluded that unorder was a mistake, and we adopted the precursor of E-order, which we liked.

   * Belay programmers report being very happy with unorder, and never being confused by it.

   * SPKI/SDSI...capCert had no builtin ordering constraints on acting on certs. Does zcap-ld? I suspect not.

FIFO: Waterken did point-to-point FIFO. Waterken programmers would express any three-party ordering constraints by explicitly forcing a round trip, as in your example. I don't recall anyone being tripped up by this.

E-Order: E of course adopts E-Order. I find it very pleasant. Agoric is currently proceeding with E-Order, but see...

Flow Order: Midori started with E-Order and found they were using it incorrectly. Midori programmers would assume E-Order made things more predictable than it does. In reaction Dean (cc'ed) invented Flow Order, which does provide stronger ordering than E-Order. However, AFAICT, it does so at the price of making loss of progress vulnerabilities much harder to think about. Neither E nor Midori were ever subjected to actual adversaries that would have been interested in denying progress. But I think I know how to think about defensive progress in E-Order. I never got that far with Flow Order and I am skeptical.

Causal Order:

Agreed Order:

In the conventional distributed systems literature, the sequence of recognized orders is Unorder, FIFO, Causal, Agreed. I invented E-Order because I felt FIFO was too weak for secure programming, and that Causal was too strong to be implemented by cryptographic means between mutually suspicious machines. However, I arrived at this conclusion before blockchains. A blockchain is all about implementing agreed order between mutually suspicious machines within that chain. Agreed would still be too much for an interchain protocol like CapTP on IBC. But do blockchains change the base assumptions enough that CapTP on IBC should examine Causal Order? Perhaps.

The tension between E-Order and Flow Order does make me feel ever more tempted by the Waterken position. The issue is not stronger vs weaker, the issue is misalignment between what programmers tacitly expect from a given semantics vs what that semantics actually provides. If E-Order and Flow Order are both too confusing and Causal still too hard to implement securely, FIFO may indeed be the sweet spot.

Were we to adopt FIFO, there would be no need for general wormholing. We'd still need to wormhole the provideFor messages to avoid lost resolution. But if that's all we're wormholing we may well do it alone as a special case.

On Tue, May 26, 2020 at 10:07 AM Christopher Lemmer Webber <cwe...@dustycloud.org> wrote:

--
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 view this discussion on the web visit https://groups.google.com/d/msgid/cap-talk/87r1v6wroy.fsf%40dustycloud.org.

[Christopher Lemmer Webber]

Mark S. Miller writes:

> [+Dean]
>
> This is an important question, and we need to continue examining the
> alternatives here. The criteria has to do with the models programmers form
> under various semantics, and then the mistakes they make even according to
> the semantics they tried to model. Existing comparable experiences, but
> without easily comparable data, from weakest to strongest orders:
>

> *Unorder:* The original Actors, the early Joule, Belay, and most cert

> systems all had no ordering guarantees at all. Just eventual delivery.
> * I am not aware of enough experience of people programming directly in
> original Actors to form any conclusions
> * From the early Joule experience, we concluded that unorder was a
> mistake, and we adopted the precursor of E-order, which we liked.
> * Belay programmers report being very happy with unorder, and never
> being confused by it.
> * SPKI/SDSI...capCert had no builtin ordering constraints on acting on
> certs. Does zcap-ld? I suspect not.

zcap-ld does not specify ordering constraints, but also does not specify
delivery mechanism, just processing and validation of invocations. In
general zcap-ld has been written from the per-invocation perspective.
FIFO could be layered on top, but isn't in any explicit way right now,
afaict.

> *FIFO: *Waterken did point-to-point FIFO. Waterken programmers would

> express any three-party ordering constraints by explicitly forcing a round
> trip, as in your example. I don't recall anyone being tripped up by this.

Good to know.

> *E-Order: *E of course adopts E-Order. I find it very pleasant. Agoric is

> currently proceeding with E-Order, but see...
>

> *Flow Order: *Midori started with E-Order and found they were using it

> incorrectly. Midori programmers would assume E-Order made things more
> predictable than it does. In reaction Dean (cc'ed) invented Flow Order,
> which does provide stronger ordering than E-Order. However, AFAICT, it does
> so at the price of making loss of progress vulnerabilities much harder to
> think about. Neither E nor Midori were ever subjected to actual adversaries
> that would have been interested in denying progress. But I think I know how
> to think about defensive progress in E-Order. I never got that far with
> Flow Order and I am skeptical.

Interesting (I had not heard of Flow Order before).

My gut feeling is that any ordering system that I can't play a
simulation of in my head or follow drawn out on paper (similar to the
"animations" on the e-order pages) is probably one that has some nasty
hidden corner cases that will probably bite the average, and even
not-so-average, developer.

> *Causal Order:*
> *Agreed Order:*

> In the conventional distributed systems literature, the sequence of
> recognized orders is Unorder, FIFO, Causal, Agreed. I invented E-Order
> because I felt FIFO was too weak for secure programming, and that Causal
> was too strong to be implemented by cryptographic means between mutually
> suspicious machines. However, I arrived at this conclusion before
> blockchains. A blockchain is all about implementing agreed order between
> mutually suspicious machines within that chain. Agreed would still be too
> much for an interchain protocol like CapTP on IBC. But do blockchains
> change the base assumptions enough that CapTP on IBC should examine Causal
> Order? Perhaps.

Blockchains are able to approach ordering by providing "decentralized
centralization" at enormous cost... but still per-ledger. Decentralized
centralization of decentralized centralizaiton across ledgers formed
like this, if possible, will probably work in after-commit safe
resolution of what the order is... but a-priori analysis probably will
be tantamount to speculative quakery.

If it were just one "machine", maybe. I don't think it's going to work
as a network of machines.

> The tension between E-Order and Flow Order does make me feel ever more
> tempted by the Waterken position. The issue is not stronger vs weaker, the
> issue is misalignment between what programmers tacitly expect from a given
> semantics vs what that semantics actually provides. If E-Order and Flow
> Order are both too confusing and Causal still too hard to implement
> securely, FIFO may indeed be the sweet spot.

This is exactly what I was trying to needle at, so I'm happy to hear
you say it. ;)

> Were we to adopt FIFO, there would be no need for general wormholing. We'd
> still need to wormhole the provideFor messages to avoid lost resolution.
> But if that's all we're wormholing we may well do it alone as a special
> case.

Honestly that seems like the right thing to me. However, Ian's comments
about promise pipelining getting goofy without e-order make me unsure.
But I haven't been able to fully digest Ian's example yet... will
probably do so while tossing and turning right before I fall asleep
tonight.

Thrilled that my advocacy-for-devils was not completely off-base!
- Chris

[Christopher Lemmer Webber]

Hi Alan,

I'm uncertain about your confusion so maybe I am not explaining what you
need to hear, but let me try to re-explain, with new understanding after
my referenced conversation with Baldur.

Alan Karp writes:

> There is something (well, lots of things to be honest) that I don't
> understand about the handoff.
>
> I assume that messages are received in the order sent. The carol~.x()
> message is sent before bob~.y(carol).

Possibly; surprisingly it doesn't matter. There could be a delay
getting through from Vat A to Vat C for this to work. Explained below.

> But bob~.y(carol) must involve alice's vat sending a message to
> carol's vat so it can set up the bob-using-carol proxy. Bob's
> carol~.w() message can't be processed until that proxy is ready.

You have it half right.

Under the wormhole model (via wormholeop or let's say wormholecert):
What Vat A gives to Vat B is effectively the same message to call
carol~.x() that is necessary to process *before* bob.~y(carol) gives Bob
access to Carol.

So:
- Vat B: Hey Vat C, has Vat A given you this message to call carol~.x()
yet? I'm not allowed to process my next message that involves Carol
until it's done.
- Then one of two things can happen with Vat B talking to Vat C:
- If Vat A has already talked to Vat C and so Vat C has already
processed (or queued) the carol~.x(), Vat A can just say "yes,
I already got this, so it's fine... you can proceed with using
that Carol reference."
- If Vat A *has not* already handed that message to Vat C, well...
Vat B just provided it, so now Vat A can process/queue that
message, and say "Thanks... I hadn't gotten it yet, but thank
you for informing me... I've queued it now so you can go ahead."
- Now the bob~.y(carol) turn can happen (which can include bob calling
carol~.w() using this reference). Horray!

So even if Vat A *never* manages to get in contact with Vat C, or maybe
takes a very long time doing so, Vat B can proceed... because the
messages that were required before Vat B could proceed have been passed
along, store-and-forward style!

Pretty cool, but also... pretty weird.

Alan, does that explain things for you?

[Ian Denhardt]

Quoting Christopher Lemmer Webber (2020-05-26 15:17:57)

> > Were we to adopt FIFO, there would be no need for general wormholing. We'd
> > still need to wormhole the provideFor messages to avoid lost resolution.
> > But if that's all we're wormholing we may well do it alone as a special
> > case.
>
> Honestly that seems like the right thing to me. However, Ian's comments
> about promise pipelining getting goofy without e-order make me unsure.
> But I haven't been able to fully digest Ian's example yet... will
> probably do so while tossing and turning right before I fall asleep
> tonight.

The goofiness in my example is due to the example is actually failing
FIFO, but my point was that in the presence of promise resolution, you
have to *do* something to make that not happen (it doesn't "just work"
as an artifact of the already-FIFO transport), and the solution adopted
by capnproto gives you e-order as well (sans lost resolution bug). It's
not clear to me that there's much simplification to be had by dropping
the difference between FIFO and e-order.

That said, it's likely that bits of the problem are not sticking to my
brain properly, as (per my earlier comment) the hash table issue doesn't
come up in capnproto, since we don't have them.

-Ian

[Christopher Lemmer Webber]

Christopher Lemmer Webber writes:

> Christopher Lemmer Webber writes:
>
>> Again, using the example:
>>
>> // alice's perspective
>> carol~.x()
>> bob~.y(carol)
>> carol~.z()
>>
>> // bob, after getting carol
>> carol~.w()
>>

[...]

>> But another route would be to do (sorry, I am mangling multiple syntaxes
>> here):
>>
>> when(carol~.x()) {
>> bob~.y(carol);
>> carol~.z();
>> }

First of all, this should have been:

when(carol~.x()) {
bob~.y(carol);
}
carol~.z();

The reason I bring this up will be important in a moment.

> One response to this could be not a reduction of errors but efficiency:
> E-Order reduces time delays similar to how promise pipelining does: we
> do not have to wait for the carol~.x() to settle before we send a
> message to Vat B... we can start sending a message to Vat B immediately.

Note that if we are looking at this as an optimization to avoid round
trips, it may be possible to do so using something resembling promise
pipelining. The round trip back to A within the "when" can be
completely eliminated by a smart compiler and with a little bit of
extension of the promise pipelining protocol:

- A to C: deliverOp(carol, 'x', [], <carol-x-question-pos>)
- A to C: I'd like to give a gift for B of <carol-x-question-pos>
at <a-to-b-on-c-gift>
- A to B: callWithPromiseResolutionOp(bob, 'y', [<when-settled: a-to-b-on-c-gift>])

What is happening at that A to B is critically a new kind of message
that says "here's something I'd like you to do... subscribe to this
promise (or these promises), and when fulfilled, use the result to call
this other thing".

In a sense, this gives what was desired from e-order, but is explicit
and does not require more than FIFO... but it still avoids the round
trip back to A. Instead, we introduce a new CapTP operation and a
compiler optimization that notices how to use it to avoid a round trip,
similar to such "optimizations" in promise pipelining.

After all, new york and london speed of light blah blah blah...

What do you think?
- Chris

[Alan Karp]

Christopher Lemmer Webber <cwe...@dustycloud.org> wrote:

> I assume that messages are received in the order sent.  The carol~.x()
> message is sent before bob~.y(carol).

Possibly; surprisingly it doesn't matter.  There could be a delay
getting through from Vat A to Vat C for this to work.  Explained below.

Delay doesn't affect pairwise ordering.  Are you saying something else? 

 

So even if Vat A *never* manages to get in contact with Vat C, or maybe
takes a very long time doing so, Vat B can proceed... because the
messages that were required before Vat B could proceed have been passed
along, store-and-forward style!

Pretty cool, but also... pretty weird.

Alan, does that explain things for you?

Yes.  Now my question is about the tradeoff of vat C waiting for an explicit handoff message from vat A instead.  The invocation by bob might be delayed, but the protocol is simpler with fewer corner cases.  Another point is that bob can't invoke carol if alice's carol~.x() is delayed.  Can Bob even tell the difference?

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