Guestrin, Goldstein, and Haigh present DARPA ISAT Study
The Internet, the powergrid, and the telephone system. These are examples of critical infrastructure that are based on large-scale distributed systems. These systems have been painstakingly engineered at great effort and expense to accomplish something that is well known to be extremely difficult: to get a very large collection — or “ensemble” — of computing elements to work together reliably and efficiently to accomplish a task. Will we see more distributed systems in the future? It seems likely, and in fact the systems we want to build in the future might be much larger than those of today. How will we build them, and in particular, how will we program them?
These questions and others were contemplated in a nine-month long study under the auspices of DARPA’s Information Science and Technology Board (ISAT). Last month, Carlos Guestrin made a presentation to the DARPA Director, Tony Tether, on the study’s results. The study was co-chaired by Carlos, Seth Goldstein, and Karen Haigh (of BBN but formerly a graduate student here). They enlisted the help of about 40 other prominent computer scientists and engineers.
I found Carlos’ presentation to be technically impressive. He has a clear, persuasive style that makes one forget how junior he is. In part, his good performance is the product of a great deal of expertise in the problem domain. The kinds of sensor nets he develops make very interesting use of distributed computing. In a relatively short time here, he and others have developed ideas that are elegant in their application of mathematical concepts to the practical problems of coordinating large numbers of unreliable sensors. In another project, co-chair Seth Goldstein, along with Todd Mowry, Jason Campbell (at Intel) and others have been developing the startling idea of Claytronics, a substance made up of thousands or millions of sub-millimeter robots, networked together and working as one to form into macro-scale shapes. Recently, the project has been extremely successful publishing in relevant symposia such as IROS and ICRA, as well as in major media such as CNN. (See the CNN story on Claytronics.) DARPA, of course, faces the challenge of the networked battlefield — variously referred to as the “battlespace infosphere” or “network-centric warfare” — moving it from concept to reality. In the future, every vehicle, soldier, and weapon in a theater of operations will have multiple computing devices and sensors, ideally networked together to provide clearer situational awareness and allocation of resources.
All of this begs the question: How on earth are we going to program these systems? Very large scale, successful systems, like the Internet, were products of massive amounts of experimentation, research, and engineering effort. Is there something to be learned from this and other examples, that might guide us in future systems? These and other related questions were the subject of the ISAT study, entitled “Engineering Ensemble Effects”. On September 17, 2007, Carlos Guestrin gave a 45-minute presentation on the results of the study to Dr. Tether. (The powerpoint slides are held by DARPA and thus I can’t post them here. However, it may be possible some day for Carlos to give a seminar for us.)
DARPA ISAT
A few words about DARPA ISAT. This study board is roughly similar to other government-sponsored study boards such as the Army Science Board, Defense Science Board, and the NRC’s Computer Science and Telecommunications Board. Established 25 years ago, it’s roughly 70 members conduct 2 or 3 studies annually on topics proposed by members and then selected through a competitive process. Members serve for three years, and new members are nominated annually and elected in an annual meeting. Membership is quite selective. Traditionally, CMU has had very good representation, with past members including Tom Mitchell, Bill Scherlis, Seth Goldstein, Jeannette Wing, and others. Today, Jessica Hodgins and Carlos Guestrin are members, and this fall I am slated to be the new Vice Chair for two years and then after that the Chair.
In contrast to more typical study boards at the NRC or the armed services, ISAT gets its ideas for studies directly from its own members, not from the sponsors. DARPA program managers are allowed to see the members’ study proposals very early on and provide feedback and guidance. Their input and interest level ends up being important factors in the selection of study topics.
While the input of DARPA program managers in the selection of study topics can be viewed as “meddling”, it also means that ISAT studies have an unusually high “hit rate”, in the sense of influencing DARPA investment
decisions, particularly in new programs.
E3
So, what were the main conclusions of the E3 (Engineering Ensemble Effects) study? Well, first off, it’s not hopeless. While it may seem that large ensembles will always be too complicated to program and get right, early experience with some applications, such as sensor nets and Claytronics, shows that as the ensemble scales, it sometimes becomes possible to depend less on the reliability of individual nodes. The study contemplates, for example, a “thermodynamic” model of distributed systems. This is in contrast to conventional approaches to distributed systems, where the behavior of each node must be precisely controlled. Instead, the study appeals to an analogy with physical systems such as gases, where the precise behavior of each molecule is not controlled but physical laws still allow key properties of the ensemble to be predicted and controlled.
The study further argues that a software model for ensembles, based loosely on the same kind of layering principle seen in today’s networking systems software, can form the basis of a wide range of ensemble systems and even be supported by tools for programming ensemble systems. I found this part of the study findings to be particularly intriguing, and also controversial. The claim that there is a useful organizing principle for a wide range of large-scale ensemble systems is an audacious one. While it is interesting that the study’s examples seem to show this might in fact be possible, a lot more investigation is needed. Ultimately, finding enough commonality so that tools and even code might transfer from domain to domain looks to be extremely difficult.
What will DARPA do with the study results? It is never easy to understand what and how DARPA does, although if past history is any indication, bits and pieces of the study findings will end up having a fundamental influence on the thinking in future programs that involve large numbers of networked nodes.
Peter Lee @ October 15, 2007