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

Tyler Close tclose@oilspace.com
Tue, 13 Feb 2001 16:02:41 -0000


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