Note to users. If you're seeing this message, it means that your browser cannot find this page's style/presentation instructions -- or possibly that you are using a browser that does not support current Web standards. Find out more about why this message is appearing, and what you can do to make your experience of our site the best it can be.

Science 28 July 2000:
Vol. 289. no. 5479, p. 503
DOI: 10.1126/science.289.5479.503c
Prev | Table of Contents | Next

NetWatch

Another devilishly hard computational problem has cracked under the coordinated assault of computers linked by the Internet. An alliance of 2500-some computer processors took just a week to solve "nug30," a problem that had resisted mathematicians' best efforts for 3 decades.

So-called distributed computing has already become a popular alternative to fighting for time on a supercomputer for some researchers. Perhaps the best known example is SETI@home, in which volunteers' PCs comb tiny chunks of data for radio signals from alien life. It was another collaborative effort, called MetaNEOS, that tackled the nug30 quadratic assignment problem. First posed in 1968, nug30 is an optimization problem--akin to the traveling salesman problem where someone tries to visit the state capitals while putting the minimum number of miles on his car.

The MetaNEOS team, based at Argonne National Lab in Illinois, solved nug30 in 7 days in June, using up to 1009 processors simultaneously at eight institutions to crunch the numbers. The feat marks perhaps the biggest distributed computing success yet outside of special demos or applications, says participant Miron Livny of the University of Wisconsin, Madison. The 96,000-CPU-hour problem could have been completed as quickly on a 1000-node supercomputer--but only if you could win time on one, says Livny. His goal "is to allow every scientist to do an order of magnitude more computing than they do today."

To Advertise     Find Products

Science. ISSN 0036-8075 (print), 1095-9203 (online)