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

[Tyler Close]

Markm wrote:
> At 02:53 AM Wednesday 2/28/01, Tyler Close wrote:
> >[...] 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.
>
> Actually, I would appreciate it if you would get into it.
> Even on so little
> information, I already like the smell of this argument.

The way I see it, one of the greatest powers of the capability model
is that it does not make any assumptions about the security features
of external nodes (Vats). We often overlook this advantage because we
have recognized that it is the only realistic assumption to make. We
shouldn't underestimate the power of this approach. We can get a lot
of leverage out of it.

The Web, as it is today, works by sending method invocations (GETs and
POSTs) over references (URLs). Seen in this way, my e-gold account has
an API. There's no reason why my e-gold account can't be made to look
like an object in a remote Vat. (In fact, using Droplets, it currently
does.) This is a huge win. If you are careful about defining your
reference semantics, you can pretend that capabilities are already
widely deployed.

If Microsoft, and others, are successful at deploying .NET and SOAP,
then within a few years, the Web will be populated with a wide array
of interesting services that are accessible using a mechanism that,
from the client's perspective, can be seen as a capabilities.

If, like Droplets, E can be made to play nicely with web services,
then E becomes a powerful language for scripting together various web
services, and also for implementing web services. The adoption plan
that this approach offers is compelling.

> At 02:53 AM Wednesday 2/28/01, Tyler Close wrote:
> >(Assuming we
> >keep Joule-style ordering of messages, as Dean and MarcS have
> >convinced me we should.)
>
> >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.
>
> Before this message, I had no idea you agreed that
> successive messages on
> the same reference should be delivered in the order they
> are sent (the two
> party full-order case).  With this agreement, our positions are now
> substantially closer.
>
> Since you now agree with two party full-order, could you
> restate your
> proposed non-fail-stop semantics of message delivery in
> this context?  I
> think the two issues are crucially tied together.

For my current Droplets reference semantics, there are three client
discernable results to an eventual send. The return value promise may
be:

1) Resolved. The message got to the target and succesfully executed.
The return value promise has been resolved to the return value.
2) Deferred. The results of the message send are currently unknown.
3) Smashed. The message was received and execution produced an
exception, or the message was never delivered, or the target is no
longer accepting messages.

To make this full-order, I think I just have to modify condition 3 to:

3) Smashed. The message was received and execution produced an
exception, or the target is no longer accepting messages.

And then guarantee that messages are sent, and processed, in FIFO
order.

At the implementation level, this means that when the sending Vat
discovers that the partition has been repaired, it repeats the
messages that it was waiting for a response to. If the receiving Vat
finds that the target reference is still valid, it uses the archash in
the message to determine whether or not the message has already been
processed. If the message has already been processed, then the archash
is already resolved to the return value. If the message has not been
processed, the Vat processes it as usual. If the target reference is
no longer valid, then the smashed message is returned.

(Note: I've decided to steal your E archash idea for Droplets. It will
be documented as such in the Javadoc. Yet another for the collection
of E stuff in Droplets. Thank you.)

This makes supporting normal web sites less friendly. We can't assume
archash processing, so we can't repeat the message. This means
smashing the reference immediately, whereas before I only had to smash
the return value promise. This client code will now have the
additional responsibility of getting a new reference.

Thinking about this, it basically amounts to just making E's "live"
references less fragile. All references become "sturdy" references
that need to be garbage collected. In Droplets, I've opted for not
doing distributed garbage collection, but for imposing on the
programmer the responsibility of exporting references from a specific
context. The programmer then has to kill off the context to "garbage
collect" the exported references. This certainly has limitations, but
I am not expecting clients to be capable of participating in a
distributed garbage collection algorithm. I am expecting clients to be
web browsers, Perl scripts, Python scripts, etc. (Note, there are
implicit ways of exporting references as well, but lets not mix the
discussions for now.) I think it would be a good idea for E to support
this model, and also provide a special context that cannot be
invalidated, but does do distributed garbage collection.

I started down this path for several reasons.

1) E's connection based references can disappear on you at any time,
leaving you with the task of recovering. Writing this recovery logic
is too burdensome. I need an automated recovery.
2) Often, the recovery strategy was "Just send the message again".
Client code is not in a good position to know when to resend the
message. Really, you want the Vat to do this work, since it is in a
good position to notice that the remote Vat is online again and that
the lost messages can be retried.
3) Writing server objects that allow clients to recover is really
tricky in E. You have to anticipate all the modes of use. Automated
recovery helps when writing the server object, as well as the client
object.

Tyler