Ordering Guarantees (E-Order vs. point-to-point FIFO?)

[zenhack]

Forking off of discussion from #5 (comment):

We'd mostly settled only only providing point to point FIFO ordering guarantees, because the lost resolution bug convinced people that E-Order is apparently harder than originally believed, and it was deemed not worth the trouble. But in light of the way the discussion on issue #5 is going, we may end up building a data model where the lost resolution bug at least cannot cause decoding errors.

With this issue I'd like to understand exactly what the trade-offs are, and what we're buying ourselves by relaxing the ordering requirements. I also want to see if I can align the way capnp does things; having different ordering semantics seems like a great way to have extremely subtle bugs, but right now the capnp docs say we provide E-order. But we also don't do 3PH yet (actively working on it) which is where the hard cases come in, and I'm not sure how wedded we are to that.

Reference: http://erights.org/elib/distrib/captp/WormholeOp.html

I'd like to try to understand what switching to point-to-point FIFO does to the implementation -- what does that look like vs. what E did?

If my understanding is correct, Goblins currently provides E-Order, but not the guarantee that references don't unsettle in flight, which the above link seems to suggest is critical for the "Allow services with Near arguments" criterion, so effectively we're dropping that, forcing such services to have to potentially deal with waiting for arguments to resolve, even for things that should end up being near references. I'm currently on the path to implement a similar thing in go-capnp.

Does dropping E-Order lead to a different implementation? If so, what does it look like?

[zenhack]

Also, I have some vague recollection of @tsyesika's pebble system reducing the importance of things like MintMaker? does this change the calculus at all?

[erights]

the capnp docs say we provide E-order. But we also don't do 3PH yet

Until 3PH, E-Order is the same as point-to-point FIFO. So I don't think this creates a compat problem in practice.

[zarutian]

So, I been thinking about this kind of ordering issues on and off for (too many) years in relation to various captp protocols and related ilk.

Everything from WaterKens store&forward retry forever message oriented to Es connection oriented and AmbientTalks ambient references with timeouts and leashes.

As I understand it, E-order (historical) is a way to implictly do certain kind of attenuation when delegating a reference.
The aforementioned attenuation is that Alice wants to give Bob access/reference to Carol after Alice has sent an eventual send invocation(s) to and targetting Carol.

When I was musing on how to do captp over udp (or letters or carrier pigeons) it look to me that only way to get such attenuation or ordering gurantee was to explictly encode it SSA style in each packet.

My question is, given FIFO point to point ordering gurantee, what sort of mechanism (via wellknown methods on the bootstrap objects/NonceLocator or something) would we want on top to get back E-order or even get nearer Total Order?

And do we want that?

[zenhack]

What I want to pin down is:

1. What exactly are we giving up going from E-order point-to-point FIFO?
2. How is the implementation different as a consequence of this?

My intuition for (1) is that the answer should be, with E-order, if alice sends foo() to carol and then sends carol to bob, any messages bob sends via that reference are delivered after the foo() that alice sent. Whereas with point to point FIFO, there is no requirement that bob's messages arrive after alice's, only that alice's future messages arrive after past ones, and likewise for bob's messages (separately).

However, this doesn't seem to line up with what I've read; it sounds like the gap in desired vs. actual semantics caused by the lost resolution bug is that promises may "un-resolve" in transit (but will later re-resolve to the same thing). It's not clear to me what, if anything, this has to do with the ordering guarantees per se?

[zarutian]

However, this doesn't seem to line up with what I've read; it sounds like the gap in desired vs. actual semantics caused by the lost resolution bug is that promises may "un-resolve" in transit (but will later re-resolve to the same thing). It's not clear to me what, if anything, this has to do with the ordering guarantees per se?

It is not promises that get "un-resolved" but already settled far references. It has to do with third party handoff where VatA informs VatC that VatA is giving VatB access to Carol (which VatC hosts), call that message provideFor, and VatA informs VatB that there is gift waiting for it at VatC, call that message part Promise3Desc.

If Carol far ref is a key in a Map (js term) that Alice sending to Bob then because of VatB needing to estabilish a connection to VatC and retrive the gift of Carol that far ref will either temporarly, in perspective of VatB, become a promise aka get "un-resolved".

What WormholeOp does is redundantly send the provideFor message from VatA to VatC via VatB acting like a proxy. This allows VatB to minimize the time their Carol far ref spending as an unresolved promise from their perspective.

How does this relate to message ordering constraints? To fix the lost resolution bug fully VatB must hold off delivering Alices invocation of Bob where he is given as part of a Map access to Carol until both the WormholeOp’ed provideFor message and VatBs acceptFrom message have arrived at VatC and VatB has gotten a resolved far ref to Carol as result.

Which can cause unacceptable delay as promise pipelining is not used in that case (iirc).

[zenhack]

Alright, that more or less matches my intuition. So what if instead of relaxing things to point-to-point FIFO, we just allow far references to become unsettled while in transit (but require them to eventually re-settle to their original target)? I.e. take the behavior of the lost resolution bug and just say that's not a bug, it's behaving as specified? If we're dropping maps from the core data types, the decode errors go away, so this seems not so bad.

[erights]

Which can cause unacceptable delay

The issue is not whether the delay is reasonable. The issue is a denial of progress attack. Can VatA cause the VatB->VatC stream of messages to be infinitely delayed because VatA does not properly do its part is resolving the indirect reference.

That's why the wormholeOp has VatA send to VatB the alleged traffic from VatA to VatB. Whether VatA lies or not, once VatB knows it is sent, it can then treat Carol as remotable (a resolved far reference) and proceed. If VatA sends VatB something weird as the alleged traffic, VatA only fouls its own nest.

[erights]

Also

We know for sure that pipelining is a huge benefit for two-party interaction. I have no reason to expect that the speed of three party handoff actually matters that much. Pipelining here is a nice-to-have. But unless three party handoff has a surprising need to be speedy, I would sacrifice an extra round trip to two if needed for correctness, where correctness includes lack of vulnerability to lost-progress attacks.

[zarutian]

I am all for dropping maps and sets from core data model of captp.
But I am musing if well known constructor methods for maps and sets should then be on the bootstrap-object or what E calls NonceLocator
Zarutian_iPad 21:19:03
perhaps with helpers of async_ops also available for the thorny situations that require them.

One such example use id jsE(E(NonceLocatorAtOtherEnd).getAsyncOps()).someArgsAwaitForMethod(NonceLocatorAtOtherEnd, “constructMap”, [<even number of things>], [<bool array of those that need to be awaited on>]); to construct a map with its keys already settled.

But in that example what ever that is supposed to get the map gets a promise for it instead the map itself.

[erights]

With the title "Ordering Guarantees", this thread has come to contain both discussions of comparison orders among data types, and message delivery orders over networks.

[dckc]

Yeah... oops... I think mixing value ordering in here was a mistake.

[zenhack]

Changed the title to clarify.