[e-lang] E-order can be optimized out of CapTP for DeepFrozen objects

[Kevin Reid]

(Please keep discussion mainly on e-lang list for consistency.)

A novel observation that was made at last Friam while reviewing Cap'n Proto. In E terms:


If an object is known to be DeepFrozen, and therefore stateless, then it is not necessary to delay third-party messages to that object in the fashion required by E-order, as that requirement is to prevent mis-orderings of stateful operations.


I don't currently recall enough of the CapTP design to say how hard this alternate behavior would be to implement. It would also require holders of far references to have a remote-is-DeepFrozen flag, which is not especially difficult but does not fit neatly into the target-object-agnostic existing protocol.

[Mark S. Miller]

On Wed, Oct 2, 2013 at 3:26 PM, Daira Hopwood <

Post by Kevin Reid

Post by Kevin Reid
A novel observation that was made at last Friam while reviewing Cap'n

Proto. In E

Post by Kevin Reid
If an object is known to be DeepFrozen, and therefore stateless, then it

is not

Post by Kevin Reid
necessary to delay third-party messages to that object in the fashion

required by

Post by Kevin Reid
E-order, as that requirement is to prevent mis-orderings of stateful

operations.
This appears to be almost unobservable in the case where all the arguments
to the message
are also DeepFrozen. Only 'almost', because the target machine receives
information
before it could have done so in E-order, and nothing prevents the target
machine's
E (or similar language) implementation from retaining that information
despite its *claim*
that the object is DeepFrozen.

CapTP does not enforce that the target machine (as opposed to the target
object) not receive the message ahead of E-Order. In the <
http://erights.org/elib/distrib/captp/provideFor.html> scenario I use to
explain how CapTP implements E-Order, I illustrate exactly such a case of
early delivery, which has a pipelining advantage rarely seen in 3-machine
introduction protocols.

Post by Kevin Reid
When some arguments are not DeepFrozen, this is an observable
specification change
even when all machines respect their claims about DeepFrozenness: it's
possible for
messages to sent to other stateful objects in an order that would not be
possible
according to E-order.

Perhaps an example?

Post by Kevin Reid
I can't immediately think how this could cause harm contrary to the design
intent
of E-ordering, but I haven't thought very hard about it. In any case I
think this
ordering should be given a different name, since it's clearly
distinguishable.
It would be really nice to have a formal specification of E-order. I know
only of
informal descriptions.

If anyone here would like to take the lead on writing a paper formalizing
E-Order, I'd be happy to participate and co-author.

Post by Kevin Reid
--
Daira Hopwood ⚥

[Kevin Reid]

Post by Mark S. Miller

When some arguments are not DeepFrozen, this is an observable specification change even when all machines respect their claims about DeepFrozenness: it's possible for messages to sent to other stateful objects in an order that would not be possible according to E-order.

Perhaps an example?

I'm too tired right now to write code, but I can describe an example informally.
Suppose two messages X <- foo(Y, 0) and X <- foo(Y, 1) are sent in that order, where X and Y are in the same vat, X is DeepFrozen, and Y is not DeepFrozen. Also suppose that X.foo(obj, i) sends obj <- bar(i).
Then in strict E-order, X <- foo(Y, 0) and X <- foo(Y, 1) must be received in that order, and Y <- bar(0) and Y <- bar(1) must also be received in that order. But under the relaxed E-order, if I understand correctly, X <- foo(Y, 1) may be received before X <- foo(Y, 0), and so Y <- bar(1) may be received before Y <- bar(0).

[Reiterating: Please send further messages To: e-lang, not whichever list you happen to be looking at. This will help ensure the discussion does not get fragmented in case of the absence of reply-all.]


Thank you for pointing this out. This sort of compositionality property is something we I want to have been thought carefully about.

Even if we somehow treated "X <- foo(Y, 0)" like a message send to Y, that would not be sufficient due to the possible ordering of events:
sender: X <- foo(Y, 0)
sender: X <- foo(Y, 1)
X: Y <- bar(1) (this is delayed...)
X: Y <- bar(0) (but this is still put on Y's queue *after*)

There is no obvious narrow patch to fix this problem. So, my original claim shall be weakened, as follows:

If the receiver and arguments of a message send are known to be DeepFrozen, and therefore stateless, then it is not necessary to delay the message in the fashion required by E-order.

It is not any harder to implement: if far refs have DeepFrozen flags then we can equally well check them for the arguments too.

I observe that this is slightly weaker than the condition required to generically turn a DeepFrozen function into a memoized DeepFrozen function; the latter also requires that the return value be Data (i.e. deeply not selfish).

[Karp, Alan H]

Ah OK. At a previous friam, when I suggested roughly similar optimizations in the context
of a Ken-like protocol (releasing messages before the end of a turn but marking them
speculative), I got a lot of pushback on that idea for the above reason.

Yes. The pushback had nothing to do with whether or not the message was delivered to the machine. It had to do with allowing that message to be processed and generate further speculative messages. Recovering from a failure ended up being essentially a Chandy-Lamport scheme.

________________________
Alan Karp
Principal Scientist
Enterprise Services, Office of the CTO
Hewlett-Packard Company
1501 Page Mill Road
Palo Alto, CA 94304
[phone], fax [phone]
http://www.hpl.hp.com/personal/Alan_Karp