[E-Lang] Hash Chaining & Capabilities, Proposal #1b: SimplifyingPluribus

[Mark S. Miller]

Everyone, and especially Tyler, very sorry for the delay!

At 04:04 AM 10/25/00, Tyler Close wrote:
>A while back, markm wrote:
>> So, if no one has a counter-argument, I'm still planning to
>> look up a
>> swissNumber rather than a pair, and I'm still planning to
>> use the Vine to
>> determine what vat to round trip to, rather than provide
>> other extra
>> information for this purpose.
>
>I don't think that the partial ordering of messages that E defines,
>guarantees that a round trip to the originating Vat will complete
>after the original message. The two messages are sent on different
>'live' references, so there are no order guarantees.

Currently, this isn't a fatal problem, since I only need to solve this 
problem within the Pluribus protocol, and the Pluribus protocol can validly 
count on properties of the Pluribus protocol that are beyond the E 
semantics.  Currently, the Pluribus protocol is conceived of as fully order 
preserving of all messages on a particular live inter-vat connection.  
Clearly, full-order preservation in the protocol is sufficient, but more 
than necessary, to implement order preservation of the messages on each 
individual reference carried by this connection -- hence the "beyond".  

This is much like the normal practice of an implementation being able to 
count on other "incidental" properties of the implementation that are not 
specified by the semantics being implemented, except that here one spec -- 
Pluribus -- is in the implementation role of another spec -- E.  Each of 
these specs has its own implementation as well.

OTOH, other things being equal, it's always better to count on less, as 
changes in one part of the system will cause fewer cascading changes.  Also, 
since Pluribus exists right now only to implement E's semantics across the 
network, the E semantics can be considered strictly more stable than the 
Pluribus semantics, so, other things being equal, it's better to count only 
on those properties of Pluribus demanded by E's semantics.  Therefore I 
appreciate what your suggestion is trying to do.  (Ironically, once E sees 
large scale use, the Pluribus semantics will be more stable, as network 
protocols are harder to change than languages.)

By fortuitous timing, Jed Harris has proposed a change in to Pluribus for 
better behavior under certain resource exhaustion accidents.  Jed's 
suggested change probably would relax the per-connection full ordering 
property I was planning to count on, while leaving the E semantics 
untouched.  So a suggestion such as yours would become necessary.

(Briefly, Jed suggests that only a bounded number of messages should be sent 
on a RemoteVow (an inter-vat promise) before hearing that the promise is 
resolved.  The bound should be high enough to get most of the benefit of 
pipelining, but, by being finite, causes an unbounded sending program to 
allocate only a finite amount of space in the recipient's vat, and instead 
allocate the unbounded amount of space in its own.  This causes the "pipes 
to back up" into the sender's vat, ultimately wedging it, rather than 
wedging the recipient's vat.  A useful safeguard for the "cooperative intent 
+ accident" situation.  Note that vastly more work would be required to 
guard against resource exhaustion attack.

With Jed's suggestion, the full order of messages on each reference no 
longer becomes a temporal full order of all messages on a connection.)


>I think a small change to the Vine will fix this. When VatA generates
>and sends the cap the VatB, it also includes the cap for the slot in
>VatA that VatC will eventually resolve. When VatC receives the message
>from VatB, and finds that the cap does not exist yet, it sends a
>"whenResolved" message on the second cap (the one identifying the slot
>in VatA). This is the same "whenResolved" message that promises
>currently support.
>
>The "whenResolved" message is the standard way to impose order on
>separate 'live' references, so it seems appropriate to use it to solve
>this problem.

But I'm not sure I understand your suggestion.  What do you mean by "slot"?  
How would this slot be connected to the Vine?