Vladimir Sedach

Have Emacs - Will Hack

June 3, 2007

Book review: Carriero and Gelernter's How to Write Parallel Programs

I recently finished reading Nicholas Carriero and David Gelernter's How to Write Parallel Programs (local mirror), a hidden gem on parallel computing published in 1990. A lot of books about distributed and/or parallel computing that I have come across are banal junk (who needs another poorly written book about MPI?). How to Write Parallel Programs contrasts sharply.

I suspect a major reason why parallel programming is considered difficult today is that most people do not have any conceptual feel for the space of possible parallel problem-solving approaches. Most educational material presents a fragmented view of models and paradigms; the vast majority of books focus on a single system or approach. The majority of programmers, not having delved into the breadth of the parallel computing literature, simply are not aware that there exist alternatives that may make their parallel problem-solving tasks much easier.

The key insight of How to Write Parallel Programs is distilling parallel programming to three distinct coordination paradigms. It may come as a surprise that DCOM, CORBA, RMI, or any other object-oriented "remote method call" junk is not one of them (the concept of "remote method invocation" manages to get both message-passing in object-oriented programming and the basic assumptions about distributed systems wrong at the same time - more people should listen to L Peter Deutsch and Alan Kay).

How to Write Parallel Programs is intended to be a textbook, and that means algorithm analysis. This frequently leads to surprisingly practical insights about distributed systems, such as load-balancing considerations, dealing with IO bottlenecks, and even using time complexity analysis to (inadvertently) find faulty nodes. Examples are written in C-Linda (an implementation of Gelernter's tuplespaces). Following the arguments and doing the exercises is well worth the time.

I will end this review with a request for help from the readers: I am trying to track down a copy of a paper referenced in the book: R. Abarbanel and A. Janin. Distributed object management with Linda. Research report, Apple Computer, Cupertino, CA, September 1989. If someone has a copy or can obtain one, please get in touch.