[E-Lang] Ordering

[Mark S. Miller]

At 09:31 PM Thursday 7/19/01, Jonathan A Rees wrote:
>[...] I don't think it had a pointer to the argument that eventually
>swayed you.

I think you're right.  I think I did once briefly state what that initial 
argument (about Two Party ordering) was, but I'd have a hard time finding it 
as well.  ("Two Party" in the terminology of 
http://www.erights.org/elib/concurrency/partial-order.html )

At a certain point in the history of Electric Communities, we had a full 
distributed implementation of unordered Original-E that happened to preserve 
full "Two Party" ordering.  It did so not because it was required -- indeed, 
at the time it was a liability, as I'll explain.  It simply preserved full 
Two Party ordering because that was the path of least resistance -- a 
consequence of the easiest reliable (fail stop) implementation.  A vat's 
pending-delivery queue was fifo, and the stream in each direction between a 
pair of vats was fifo, and serviced in order.  Between a pair of vats we 
never allowed more than one connection (stream in each direction) for other 
reasons, but this also preserved the full ordering.

Since the language spec didn't provide full ordering, a program that 
depended on such ordering was considered buggy.  However, for programmers 
used to sequential programming (or used to leading mostly sequential lives), 
this was an easy kind of bug to make.  The E implementation would mask these 
bugs by causing such programs to run "correctly".

In reaction, I was both teaching people idioms for programming correctly 
within the unordered E spec, and working with other people on diagnostic 
tools to reveal bugs in programs that were "accidentally" acting correctly.  
(The idioms I was teaching were derived from Joule practice at the time I 
left Agorics.  Shortly after I left Agorics and joined EC, Joule 
independently decided to make partial ordering primitive.  I'll leave it to 
Dean to explain Joule's reasons.)

Trevor Morris (of EC at the time) pointed out how pointless this effort was. 
The property we were rebuilding expensively with idioms was already provided 
by the implementation for free.  Rather than declaring all programs which 
were unknowingly relying on such ordering buggy, why don't we just declare 
this property an official part of the language, and turn this class of 
undiagnosed bugs into correct behavior, all without needing to change any code?

I know I had a bunch of objections at the time, but I don't currently recall 
what they were.  (It's hard for me to remember years later how I could believe
something I then changed my mind on.)  However, I know I didn't make my 
peace with Two Party order until I understood how it generalized to Three 
Party and Four party ordering issues, also explained on that page.

The extended argument we had on e-lang, which I *can* find if you're 
interested, was, given that we have Two Party order, should we also 
guarantee Three Party order.  Note that Three Party order is far from free.  
In any case, I believe the unanimous consensus was that Three Party order is 
worth it.

I don't think we've ever argued about Four Party (eventual Grant Matcher) 
order, but given the others, I also don't think there's much to argue about.


>But by making sender and/or receiver identity figure in message
>passing semantics, it becomes difficult to employ an agent, yes?  [...]
>triangle inequality doesn't hold (sending from me to bank takes longer
>than me to agent + agent to bank)?

The real issue with the agent and the triangle is the security issue 
explained on the Three Party section of that page.


>I hope I'm merely ignorant here.  Perhaps there's more to E message
>ordering than what's in Walnut.  

Somewhat more, but hopefully not much more!  

>The reason I want to know this: I'm trying to convince a project to
>use Elib, and am getting "but promises are so complicated".  I want
>their defense to be as good as it can be.

Given asynch messages, I think asynch + promises is orthogonal from asynch + 
partial order.  But of course, I like having all three.

For material beyond Walnut for selling promises, see especially 
http://www.erights.org/elib/distrib/pipeline.html .  This pipelining 
technique was used at Xanadu circa 1990 
http://www.udanax.com/gold/index.html , and independently discovered by 
Barbara Liskov & Phillip Bogle circa 1994 as "Batched Futures" 
http://www.lcs.mit.edu/publications/specpub.php?id=1182 .


        Cheers,
        --MarkM