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

[Mark S. Miller]

The context is the semantics documented at 
http://www.erights.org/elib/concurrency/partial-order.html , and in 
particular to the guarantee (in the three party case) that Alice is giving 
to Bob access only to post-X Carol.  I recommend looking at the diagrams on 
this page while reading the following.


At 03:14 AM Wednesday 2/14/01, Tyler Close wrote:
>Markm wrote:
>> Above, you ask the correct hard question: how do NEAR
>> references, which
>> allow synchronous invocation, screw this up?  It turns out,
>> in only the way
>> documented on that page:
>>
>> [after Alice eventually sends a message to Carol]
>> >If Alice and Carol are in the same Vat and Alice has a
>> NEAR reference to
>> >Carol, Alice can still immediately call Carol, perhaps
>> delivering a message
>> >before messages which were eventually sent earlier.
>>
>> Although this is ugly, it doesn't violate the above guarantee.
>
>Sure it does. The reference, from the point of view of Alice, had the
>ability to send immediate invocations. If Alice sends this reference
>to Bob in the same Vat, then Alice expects that Bob receives an
>equally powerful reference immediately upon receipt of the message.
>Alice is granting Bob access to pre-X Carol (since Alice cannot
>control when Carol gets X).

To see that the guarantees I have in mind do hold, let's separate this into 
four separate scenarios.


1) The scenario of mine you quote above, in which *Alice* does a call to 
Carol after she does a send to Carol.  What she has is a NEAR reference, 
which does enable her to call Carol.  So although it's admittedly ugly, the 
out-of-order arrival is defensible.


2) Your transform of this scenario, in which Alice eventually sends (<-) 
this reference to Bob in message Y after she has eventually sent X to Carol. 
The semantics guarantee that Bob will not be able to use this reference to 
deliver W before X.  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.

The current implementation achieves this by not delivering Y to Bob until 
after X has been delivered to Carol. Therefore, the Y Bob receives can, 
without loss of correctness, contain a NEAR reference to Carol.  Btw, the 
current implementation achieves this for free simply by servicing the 
delivery queue in a FIFO manner, though the semantics do not demand this.


3) If Alice *calls* Bob with Y, then Bob receives the same reference to 
Carol that Alice provided -- a NEAR reference.  Bob can now call on this 
just as Alice could have, and so deliver a message to Carol ahead of X.  
Although Alice and Bob are now synchronously sharing a NEAR reference, and 
so don't have the guarantee regarding eventually sent messages, they do have 
a corresponding guarantee regarding immediate calls: If Alice called Carol 
with X before Alice called Bob with Y, then when Bob calls Carol with W, 
simple time sequence ensures that W is delivered to Carol after X.


4) In this variation on #3, Alice eventually sends X to Carol, but then she 
wishes to call Bob with the Y message containing only a post-X Carol 
argument.  She can still do so!

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

In response to the "yourself" message, by convention (provided by a Miranda 
method 

http://www.erights.org/javadoc/org/erights/e/elib/prim/MirandaMethods.html#yourself(java.lang.Object)

), an object simply returns itself.  This means "myCarol <- yourself" 
returns a promise for Carol, but that it will not resolve to Carol, nor will 
it deliver messages sent on this promise to Carol, until "yourself" itself 
gets delivered, which will not happen until all messages ahead of it (like 
X) get delivered.

In this scenario, we see that Bob's effective reference to Carol stays 
EVENTUAL until X is delivered to Carol, after which it turns NEAR.


>Now, if you take the exact same E program, and instead put Alice in a
>different Vat, why should you expect the authority transfer to change
>to post-X Carol?

Referring only to case #3 where it's an issue, if Carol is in a different 
Vat then Alice only had the ability to eventually send to her, not to call 
her.  For Alice to immediately call Bob, Bob must be in the same vat as 
Alice, in which case, as in #3, Alice can only share with Bob the access to 
Carol that she's got.


>> But what about the case you ask about?  Let's say that Bob
>> and Carol are in
>> the same Vat, whether or not Alice is in this Vat as well.
>
>It's the case where Alice is also in the same Vat that the authority
>flow is different.

#3 is different because, not only are all in the same Vat, but Alice is 
immediately calling Bob.  Other than that, the authority flow is all the same.

>> >The only way I can see to rescue this behaviour is to
>> attach semantics
>> >to the Vat.
>>
>> Do you agree that the above spec rescues the guarantee
>> without attaching
>> extra semantics to the Vat?
>
>Nope. The only thing saving the Alice, Bob and Carol in a Vat scenario
>is the implicit assumption that the message to Carol will be delivered
>before the message to Bob. You haven't turned this assumption into a
>guarantee.

The implementation must correctly implement the semantics.  Correct programs 
written in the language may only count the semantics and may not make 
assumptions about the implementation, since the program is supposed to be 
independent of any particular implementation.  However, the implementation 
may make assumptions about itself, since it is specific to itself.

The language semantics guarantee that an eventually sent Y forks the 
references it contains, and that a W sent on these forked references will 
not arrive before X.  The semantics indeed do not guarantee that X will be 
delivered to Carol before Y is delivered to Bob, and a correct program may 
not make such an assumption.  However, an implementation for which this 
assumption is true may correctly count on this assumption within the 
implementation.


>> When we tried to build it without
>> these ordering
>> guarantees, we had a hell of a time.
>>
>> The ordering guarantees originated in syntactic sugar used
>> in the Joule user
>> language (though I don't think they are in the on-line
>> manual).  When we
>> added these guarantees to Original-E and used them,
>> suddenly a whole mess of
>> n-party (for n >= 3) concurrency problems went away.
>
>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.


>[...] In Droplets, the
>Carol reference is just another sturdy reference that lives for as
>long as the Bob Vat is willing to let it live. This makes surviving
>temporary partitions a lot easier.
>
>In E, the advent of partition means that you have to tear down the
>entire structure of "live" references that you've built up and rebuild
>it from scratch when the partition is fixed. In Droplets, you may get
>a few smashed return values; however, you might be able to carry on as
>you were when the partition is fixed. Your pointers may still be good.
>E pointers that suffered a smashed return value are permanently
>broken.

In some sense, the whole point of the E mechanism is to "tear down the 
entire structure of 'live' references that you've built up" and make the 
programmer "rebuild it from scratch when the partition is fixed."  Rather 
than have all references be somewhat flaky all the time, and make the 
programmer have to deal with this flakiness everywhere, make all normal live 
use really reliable until it can't be, at which point everything's safely 
fail-stop.  Let the fine grained parts of computation built up with the fine 
grained structure of live remote reference become safely useless together, 
to be replaced by a new fine grained structure rebuilt from a small number 
of SturdyRefs.

This reproduces the valuable part of distributed atomic transactions -- 
abort (throwing away questionable state) and recovery (rebuilding from 
relatively stable things) -- while not taking on any impossible problems. 
The alternative of trying to pervasively maintain consistency in place seems 
too hard in one way, while the alternative of full distributed atomic 
transactions is simply impossible, because of the coordinated attack 
problem.  This middle point isn't even a compromise.  It's the sweet spot in 
the design space between these problematic poles.


>I'm reminded of a time when I was at your house and you were using a
>Web site over Ricochet. You disconnected from Ricochet and then
>reconnected using your land line. You then stopped and remarked on how
>wonderful it was that you could continue using the Web site without
>loss of session state. An E application would not be able to exhibit
>this same functionality. A Droplets application may.
>
>The Internet being what it is, I think the ability to easily handle
>temporary partitions is an important feature.

I agree that handling partitions is important.  That's the point!  I claim 
that the effort needed to correctly maintain consistency despite partitions 
is lower with the E pattern than with the Droplets pattern.  With less than 
this effort, the path of least resistance using the E pattern leads to an 
application that safely disconnects.  But using the Droplets pattern, the 
corresponding path of least resistance leads to an application that 
innocently continues in a confused state.



        Cheers,
        --MarkM