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

Tyler Close tclose@oilspace.com
Wed, 14 Feb 2001 11:14:52 -0000


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

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?

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

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

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

> >Dropping order guarantees on sends
> >creates a lot of implementation flexibility. It also blurs the line
> >between what a sturdy ref is and what a "live" reference is. This
> >suggests that the two could be merged, significantly reducing the
> >application complexity of managing separate references to the same
> >target.
>
> I think I now understand what you've been trying to explain
> to me about
> Droplets.  Does the following E implement the semantics of
> a Droplets
> message send?  (Assume "srBob" is a SturdyRef to Bob.)
>
>     srBob liveRef <- foo(...)
>
> It either succeeds or it doesn't, but either way, the next
> time someone
> tries this, it also either succeeds or doesn't.  No
> fail-stop implied.
> UDP-like, rather than TCP-like.

Yes, but that's not all there is to it.

If foo() took a parameter, srAlice, then the call, in Droplets, would
be:

	srBob <- foo(srAlice)

On the receiving side, srAlice is either srAlice, or the local Alice,
if Alice is local.

in E, it would be:

	srBob liveRef <- foo(srAlice liveRef)

The E case creates a "live" reference that never gets used.

Now consider a foo() that returns a reference to an object in foo()'s
Vat. In Droplets, this would be:

	define srCarol := srBob <- foo(srAlice)

In E, it would be:

	define carol := srBob liveRef <- foo(srAlice liveRef)

In E, the Carol reference is bound to the lifetime of the connection
that was started as a result of the liveRef() call on srBob. When this
connection dies, the E Carol reference gets smashed. 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.

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.

Tyler