[e-lang] Surprising message orders

[David Hopwood]

zuzu wrote:
> a/t/m i am racking my brain to elegantly transform objects into actors
> with closures to fit carl hewitt's description of using continuations
> (so that actors can automatically coordinate context themselves
> without relying on returning hard values until the very end).

I've been working on that as well, but to give a complete transformation
I need some clarification of the intended constraints on message ordering
in E:

E requires that message sends are partially ordered in the sense described
at <http://www.erights.org/elib/concurrency/partial-order.html>. Pure actors
does not require this: the event ordering laws allow messages between two
actors to cross each other. Actors is very good at expressing requirements
of other models non-primitively, though, and that's what I'm trying to do.
However, there are several possible interpretations of the partial ordering
requirement.

Define a "surprising message order" as a message order that *would* violate
causality if all messages were transmitted instantly.

For example, suppose that Alice starts holding references b to Bob, and
c to Carol. Then the following events occur in order:

1. Alice sends b <- foo(c, Alice).
2. Bob receives foo(c', a).
3. Bob sends c' <- hello("from Bob").
4. Bob sends a <- bar().
5. Alice receives bar().
6. Alice sends c <- hello("from Alice").

In addition, Carol must at some point receive hello("from Bob") and
hello("from Alice"). However, it is possible that she receives
hello("from Alice") *before* hello("from Bob"), because even though
Alice is guaranteed to send her message after Bob, the messages may
cross each other. This would be a surprising message order.

The partial ordering requirement does not rule out surprising message
orders. In the example, Bob's reference c' to Carol is updated to point
to the Alice that has received hello("from Bob"), but Alice's reference
c is not so updated.

IMHO this is fine for the general case where Alice, Bob and Carol may
be in three different vats. In that case, it is an unavoidable fact that
messages between vats are potentially subject to arbitrary delays, and
it is not in the spirit of either actors or E to enforce stronger
constraints on message ordering to prevent messages from crossing,
given that this would be at the cost of increased latency.

However, suppose that Alice and Bob are in the same vat (Carol may be
in a different vat). In that case, we might suppose that it would be
possible to queue Alice and Bob's messages in such a way that they
were guaranteed to arrive at Carol in the same order they were sent.
Semantically, the effect would be that once any actor in a given vat
had sent a message M to X, all other X-references *in that vat* would
be updated to point to "the X that received M".

This is desirable because it allows reasoning about the vat as if it
were a single actor. It also appears to be efficiently implementable.
My question is whether E's semantics requires, or should require, this
stronger version of partial ordering.

-- 
David Hopwood <david.nospam.hopwood at blueyonder.co.uk>