[E-Lang] New Page: Partially Ordered Message Delivery

[Karp, Alan]

You say "each programmer has to implement logic ...", but that's not the
case if you provide the appropriate library running in the sender's address
space.    That's what's been done in e-speak, and it works quite well.  In
particular, we provide send(), sendSynchronous(), sendReliable(), and
sendTransactional().

An earlier comment mentioned handling the logic in the Vat.  We rejected
this idea when desinging e-speak because of the danger of building up too
much state.  Instead, an undeliverable message is returned to the sender.
It's up to the library routine to decide what to do.

_________________________
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: zooko@zooko.com [mailto:zooko@zooko.com]
> Sent: Thursday, March 01, 2001 10:49 AM
> To: E Language Discussions
> Subject: Re: [E-Lang] New Page: Partially Ordered Message Delivery 
> 
> 
> 
>  Tyler wrote:
> 
> > At the implementation level, this means that when the sending Vat
> > discovers that the partition has been repaired, it repeats the
> > messages that it was waiting for a response to. If the receiving Vat
> > finds that the target reference is still valid, it uses the 
> archash in
> > the message to determine whether or not the message has already been
> > processed. If the message has already been processed, then 
> the archash
> > is already resolved to the return value. If the message has not been
> > processed, the Vat processes it as usual. If the target reference is
> > no longer valid, then the smashed message is returned.
> 
> 
> This sounds very like the technique which I devised for the
> "transaction" layer of Mojo Nation.
> 
> 
> In that system, each "response" message contains the secure 
> hash of the
> "initiating" message to which it is a response.  In addition, each
> "initiating" message has a unique unguessable nonce.
> 
> 
> This combination makes the transaction have the property of 
> "extensible
> fail-safeness" as defined by Li Gong and Paul Syverson[1][2], which
> basically means that you can believe that no possible active attack on
> the transaction can cause any worse harm than terminating the
> transaction.  
> 
> 
> In addition, this technique enables us to be sure that the 
> message will
> be evaluated "at most once", which enables retrying for greater
> robustness, as you appear to be describing above.  The important
> engineering advantage of this "at most once" guarantee is that
> programmers can write "non-idempotent" code, like "be advised 
> that your
> account balance has been incremented by 10", when they "should" have
> written "idempotent" code, like "be advised that you account balance
> has been incremented by 10 and is now equal to 110".
> 
> 
> The important fact is that programmers routinely write non-idempotent
> distributed operations, and they don't discover their error because
> messages rarely get delivered twice, unless there are exceptional
> network conditions, an active attack, or a mistake in which the sender
> retries the message thinking that the first copy never arrived.
> 
> 
> 
> Where can I read more about "archashes"?
> 
> 
> 
> A related feature of the Mojo transaction system is that all
> communications are message-based instead of stream-based.  
> This enables
> cheap stateless "relay" operations to bypass firewalls, 
> facilitates mix
> nets for anonymity, and enables transparent operation over HTTP, UDP,
> mixed substrates (for example the transaction is initiated 
> via HTTP but
> the response comes over a new TCP connection), etc.  
> 
> 
> In addition, I consider it to be more robust in terms of DoS attacks,
> because in order to cause a retriable message-based 
> transaction to fail
> you must stop either *all* of the copies of the initiating message or
> *all* of the copies of the response message.  To cause a stream-based
> transaction to fail, you just have to destroy one critical packet or
> other (I don't know the details of SSL or E's Vat Transport Protocol,
> but perhaps Ben Laurie or Bill Frantz respectively can confirm or deny
> this assertion).  (I believe this to be the case just based on the
> Byzantine General's problem and typical engineering considerations for
> stream protocols.)
> 
> 
> In terms of programmer usage, there are two kinds of situations: those
> in which you want to abandon the transaction as soon as you 
> think it is
> likely to fail, and those in which you want to keep retrying.  In Mojo
> Nation the former case is exemplified by downloading a block of data
> for multi-media streaming -- as soon as you think that the server is
> flaking out you want to abandon it and get the block from an alternate
> server.  The latter case is exemplified by making a token withdrawal,
> payment, or deposit.  You can't (without adding a complicated new set
> of features) recover nicely from a token transaction aborting because
> you don't know if the initiating message or the response 
> message is the
> one that failed (Byzantine Generals again), so you want to keep
> retrying your initiating message until you get a confirmation.
> 
> 
> Using the Mojo transaction system, the different behaviours are simply
> controlled by a flag (`retry=true' or `retry=false') which you pass to
> the `initiate()' method.
> 
> 
> In E, as I understand from reading and from talking to MarkM, only the
> first behaviour is built into the semantics, and each programmer has
> to implement logic to perform the second behaviour for himself, which
> means he has to be careful to make each of his messages idempotent or
> else he has to invent a generic "at most once" guarantee such as the
> ones we are discussing.
> 
> 
> Regards,
> 
> Zooko
> 
> [1] "Fail-Stop Protocols: An Approach to Designing Secure Protocols"
> http://citeseer.nj.nec.com/49099.html
> 
> [2] Fun footnote: Li Gong was the chief security architect for Java,
> and is now leading Sun's nebulous p2p tech platform "JXTA" that Bill
> Joy talked about at the O'Reilly p2p conference.
> 
> _______________________________________________
> e-lang mailing list
> e-lang@mail.eros-os.org
> http://www.eros-os.org/mailman/listinfo/e-lang
>