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

[zooko@zooko.com]

 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.