[E-Lang] security, comms, ordering guarantees

[Ralph Hartley]

zooko@zooko.com wrote (not in order):

> To me this issue seems so tightly related to other notions of capability and
> other notions of ordering and robustness that we should at least consider
> whether to integrate it into the fundamental comms abstraction.

> In any case, defining the ordering guarantees to be meaningful in the context of
> the receiving capability, or else in the context of (the receiving capability,
> the sending object) seems much cleaner to me than defining it in terms which
> include either the receiving or the sending Vat.  My impression is that one of
> the design goals of E is to abstract E code away from having to know which Vat
> it is in and which Vat it is talking to.  (Please confirm or deny this!)
> Certainly MarcS appears to have implicitly assumed that the sending Vat's
> identity was not a factor in security, and it seems like a natural assumption to
> me.

Here is my suggestion for a reasonable communication abstraction.

Let's call it a "channel".

A channel is just like a connection, except that it can never be broken. 
Once created, it continues to exist and function, until it is closed by 
either the sender being destroyed and the last message sent being 
recieved, or the reciever being destroyed (and it may continue longer, 
it's contract is vacuous once one of those thing happens).

It has one sender and one reciever. The sender sends messages which the 
reciever may recieve. The messages recieved are guaranteed to be:

(a) No messages are recieved that are not identical to a message that 
was sent.

(b strong) No message is recieved untill (or unless) all mesages sent 
before it have been recieved.

There is NO implication that the sender is on the same VAT as the 
reciever(the implimentation may be diferent if he is),  or that he or 
the reciever don't move from VAT to VAT. The sender and reciever are 
defined to be the holders of SEND and RECIEVE capabilities. They might 
not even be unique.

If there are multiple senders on different VATs exist, any 
implementation will require some form of coordination in order to 
fulfill the ordering promise. The coordination point could on be the VAT 
where it was created, or on the reciever's VAT. Similarly if there are 
multiple recievers.

> This is a strictly weaker guarantee than the "Up-To-Here." guarantee that E
> already offers -- when and if the counterparty processes message N, then he is
> guaranteed to have already processed message N-1.  (That is: if the Up-To-
> Here guarantee holds, then the No-Late-Messages guarantee holds, but not vice
> versa.)

This strong form is what willl be used most often. Most applications 
cannot be expected to make sense of out of order communications, there's 
just too much subtlety involved.

>Hm.  This is an intriguing technique that MarcS and MarkM have discovered.  It
>provides an ordering guarantee which can be called "No-Late-Messages." -- when
>and if the counterparty processes message N, then he is guaranteed not to
>subsequently process any message < N.
>
An usefull weaker form would be:

(b weak) The reciever is informed of the order in which the messages 
were sent (e.g. each message has a sequence number which is given to the 
reciever).

This allows the reciever to implement No-Late-Messages. In fact it can 
implement (b strong) and Up-To-Here as well, but at a cost, if one 
message is never delivered, latter ones won't either. This is really the 
main objection to (b strong), it is stopped by the loss of a single message.

We really want any channel that does (b strong), and some that do (b 
weak) to give us:

(c) All messages that are sent are delivered eventually, unless the 
reciever chooses otherwise or is distroyed.

This, of course, is hard to guarantee. SOMETIMES we might accept best 
effort. For some applications we might need more. Acks and 
retransmission increase the chances of messages being recieved, but they 
are essentially irrelevant to (a) and (b).

In fact, I don't know of any way to even enforce (b weak) that doesn't 
involve a trusted third party (note that the sender is a potential 
attacker).

We sometimes even need:

(c limited) All messages that are sent are delivered before some 
designated deadline.

I think the folks that work on real time operating systems wory a lot 
about this one (The car MUST start to brake within 100ms of the brake 
pedal being pressed, no exceptions). On a networked system, it often 
isn't possible.

>However, the No-Late-Messages guarantee can be implemented with less local
>state than the Up-To-Here guarantee.  The state required to implement Up-To-Here
>is as much as "a copy of all messages which have been sent but not yet acked".
>The state required to implement No-Late-Messages is simply "A capability to the
>stream of messages in question.".
>
I don't think this is true. Here is an implementation of Up-To-Here:

Sender - send each message once, in order, with a sequence number 
attached to each.

Reciever - process each message that arrives in order. If a message 
arrives that is not in order (if a message has been skipped), stop, do 
not process that message or any recieved afterwards.

Of course this doesn't guarantee (or even promote) condition (c).

Given condition (c) the recipient can also re-order the messages and get 
Up-To-Here, with only messages that arive out of order being stored.

Ralph Hartley