[cap-talk] Petnames versus E-order with ocaps

[David-Sarah Hopwood]

David-Sarah Hopwood wrote:
>  - a promise, in a given vat, is a mutable data structure that includes
>    the fields
>      referentCell:
>          a pointer to a mutable cell that, when the promise is
>          settled, will contain the ObjectID of the referenced object.
>      lastMessage:
>          the MessageID of the last message that *must* have been acted
>          on by the referenced object before it can receive any messages
>          sent on this promise.

Note that the lastMessage field represents an edge in the reference
topology described in the 'Tree Order' section of
<http://www.erights.org/elib/concurrency/partial-order.html>.

(The more general partial ordering described in
<http://www.erights.org/elib/equality/after-both.html> does not need
to be explicitly modelled, because it can be implemented in terms of
the tree ordering, as done by the implementation of 'join' on that page.)

[...]
> Pipelining can be maximized by implementing this model fairly literally.
> Messages are held by the receiving vat until they can be acted on in an
> order that is consistent with E-order.

The advantage of this approach relative to WormholeOp is that it can
be layered on top of a secure channel protocol such as TLS, without
having a higher layer perform additional crypto operations based on
keys established for the secure channel, which could be considered a
layering violation.

> (To avoid resource exhaustion, a
> vat could have a memory quota for held messages received from each other
> vat.) An implementation does not actually need to record *all* of the
> MessageIDs of messages already acted on by a given object, only those
> that might still be in some promise's lastMessage field (which is a
> distributed garbage collection problem with some potential optimizations
> specific to this context).

For example,
 - represent a MessageId as (ConnectionID, SequenceNumber), where
   ConnectionID identifies an in-order connection between a pair of
   vats, and SequenceNumber is the number of messages previously
   sent on that connection.

 - instead of recording the MessageIDs that have been acted on,
   the receiving end of each connection records the highest sequence
   number seen so far, and the set of lower sequence numbers for
   messages that have *not* been acted on.

   (This set will only contain sequence numbers of messages that were
   received out-of-order, or delayed due to the E-order constraint,
   and so its representation should remain fairly small.)

-- 
David-Sarah Hopwood ⚥