[cap-talk] A Taxonomy of Current Object-Cap Systems

[David-Sarah Hopwood]

Mark Seaborn wrote:
> Plash's protocol is a point-to-point protocol and connections must be
> set up explicitly.  Suppose the processes have connections set up
> between them as follows:
> 
>     A
>    / \
>   B   C
> 
> If A invokes (an object defined by) B, passing a reference to (an
> object defined by) C, it does not automatically create a connection
> between B and C.  C gets A's proxy object, which will forward messages
> to B.
> 
> An alternative topology is
> 
>   A
>    \
>     B
>      \
>       C
> 
> This is not so good because if C creates further nested sandboxes, it
> can result in a longer chain of objects forwarded across connections.
> The first topology, where A acts as a hub, avoids that problem.

Any plans to support reference chain shortening in Plash?

> Toby Murray <toby.murray at comlab.ox.ac.uk> wrote:
>> An async senc without async receive might look like:
>>
>> asyncSend(cap,msg,replyCap);  // done async (e.g. in another thread)
>> waitForRecv(replyCap,&msg);   // block waiting for the reply
> 
> I would call that selective receive rather than synchronous receive.

Selective receive normally means that an arbitrary message pattern can
be matched. I would call this an "explicit closed receive":


   Explicit    Receive by explicitly invoking a primitive (usually blocking,
               but timeouts or polling may be supported) that returns the
               next message. [Erlang, KeyKOS/EROS/CapROS, Plash,
               Asynchronous Sequential Processes, Concurrent ML,
               Join calculus]

   Implicit    Receive implicitly at the top of a per-process/per-vat
               event loop. [E, A4, gen_server in Erlang/OTP]

   Interrupting
               Receive via an interrupt or scheduler activation.
               [Unix signals]

x

   Selective   Match an arbitrary message pattern. [Erlang, Join calculus]

   Closed set  Match messages to any of a set of facets (objects,
               message queues, ports, file descriptors, etc.) of this
               process/vat. [Unix select, A4]

   Closed      Match messages to a specified single facet of this
               process/vat. [EROS/KeyKOS/CapROS]

   Open        Match messages to any facet of this process/vat. [E, Plash,
               KeyKOS/EROS/CapROS, Asynchronous Sequential Processes]

x

   Synchronous-order
               A successful send happens as-if at the same time as the
               corresponding receive.
               [Concurrent ML, Synchronous pi calculus]

   Causal-order
               If M1 is sent before M2, and both messages are
               received, then M1 is received before M2.

   E-order     References are "forked" when sent between processes/vats.
               If M1 is sent before M2 on the same reference, or if
               M1 is sent to a reference R and then M2 is sent to a
               reference forked (maybe indirectly) from R, and both
               messages are received, then M1 is received before M2.
               [E, A4]

   (Point-to-point) FIFO-order
               If M1 and M2 are sent by process A to process B, and
               M1 is sent before M2, and both messages are received,
               then M1 is received before M2. [Erlang, Waterken]

   Fully asynchronous-order
               No constraints on message ordering, other than that a
               a message is sent before it is received, and there are
               no causal loops. [Actor model, Joule]


(A4 is a message-passing kernel language I'm developing.)

Selective and closed receives do not consume messages that are not
matched, so they are not equivalent to testing for a pattern after
performing an open receive. (Resending the message to self if the
pattern or id is not matched would change the message ordering.)

Selective or closed [set] receive can be simulated in terms of open
receive, by using a front-end process, called a "receptionist" in
actor terminology, that maintains a reified message queue. On each
receive, the main process makes a request to the receptionist
specifying the pattern or the set of facets to select, and it
returns and consumes the next matching message.

"Before" in the descriptions of message orderings refers to the
happens-before partial ordering.

Systems often support more than one kind of receive, but a given system
will usually only use a single message ordering, unless two systems with
different orderings have been bridged.

> To me, the term "asynchronous receive" suggests mechanisms like Unix
> signals, where the execution of the process is interrupted,

These are interrupting receives in the above taxonomy.

> or (assuming I understand it correctly) Coyotos's "notifications"
> system [1], which doesn't interrupt the execution of a process but
> is more akin to poll()ing file descriptors with a timeout of zero.

That's an explicit non-blocking receive.

>> An async receive without async send seems a bit strange and I'm not
>> sure that it exists anywhere, although it can be easily modelled.
> 
> How would you classify pi calculus with its rendezvous operation?

I'd classify the synchronous pi calculus as a synchronous-order
system with explicit closed receives.

-- 
David-Sarah Hopwood ⚥