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

Tyler Close tclose@oilspace.com
Wed, 28 Feb 2001 10:53:37 -0000


Markm wrote:
> >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?

You used this justification for creating the concept of reference
forking, and I agreed with it. The whole point of the reference
forking, I thought, was to preserve Alice's view of what the reference
can do. The is certainly what is communicated by the second paragraph
at:

http://www.erights.org/elib/concurrency/partial-order.html

In trying to preserve Alice's view of the reference's meaning, I think
reference forking oversteps its mandate. I think a reference fork
should be an explicit operation. So code that required a forked
reference would be written as:

     define alice {
         to doSomething() {
             myCarol <- X
             myBob <- Y(myCarol <- yourself())
         }
     }

The above code makes the authority transfer very clear. (Assuming we
keep Joule-style ordering of messages, as Dean and MarcS have
convinced me we should.)

I am putting so much effort into this discussion because I am annoyed
by the cost of implementing a reference fork every time a reference is
passed inter-Vat. If Alice passes a collection of 20 references to Bob
in another Vat, Alice's Vat has to do 20 message sends to fork the 20
references. In all likelyhood, the program's security did not require
this effort. In the cases where the program's security does rely on
the reference fork, it would seem much safer to explicitly code the
fork.

> 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.

Agreed. I am not suggesting that they be different. I am picking on
the same Vat case because I think it is the "loose thread" in your
reference forking story. I am hoping that by tugging on it, I can
unravel the whole approach. My real goal is to not have to do the
automatic reference fork in any of the cases. There are also
non-performance reasons for this goal, but I probably shouldn't get
into them right now. I guess I'll just say that one of my goals with
Droplets is to be able to treat any Web site as if it were a Vat. Most
web sites don't support reference forking.

> 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.

I think I understand the semantics you describe at the given URL. I am
just not sure that these semantics are reflected in the program code,
or that they need to be as strong as they are.

> >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.

It is not possible for Bob to ever have a NEAR reference to Carol,
because they are not in the same Vat. As you pointed out, this is one
of the issues where it is not feasible to hide the existence of Vats.
I don't think the reference passing mechanism I suggested creates
additional dependencies. It just recognizes the existing dependency.

> 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?

Yes. Re-reading the erights.org URL also makes this point clear. My
"loose thread" isn't as loose as I was hoping. My only remaining
thread to pull on is that this fork operation doesn't seem very clear
in the program text. That the fork can also be explicitly coded as a
method invocation surely exhibits this.

> >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.

5) All arguments in an eventual send message are copies of their
   local representations. Copying a PassByRelay reference creates
   a new PassByRelay reference that marks the beginning of a new
   timeline for messages directed at the indicated target object.
   This new timeline is in no way connected to the timeline of the
   copied reference.

This is basically Joule message ordering.

Tyler