Lambda the Ultimate

I assume that by "threads" the authors mean "shared-state concurrency".

The article spends quite a bit of time on threads and shared state, and pointing out the difficulties with nondeterminism that ensue. IIRC the author makes the point that if there is no state shared between threads then they are very easy to use and analyze. The "problem with threads" lies in the current approach to sharing state by default, and "pruning away nondeterminism" to get a correctly functioning system. As I mentioned in my original post, much of this is familiar ground for readers of CTM.

The difference between Erlang and coordination languages is small. Erlang has named communication by default (the sender knows the receiver), whereas a Linda-style tuple space (the usual model assumed for coordination languages) has anonymous communication by default (the sender and receiver don't know each other).

I believe that the coordination languages which Lee is thinking of are ones that allow mixed models of communication. Lee is associated with the Ptolemy project at UC Berkeley. The Ptolemy II toolset allows use of multiple models of coordination (e.g. synchronous-reactive, synchronous data-flow, and rendezvous communications) in one design. The ability to choose "the right tool for the job" strikes me as very similar to the capabilities provided by Oz.

IIRC the author makes the point that if there is no state shared between threads then they are very easy to use and analyze.

Very easy? Analyzing concurrent systems is difficult even without the add fun of shared state. E.g., deadlocks etc. Unless you define shared-state to include communication between threads, but that's going a bit far...

Sorry, perhaps I was a little imprecise in my use of words. What I was trying to say was that the article points out that totally independent threads are easy to use and analyze. I really should have said "threads that share nothing".

As you rightly point out, even without shared state, deadlock and coordination problems are still an issue. I've spent a lot of time working on pure message passing systems, and still have to deal with these problems. Fortunately, I have CSP to help me detect and correct potential deadlocks in the design...

... in the sense of CSP or Unix (which is a degenerate case of CSP, though the model of Unix processes as exchanging byte streams is itself a degenerate case: normally Unix processes exchange line records, and the article's claim that pipes can't support loops is a consequence of shell syntax, not the primitives).

It may be useful to implement shared-nothing processes as OS threads or green threads or simple call/cc, but if they are shared-nothing, they are processes.

Are there languages which are vaguely in that direction? Or papers / notes about such designs? I'd be interested in hearing more, thanks!

I am not aware of production-quality implementations, but there are papers, some of them discussed in this thread.
The idea is not new, but I do not see any of the papers getting close to something realistic. Maybe this is caused by obsession with monads, and what is needed is courage to try something new... Or not so new: e.g., sketches (a lot of literature, I am currently reading some papers by John Power and Charles Wells). I would recommend Sketches: Outline with references as an introduction.

Polyglot is an extensible java compiler that has been used to add language features to Java. With Nate and Xin's work on J& they're modifying it to allow easy composition of added language features to create this sort of Mix'n'match compiler.

Ada tasking is based on a rendezvous model, and Ada95 added a monitor-like construct for shared data - beacuse the rendezous model proved inadequate. You should glance and the discussion regarding this decision in the Ada Rationale. While this doesn't answer your specific concern, I think it is of interest.

While the rendezvous model indeed doesn't resolve all the difficulties in concurrent programming, I think it does provide an easier programming model. It is also easier to reason about.

Both these facts are important, but they don't add up to "no more problems with concurrency", obviously...

Rendevous-based message passing also broken?

Any non-monotonic concurrency is... uhm... unsafe.
I mean monotonicity in the sense defined by concurrent constraint programming. As I understand it - monotonicity of predicate P means that if it holds at some moment t0, it holds forever after t0.
One example of monotonic behavior is a promise - once fulfilled it remains fulfilled forever. One example of non-monotonic behavior is a shared cell - its value can change any time.
Monotonic features are easier to schedule - it is always safe to access them a bit later (modulo fairness). Features that also are safe against early access (e.g., promises) make scheduler's job even simpler - basically fairness remains the only concern.

Interestingly, join patterns are not monotonic - they can be enabled at some moment, and become disabled later. The crucial feature of Join Calculus is to limit the scope of this non-monotonicity to a single syntactic unit - a definition. First, it ensures that all potentially unsafe interaction is written in one place by one person. Second, it simplifies scheduling - provided each definition is "run single-threadedly" (a strategy of the scheduler), the expectations of the programmer are not broken.

But I'm worried that the lack of message ordering in the Join Calculus causes programming difficulties

Yes, it does. Ordering can be encoded in the program, but unfortunately this would require busy waiting (I didn't prove that, so take it with a grain of salt). Join Calculus can be extended to either support some kind of ordering, or provide more powerful forms of joining (e.g., equality matching of parameters). Another very useful extension would be first class support for records (which can also be encoded, but in a very expensive way). And custom schedulers wont hurt, either. And macros... :-)
But enough of fantasies - I am almost tempted to accept this challenge - I only need to find some time to write an interpreter of user-friendly Join Calculus... Let's hope you will have no reason to introduce point 7 on that chart :-)

The rendezvous model was used quite successfully in the occam language. One advantage of the rendezvous model is that it admits algebraic reasoning (which I believe was outlined in Roscoe and Hoare's "The laws of occam programming" back in 1986 — sadly not available online). It is also possible to perform local analyses for deadlock, and to utilize process synchronization patterns (such as Peter Welch's IO-Seq and IO-Par patterns) to ensure global freedom from deadlock. Finally, at least in the case of occam, a rendezvous-based system can be readily modeled and analyzed in CSP (or some other process algebra), which permits potential deadlocks to be detected and eliminated (as well as permitting the proof of other properties).

This is not to say that the rendezvous model is the best in all situations. But in the embedded space where occam was most popular (and where Lee's primary concern appears to lie), it seems to have worked very well.

As an aside, it's probably worth noting that FIFO queues that permit asynchronous communications can be introduced (where necessary) into occam programs as a chain of buffering processes (which are also easily modeled in CSP). In the more modern JCSP library, which permits occam-style programming in Java, so called "buffered channels" are built into the system (and in fact one can choose the from several possible policies for the actions to take when the buffer is full — overwriting, overflowing, or blocking). Rumor has it that these built-in buffered channels may eventually make it back into occam-pi, which is the version of occam currently under development at the University of Kent.