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

[Tyler Close]

Zooko wrote:
>  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.

I think E's archash technique is actually more flexible than this. In
an E message send, the sender gets to specify the address that the
return value will be placed at. The sender does this by providing a
nonce (the archash) that will be transformed by the receiver with a
one-way-hash (SHA1), to calculate the return value address. E uses
this in order to implement message pipelining. The sender can send the
expected return value address to another receiver, at the same time as
it is sending out the return value producing message. I think this is
more flexible than the Mojo technique because it would appear that the
Mojo technique does not support pipelining.

My proposoal is to use this same archash technique to also implement
"robust" references.

> 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.

Non-idempotent protocols are also much more flexible than idempotent
ones. By definition, the sender does not need to maintain as much
state in order to use the non-idempotent protocol. The solution must
be to make non-idempotent protocols safe. E currently does this, but
at the expense of exposing client code to the cruel realities of its
network.

> Where can I read more about "archashes"?

The basic concept is as I said above. More can be read in the "Active
Certificate" thread that MarkM authored a while back.

> 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.

I agree that this is a *very* important feature.

> 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.)

The ability to retry definitely lets you smooth over a lot of error
conditions. In this case, DoS can be seen as just a temporary network
failure. Wait until the storm is over and then pick up where you left
off.

> 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.

In terms of object programming, I think the latter case is the common
one. The former case isn't really a message send, but a series of
message sends. Implementing it just means not sending any new messages
if you find that most of the message you've sent haven't been settled
yet.

> 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.

This seems like an object API level decision, not message semantics
issue. Essentially, it sounds like you've got a Download object that
allows you to specify its message sending behaviour.

> 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.

Yes. I propose removing this burden. The Vat already has enough
knowledge to do the right thing.

Tyler