[E-Lang] Promises, equality and trust

[Mark S. Miller]

At 02:54 PM Thursday 7/26/01, Mark Seaborn wrote:
>When they
>resolve, promises *become* the reference they resolved to, rather than
>just being [wrapping objects, like Scheme promises].  [list of advantages...]
>
>  This advantage seems to be thrown away by using the Miranda
>   method whenResolved for detecting resolution, since the object a
>   promise resolved to may tell the observer that the promise resolved
>   to something else.  eg.
>
>     when(X) -> done(Y) { Z } ...
>
>   When Z is executed, X will be resolved.  What, then, is the point
>   of Y?  If promises are a primitive provided by the vat, why isn't
>   there a per-vat whenResolved function instead of a Miranda method?

Thanks for probing this issue.  As a result of these questions, and of 
addressing other issues in the new captp system, the answer (starting in 
0.8.10) is that, when Z is executed, X and Y will indeed be identical, even 
if the object they designate overrides whenMoreResolved in an aberrant way.  
This is true even though the when-catch construct is still implemented using 
whenMoreResolved.  To understand this, let's expand the when-catch construct.

The when-catch construct's expansion to Kernel-E is unchanged from 0.8.9t.  To expand on your example, 

    when (X) -> done(Y) {
        ...Z...
    } catch problem {
        ...Handler...
    }

expands to

    Ref whenResolved(X, def done(temp) {
        if (Ref isBroken(temp)) {
            def problem := Ref optProblem(temp)
            ...Handler...
        } else {
            def Y := temp
            ...Z...
        }
    })

So we see that the when-catch construct is rather shallow syntactic sugar 
around Ref's whenResolved/2 
http://www.erights.org/javadoc/org/erights/e/elib/ref/Ref.html#whenResolved(java.lang.Object,%20org.erights.e.elib.util.OneArgFunc)
, which does the real work.  Everything to the right of the "->" is turned 
into the definition of the one-arg function that will be handed to Ref's 
whenResolved/2.  This function is used in an observer-like way.  Observers 
in E are called "reactors", so let's refer to this "done" function as the 
"reactor".  When does whenResolved/2 invoke the reactor?  What does it 
invoke the reactor with?  The javadoc-umentation at the above URL (which 
uses "ref" for the first "X" argument) says:

>If ref never becomes resolved, the reactor is not invoked. Should ref become 
>resolved, the reactor will be invoked exactly once. For example, if ref 
>becomes fulfilled and then broken, the reactor will hear of exactly one of 
>these events.
>
>Once ref becomes resolved the reactor will be invoked with the resolution. 
>Should the reactor be invoked with a non-broken value (and therefore a 
>fulfilled value), all earlier messages sent on ref before the whenResolved 
>are guaranteed to have been successfully delivered.

This text certainly corresponds to the normal assumptions under cooperative 
conditions.  What if the object designated by ref or the vat hosting the 
object are hostile and seek to disrupt these guarantees.  How bad can it 
get?  To explore this, I'll walk through the current draft implementation of 
whenResolved/2.  For layering reasons, this is actually implemented in Java, 
but for clarity I'll translate to E.

    def Ref {
        # ...
        to whenResolved(ref, reactor) {
            def wrappingReactor := WhenResolvedReactorMaker new(reactor, ref)
            ref <- whenMoreResolved(wrappingReactor)
        }
    }

where WhenResolvedReactorMaker is implemented equivalently to:

    class WhenResolvedReactorMaker(var optWrapped, var ref) :any {
        def WhenResolvedReactor {
            to run(_) {
                if (optWrapped != null) {
                    if (Ref isResolved(ref)) {
                        def tempRef := ref
                        def tempWrapped := optWrapped
                        ref := null
                        optWrapped := null
                        tempWrapped(tempRef)
                    } else {
                        ref <- whenMoreResolved(WhenResolvedReactor)
                    }
                }
            }
            to reactToLostClient(_) {
                WhenResolvedReactor(null) # invokes run/1 on itself
            }
        }
    }

and recall that the Miranda method for whenMoreResolved is equivalent to

    def Self {
        # ...
        to whenMoreResolved(reactor) {
            reactor <- run(Self)
        }
    }

Wherever a defining occurrence of a variable is expected, an "_" may be used 
instead as an "ignore pattern".  This means the two methods of 
WhenResolvedReactor don't care what argument they're provided.  Therefore, a 
malevolent invoker cannot cause mischief by providing a bad argument.  Also, 
we see that the two methods are equivalent, so no mischief can be caused by 
invoking the wrong method.  Remaining sources of mischief would only be to 
invoke one of these functions when it shouldn't, or not to invoke it when it 
should.

If these methods ignore their argument, what purpose do the corresponding 
messages serve?  In this context, they serve purely as a wakeup call to tell 
the WhenResolvedReactor to check if the original ref has become resolved 
yet. If it has, then it calls optWrapped -- the original done function -- on 
this original (and now resolved) reference.

A malicious X cannot cause damage by invoking these methods when it 
shouldn't.  Once optWrapped is called, it's dropped, and so will not be 
called more than once.  If these methods are invoked before ref is resolved, 
the done function isn't called or dropped, and a new whenMoreResolved 
message is sent (to re-request a wakeup call).

What about the guarantee that the done function will not be invoked until 
all earlier messages sent on X have arrived?  If a malicious X could arrange 
for the WhenResolvedReactor to be invoked after the reference is resolved, 
but before these earlier messages have arrived, then it could indeed disrupt 
our guarantees.  But it can't, since it won't get the whenMoreResolved 
message which gives it access to the WhenResolvedReactor until these earlier 
messages have arrived.

What about a malicious vat hosting a malicious X?  For these purposes, 
analysis must proceed 
http://www.erights.org/elib/capability/ode/ode-protocol.html#subj-aggregate 
by considering the vat as a whole as a composite, with X as a facet.  CapTP 
will not provide the malicious vat access to the WhenResolvedReactor until 
all prior messages meant for X have arrived at that vat.

Frankly, I don't know whether the safety provided by the last two paragraphs 
makes any difference at all.  However, since we are safe in this regard, I 
don't need to figure out whether it would make a difference if we weren't.  
This is an important design principle: it's often easier to provide a 
stronger guarantee, rather than figure out if there would be a problem with 
a weaker one.

A malicious X (or its hosting vat) can cause a denial of wakeup by not 
invoking the run method when it should.  The result would be that the done 
function is not invoked.  We could enhance the implementation so that the 
WhenResolvedReactor were also registered as an observer directly on ref, but 
then it would be woken up before prior messages had been delivered to X.  
Because this prior message guarantee is so useful, we choose to keep this 
property at the price of a possible denial of wakeup.  Perhaps we should 
revisit this decision.

Another kind of "malice" if you will is the unreliable network sitting 
between vats that might be trying to cooperate.  Even if X and its hosting 
vat wish to play by the whenMoreResolved rules, their run/1 response may not 
make it back to the WhenResolvedReactor because of a network partition.  To 
deal with this, the WhenResolvedReactor is also a DeadManSwitch, ie, an 
object that responds to reactToLostClient/1
http://www.erights.org/javadoc/org/erights/e/elib/prim/MirandaMethods.html#reactToLostClient(java.lang.Object,%20java.lang.Throwable) 
.  This will cause it to also eventually wake up on a network partition that 
could have prevented such a message from being delivered.  Since ref would 
have also been a remote reference to X, if ref were not already resolved, 
such a partition would also break ref.  Therefore neither accidental nor 
induced partitions can cause a violation of our guarantees.

Ironically, a partition will also cure any attempted denial of wakeups.


>If the invocation of observers passed in whenResolved messages is the
>way promises get resolved to values, wouldn't that mean promises can
>get resolved to different values in different vats?  A promise that
>started out being equal to itself would end up splitting into
>inconsistent values.

As we've already discussed, this issue is unavoidable between vats.  Based 
on the mechanism we explain above, we now perfectly avoid this issue within 
a vat.  How?

An important capability design pattern:  Want to avoid getting inconsistent 
answers to the same question?  Only ask the question once, and only 
"believe" the first answer.  For a given unresolved reference in a given 
vat, that vat must ask at least once "What's the resolution of this 
reference?" Because each vat must ask separately, they can be told different 
answers from each other, hence the unavoidable problem.

Within a vat, a captp unresolved remote reference automatically generates 
whenMoreResolved messages for answering this question.  Only one of these 
answers will be used to resolve the remote reference (ie, the arrow-tail 
side of the reference).  Normal programs are encouraged to ask the question 
using when-catch or Ref's whenResolved/2, and, by the above analysis, they 
thereby share the answer "believed" by the remote reference itself.


Once again, thanks for asking.  It took awhile to get this right, and 
figuring out how to answer your questions helped us think about the issues.


        Cheers,
        --MarkM