Worms and Distributed Computations

Posted on Wednesday, February 20, 2008.

John Shoch and Jon Hupp's 1982 paper “The ‘Worm’ Programs—Early Experience with a Distributed Computation” (PDF, also HTML) discusses a fascinating series of distributed computation experiments carried out on a network of Altos at Xerox PARC. An earlier post discussed the Alto file system.

The Alto had memory to run only one program at a time and lacked virtual memory. It multitasked by swapping one program (and often much of the operating system) completely to disk and then loading a different one. Such a “world swap” took about two seconds. Because of this usage model, users tended to close their programs before going home, leaving the machine idle for other uses at night. Because they came out at night, the programs were sometimes called “vampire programs.”

Shoch and Hupp called their programs “worms” after the electronic tapeworm created in John Brunner's 1975 book The Shockwave Rider*, although the distributed computation ideas probably predate the book. (They lament that the phrase “distributed computing” “has already been co-opted by those who market fairly ordinary terminal systems,” although, at least in my experience, the phrase seems to have been restored to its original meaning.)

The paper discusses a handful of possible distributed computations, ranging from a simple “hello,world” to a multimachine animation computation. Perhaps the most interesting part is Section 5, which gives some of the history of multimachine programs on the Arpanet (the predecessor of the Internet). Of course, there are the network's routers themselves; maintenance of routing tables is almost certainly the longest-running distributed computation in history. The paper gives a few other examples, most notably a multimachine air traffic control simulation called McRoss (multicomputer route oriented simulation system). McRoss partitioned the air space among the computers running the simulations; particular planes were handed off from one computer to another as they flew around the air space.

The summary concludes:

This summary is probably not complete or fully accurate, but it is an impressive collection of distributed computations, produced within or on top of the Arpanet. Much of this work, however, was done in the early 70s; one participant recently commented, “It's hard for me to believe that this all happened seven years ago.” Since that time, we have not witnessed the anticipated blossoming of many distributed applications using the long-haul capabilities of the Arpanet.

In 2008, it's still hard to believe that this all happened 30 years ago. In the past decade, such distributed computations have really taken off (SETI@home started in 1999). Today, BOINC and other projects enlist the help of millions of computers to attack problems ranging from chess to malaria.