[cap-talk] Is "Authority" Subjective?

[David Hopwood]

Toby Murray wrote:
> On Fri, 2007-06-22 at 16:40 +0200, Pierre THIERRY wrote:
>> As I have understood
>> it from various discussions and presentations about capabilities, here
>> we mean that a subject has a permission on object B if A can invoke
>> some methods of B, and that A has an authority on B if A can use some of
>> its permissions for some methods of B to be invoked.
> 
> This appears objective -- or perhaps I mean "well-defined" (probably
> "sujective" wasn't the word I wanted originally but never mind). What
> we probably mean by authority is:
> 
> A has authority over B if A can use some of its permissions to /cause/ B
> to do something (whether respond to an invocation or whatever doesn't
> matter -- I'm not limiting myself to the object-capability model here.)

I would make this more precise as follows: define causality as a partial
order between events, by specifying which events directly cause others
in a given system.

Then, the authority of a subject is the set of events that can be caused
directly or indirectly by an event performed by that subject.

(Strictly speaking, we should distinguish between events and event
labels. If the message "a <- foo()" is sent twice, for example, then
that would be two distinct events with the same label. What we're
usually interested in is whether a subject can cause any event with
a label from a given set. I'll use <foo> below to refer to
"some event labelled 'foo'".)

For example, in a message-passing system:

 - sending a message M causes the reception of M by its target object.

 - if events occur as a result of receiving a message (such as other
   message sends, writes to variables, or a return message), then the
   message reception causes those events.

 - each read of a variable v is caused by the preceding write to v,
   whose value is obtained by the read.

 - if a write or message send has a control or data dependency on a
   read, then it is caused by that read.

This is closely related to "necessarily happens before" relations
that are often used to define concurrency semantics:

 - It is obvious that if e causes e', then e must happen before e'.
   [*]

 - In many systems, the converse also holds: the concurrency semantics
   is defined in such a way that e only *must* happen before e' in
   exactly the cases where it would be reasonable to say that
   e causes e'. I believe this is the case for the actor model, for
   example.

(Many systems require that the processing of messages by a given process
is serializable, but this is not a constraint on the ordering, i.e. if
turn t2 follows t1 in one execution, but t1 could have followed t2 in an
alternative execution with the same external input events and all
processes having the same code, then t2 is not caused by t1.)

Note that this definition is conservative in the sense that it can
treat an event e' as being caused by e even though e' may have
necessarily happened anyway. For example, suppose that at a given
point some object can only receive messages m1 or m2, and either way
it sends the message m3 (with the same target and payload). Then the
sending of m3 is caused by the reception of m1 (for example), even
though it would still have occurred even if m2 had been received
instead. I don't think this is really a problem, though.

A limitation of this definition is that it can only directly model
authorities that correspond to some event occurring, as opposed to a
combination of events or the prevention of an event. (OTOH, it is
possible to model things like the authority to perform a revocation
via a specific caretaker or membrane, since that corresponds to a
single event.)

> Suppose we have 3 objects/subjects/actors/whatever, Alice, Bob and Carol
> and the system is 
> 
> P = aliceInvokesCarol -> carolRespondsToAlice -> bobInvokesCarol -> STOP
> []
>     bobInvokesCarol -> STOP
> 
> i.e. initially either Alice or Bob can invoke Carol. Once invoked by
> Alice, Bob can't invoke Carol until she responds to Alice.

[I'd just like to add my voice to Jonathan and Valerio's dislike of the
Alice/Bob/Carol convention for naming processes or subjects. If you must
use personal names, please at least use lowercase to indicate that they
are not principals, and "it" as the pronoun rather than "he" or "she".]

> Would you say that Alice can cause Bob to invoke Carol?

According to the causality relation approach described above, yes,
alice can cause <bobInvokesCarol>. This is because alice participates
in <carolRespondsToAlice>, and <bobInvokesCarol> is caused by
<carolRespondsToAlice>.

As others have noted, this example depends on the fact that CSP is
synchronous. If the response by carol were asynchronous, then carol
would send the response and immediately be invokable by bob; in that
case, <bobInvokesCarol> would not be causally dependent on any event
performed by alice (assuming that it is not causally dependent on
<aliceInvokesCarol>).

OTOH, there are examples in asynchronous systems that are very similar
to this one: suppose that carol is a reversible caretaker, and alice
revokes, then unrevokes bob's access through that caretaker. I think
we need alice to be considered to have authority to cause
<bobInvokesCarol> in this case.


[*] A professor was notorious for leaving complicated demonstrations
    to the students, with no more than a remark that "It is obvious
    that..."
    One day a student interrupted: "Professor, is it really obvious
    that the second line follows from the first?"
    The professor peered intently at the blackboard, wrinkled his brow,
    and started to scribble furiously. Half an hour later, he turned
    back to his students and triumphantly said, "Why yes, it is
    obvious."

-- 
David Hopwood <david.hopwood at industrial-designers.co.uk>