[E-Lang] New Page: Partially Ordered Message Delivery

Mark S. Miller markm@caplet.com
Tue, 27 Feb 2001 11:41:35 -0800

Note before reading on: "PassByRelay" is E's new term for "PassByProxy".  
Java 1.3 has used up the term "Proxy" for an unrelated concept.  PassByRelay 
is the default in E, as contrasted with PassByCopy or PassByConstruction.  
All the discussion so far has assumed that Alice, Bob, and Carol are 
PassByRelay, and we continue with that assumption.

At 06:39 AM Tuesday 2/27/01, Tyler Close wrote:
>Markm wrote:
>> 2) [...] Since a NEAR reference would give Bob
>> the ability to
>> deliver W immediately (via a call), the semantics require
>> that the reference
>> delivered to Bob not be NEAR until after X has been delivered.
>This is actually the case that I am thinking about. The confusion is
>about what "the semantics require". Take this adaptation of your code.
>     define alice {
>         to doSomething() {
>             myCarol <- X
>             myBob <- Y(myCarol)
>         }
>     }
>Assume Alice, Bob and Carol are all in the same Vat.

Yes, this code corresponds to this case.

>After sending Y to Bob, Alice is free to do a synchronous invocation
>with myCarol. 

Yes.  Alice's myCarol is a NEAR reference by assumption.

>I assume that as soon as Bob gets his copy of myCarol,
>Bob will also be able to do a synchronous invocation with myCarol. Bob
>should get exactly what Alice sent him. Alice could do a synchronous
>invocation, so Bob can too. The delivery of X to Carol is not an
>element of this timeline.

Why do you assume that?  Why should Bob get exactly what Alice sent him?  As 
you agreed, we seek to have a semantics as independent of Vat boundaries as 
reasonably possible.  The eventual send is the kind of send that can cross 
vat boundaries, and therefore any semantics we attach to it when Bob and 
Alice are in different vats we should at least consider attaching to it when 
Bob and Alice are in the same vat.

The semantics described at 
http://www.erights.org/elib/concurrency/partial-order.html do exactly this: 
Bob receives not the same reference to Carol held by Alice, but a fork of 
this reference, where the fork point is behind the X.  Above you say 'The 
confusion is about what "the semantics require".'.  Well clearly, the 
semantics I describe on that page require this forked reference not to 
become NEAR until there are no messages ahead of it.

Btw, in the current implementation, Bob does indeed receive exactly what 
Alice sent him, since Y isn't delivered to Bob until after X is delivered to 
Carol.  Therefore the current implementation does not have to transform 
intra-vat messages.

>I am guessing that when you say "the semantics require", you are
>saying that the semantics require that Bob gets a reference that is
>not able to do an eventual invocation that arrives before the last
>eventual invocation by Alice. You are then using this condition to
>justify the creation of a temporarily non-NEAR reference. It is this
>last step that does not seem clear to me. Alice sent a NEAR reference.
>Why does Bob (in the same Vat) get a non-NEAR reference? Just looking
>at the code, I see nothing that implies this transformation. 

Your argument depends on your qualifier "in the same Vat", and therefore 
violates your desire for a semantics mostly independent of vat boundaries.  
Were Bob in VatB, while Alice and Carol are both in VatA, you would not 
object to Bob receiving an EVENTUAL rather than a NEAR reference to Carol.  
Likewise, were you to grant order preservation on references, you would not 
insist that messages from both Alice and Bob-in-VatB be delivered according 
to the chronological full order in which they were eventually sent.  You 
would instead loosen the order, whether to E's partial order or something else.

So, E's vat-boundary independent statement of partial ordering semantics is: 
 In an immediate call (only possible on a NEAR reference), a reference 
passed in the message is identical to the reference delivered  By contrast, 
when a reference to a PassByRelay object (Carol) is passed (Y) in an 
eventual message send (possible over either a NEAR or EVENTUAL reference), 
what is delivered is a fork of that reference, where the fork-point is 
according to the partial ordering semantics described at that URL (after X). 
 So long as the reference sent is not BROKEN, ie, is NEAR or EVENTUAL, the 
delivered reference may be NEAR, EVENTUAL, or BROKEN.  However, in no case 
shall the delivered reference (the Carol argument of Y as received by Bob) 
enable the recipient (Bob) to violate the partial ordering constraints 
(cause a message to be delivered to pre-X Carol).

Now do you agree that this is a vat boundary independent statement of the partial ordering semantics?

Of course, the full semantics does include vat boundaries, but only within 
the degrees of freedom allowed by the above statement: 1) Intra-vat references 
are required to eventually become NEAR.  2) Only inter-vat references can 
spontaneously become BROKEN, and only on partition, which 3) breaks all 
inter-vat references between that pair of vats.  In other words, for the 
live references between VatA and VatB, partition is all or nothing.

As you say elsewhere, until we have persistence we should be careful about 
considering matters to be too settled.  In particular, I expect that across 
a checkpoint-revive there will be other references that revive BROKEN, 
violating the "Only" of #2 above.

>The raw
>code suggests to me that Bob gets the powers Alice gave to him, which
>included the ability to do a synchronous invocation. Bob is granted
>access to pre-X Carol.

This would be a plausible interpretation from reading only the current draft 
state of Walnut.  As I see it, there are several possible fixes to this 
naive interpretation:

1) Don't worry about it.  There's no way for a programmer to get into 
trouble by coding to this naive interpretation.  In particular, this naivete 
cannot cause a security hole.  When they want an in-depth understanding, the 
reference documentation (mostly to be written, but including the stuff at 
that URL), will make things clear.

2) Expand on this in Walnut.

3) Drop the ordering guarantees as you suggest.

4) Guarantee as well that a send NEAR reference will be received as NEAR, a 
property of the current implementation.  Although this would still not 
demand that pending intra-vat deliveries be serviced in a strict FIFO order, 
it would become less likely that there remain reasonable engineering choices 
other than strict FIFO.  This is more restrictive than I'd intended the 
semantics to be, but may still be the right engineering choice.

>> >Are these problems adequately solved by the multi-promise resolve
>> >sugar you recently introduced?
>> No.  They solve a different issue -- waiting for multiple
>> separate things to
>> be resolved before taking some action.
>Could you give me an example of the type of problem you are thinking

 From the Walnut:

More later...