NET NEWS: Milestone for Linked Computers

See allHide authors and affiliations

Science  28 Jul 2000:
Vol. 289, Issue 5479, pp. 503
DOI: 10.1126/science.289.5479.503c

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, 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.”

Navigate This Article