[E-Lang] security, comms, ordering guarantees

[Karp, Alan]

Ralph Hartley wrote:
> 
> 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.
> 

There are plenty of times when messages can be handled in receive order.
The most common case is sending a large amount of data in separate pieces.
As another example, it doesn't matter in what order a sequence of deposits
(I should be so lucky :) appear in my account, but withdrawals need to be
ordered properly with respect to deposits.  

Switching normally involves a handshake, but we have a patent (sorry MarkM)
that lets the sender inform the receiver of whether messages must be
processed in send order or if they can be processed in receive order.  The
idea is entries in the message header that say "This is the Nth message.
You may process it after handling the Kth message."  If K=N-1, we have
send-order processing.  If, instead, K=N-M, then M messages can be processed
in the order received.  

I believe that this trick can be used with either up-to-here and
no-late-messages.  However, in the former case, "up-to-here" may need to be
modified to mean the next message to be processed in send order.  In the
latter case, we may have to undo anything associated with receive order
messages processed after the last send order message.

_________________________
Alan Karp
Principal Scientist
Decision Technology Department
Hewlett-Packard Laboratories MS 1U-2
1501 Page Mill Road
Palo Alto, CA 94304
(650) 857-3967, fax (650) 857-6278
https://ecardfile.com/id/Alan_Karp
http://www.hpl.hp.com/personal/Alan_Karp/
 

> -----Original Message-----
> From: Ralph Hartley [mailto:hartley@aic.nrl.navy.mil]
> Sent: Monday, April 23, 2001 10:19 AM
> To: zooko@zooko.com
> Cc: e-lang@eros-os.org
> Subject: Re: [E-Lang] security, comms, ordering guarantees
> 
> 
> 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
> 
> 
> _______________________________________________
> e-lang mailing list
> e-lang@mail.eros-os.org
> http://www.eros-os.org/mailman/listinfo/e-lang
>