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

Marc Stiegler marcs@skyhunter.com
Mon, 26 Feb 2001 18:52:10 -0700

This message is a very out-of-synch response to Tyler's request for my
opinion about dropping out-of-order guarantees from E. I have reproduced
Tyler's original message in total at the bottom, but there are no embedded

Tyler, if I understand your proposal correctly, I find the current ordering
guarantees for sequential delivery quite valuable, though there is no one
killer example that makes it a must-have. I will jot down a couple of
examples for you.

I have an DBMS server which I use with a web page server, all in e. I send
updates to the dbms server, then make queries. I really want the updates to
be performed before the queries start, but I also want to pipeline (i.e.,
not wait for acknowledgement on the update before issuing the query).

I have a marketplace in which the buyer's viewer is receiving a series of
updates on the state of the marketplace--a tickertape, more or less. If  the
updates arrive out of order, the buyer will be viewing states of the
marketplace that never actually existed, with unclear consequences.

I have a file transfer system that can simply assume the next block of data
can be appended to the end of the open file. It includes a beautifully
simple recovery algorithm if partition occurs in the middle of the transfer.
Everything would be far more complicated if I had to cache all the
individual blocks separately, stitch them together at the end, and compute
and discuss the "holes" in the blocks after a partition.

I could of course manually label all these transactions to keep track of
sequencing, but it keeps the code at my level clean and simple to have it
done down inside E itself.


----- Original Message -----
From: Tyler Close <tclose@oilspace.com>
To: Mark S. Miller <markm@caplet.com>
Cc: E Language Discussions <e-lang@eros-os.org>
Sent: Tuesday, February 13, 2001 9:02 AM
Subject: RE: [E-Lang] New Page: Partially Ordered Message Delivery

> Markm wrote:
> > http://www.erights.org/elib/concurrency/partial-order.html
> At this URL, you write:
> "The reference as handed to Bob gave Bob a dangerous possibility -- of
> delivering a message ahead of X -- that was beyonds Alice's notion of
> the reference's meaning. This would be dangerous."
> In E, a local reference is indistinguishable from a remote reference
> if you are only doing eventual sends, as Alice would be in this
> scenario. If Alice, Bob and Carol are all in the same Vat, then there
> is nothing preventing Bob from doing a synchronous invocation on the
> received Carol reference. If Bob receives the Carol reference before X
> gets to Carol, then Bob can do a synchronous invocation on pre-X
> Carol. Since Alice's references to Bob and Carol are, by definition,
> different references, there is no guarantee on the order in which the
> messages will arrive at their respective targets. The E language never
> guaranteed Alice that she was only giving Bob access to post-X Carol.
> The only way I can see to rescue this behaviour is to attach semantics
> to the Vat. To date, you've been very careful to restrict semantics to
> the reference graph, allowing the Vat boundaries to be ignored. I
> think this approach might be more valuable than the behaviour that
> could be rescued.
> If this behaviour is not rescued, then it begs the question of whether
> there should be any order guarantees at all on sends. Are we sure that
> we need them? Does the chaining of the return value from one
> invocation into a parameter to a later invocation provide us with
> enough control over the order of execution? I think so. I'd be
> interested to hear from MarcS. 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.
> Tyler
> _______________________________________________
> e-lang mailing list
> e-lang@mail.eros-os.org
> http://www.eros-os.org/mailman/listinfo/e-lang