Re: Reliability of RPC services

[Jonathan S. Shapiro]

On Mon, 2006-04-24 at 19:35 +0200, Marcus Brinkmann wrote:
> At Mon, 24 Apr 2006 12:23:18 -0400,
> "Jonathan S. Shapiro" <address@hidden> wrote:
> > Delegation != move. Delegation can be accomplished by capability copy.
> > 
> > Or to put it another way
> > 
> >     move =def= copy + drop
> >     drop => drop notice
> >     drop notice => invoked capability
> >     invoked capability => invalid capability
> >     invalid capability => no valid response ever
> 
> These are your definitions.  But in my scenario, send-once aka reply
> capabilities can _not_ be copied, only moved, where move =def= copy +
> invalidation (_without_ invocation).

Some of those are definitely NOT my definitions. Since the conversation
has gotten out of control, let me try to establish a lexicon.

The question that we are trying to *answer* is "What properties should a
reply capability have?" The difficulty in the conversation generally is
that people are not stating their assumptions. The conversation will be
much clearer if everyone (including me) would explicitly identify their
assumptions using this lexicon.

Here is an enumeration of the properties that people have talked about.

    send once: All copies of the capability are efficiently invalidated
               when any copy of the capability is invoked. There are
               two sub-cases:

                 send at most once: the recipient will not receive
                    more than one message.
                 send exactly once: the recipient will receive exactly
                    one message.

    single copy: There is only a single valid copy of this capability
               in existence. When a "copy" is performed, the source
               is invalidated.

    notice of non-reference: A message will be sent to an FCRB when
               it is discovered that the FCRB is no longer referenced
               by a capability. There are several possible methods
               of doing this, but the two that have been discussed
               seriously are "disk garbage collection" and "reference
               counts". For purposes of understanding this feature,
               the idea of a "single copy" capability should be
               considered a special case of reference counting.

    notify on container destroy: when an object is destroyed, any
               reply capability inside it is invoked

    notify on overwrite: A message is sent whenever the capability is
               overwritten (yes, this really *was* suggested at
               one point).

    invalid capability: An invalid capability no longer names an
               object. Any attempt to invoke an invalid capability
               causes an exception to occur in the invoker.

Status of each:

send once: I don't think that anybody has argued against this. We all
seem to agree that a CALL should not receive multiple replies (if it
does, then it isn't a CALL -- it is something else). We all agree (and
we have a working design) that "send at most once" is feasible. Some
people are advocating "send exactly once", but this would make network
transparency impossible.

single copy: Many people are advocating this. Everyone who is doing so
is wrong and should stop. A "single copy" capability is a particular
choice of implementation whose objective is to simplify the
implementation of "notice of non-reference". There are two reasons that
everyone is wrong to push "single copy": (1) until we determine whether
the "notice of non-reference" feature is safe and desirable, we should
not be debating how to implement it, and (2) the implementation of
"single copy" is expensive, for reasons that I have described.

notice of non-reference: This is the feature that Marcus and others
believe that they want. They are misusing the "single copy" term to mean
this feature. I have stated that (a) it is expensive, (b) it is
difficult to implement, (c) it does not solve many other issues that
require a watchdog in any case, and (d) we should not multiply
mechanisms when an existing mechanism will suffice.

  Caveat: *if* this feature is actually well-motivated (the issue is
  the combination of points (c,d), then I can see some ways to reduce
  its overhead if a small delay in notification is acceptable. The
  achievable delay is likely to be about 5 minutes, so a watchdog
  is probably better in practice.

notify on container destroy: This was done in KeyKOS, but it has some
problems that have been identified in the discussion (mainly destruction
races if one server delegates to a second and is then destroyed).
Because of these races the feature was dropped in EROS, and I think it
is not a good model.

notify on overwrite: At least one person suggested that a message should
be sent whenever a capability is overwritten. I have pointed out that
this causes a bad multiplication of messages, and that it definitely
breaks many of the things that people are trying to fix. I believe that
everyone now agrees this is a bad idea.


If I understand Marcus's current position, Marcus has stated

  Reply capability = send exactly once + single copy
                     + notice of non-reference

However, what he actually wants is:

  Reply capability = send exactly once + notice of non-reference

I am advocating

  Reply capability = send at most once

because "send exactly once" is known to be impossible, watchdogs are
required anyway, and  "notice of non-reference" is not needed if
watchdogs are present.

In future replies, please be careful to write down what you mean by
reply capability. Everyone will benefit.

shap