The crackers behind last month’s well-publicized denial-of-service attacks on major Web sites must have thought they were pretty clever. To pull off the attacks, the hackers apparently enlisted a small army of well-placed, reasonably powerful computers to do the dirty work. Presumably the perps broke into the machines and planted software designed to send barrages of information requests over the Internet to the likes of Amazon.com, Yahoo! and E*Trade.
While computers connected to the Internet can be coordinated for nefarious (or at least extremely inconvenient) purposes, millions of PCs are working together toward useful — sometimes even noble — ends. Distributed computing harnesses the power of multiple far-flung computers working together to solve a single problem. It’s a concept that proves there really is strength in numbers.
There’s monstrous power in the average desktop PC, and it doesn’t take a computer scientist to realize that most people don’t put all of that power to good use. A growing number of distributed computing projects are lining up to harness idle processors and channel their energies toward a better understanding of everything from mathematics to the galaxy beyond our solar system.
The concept of employing multiple CPUs to solve a particular computing problem is nothing new. Multi-processor computers and the peculiar brand of coding wizardry needed to take advantage of parallel processing — an architecture that allows a computer to perform multiple operations at the same time — have been around for decades.
“The technology of distributed computing is old theories, but nobody’s really done it before,” said David McNett, president of Distributed.net, a distributed computing research organization. “Now we have this magical thing called the Internet.”
Indeed, the Internet has done for distributed computing what it has done for countless other “old theories” by providing the global network infrastructure to make them a useful reality. But the popularization of the Internet and the rapid advances to microcomputer processors were not quite enough to start the distributed computing renaissance. A spark was needed to light the fire.
That spark came from security software experts RSA Laboratories, which in 1997 announced a contest to crack a message encrypted using a 56-bit DES algorithm (RC5), with the goal of showing the weaknesses in the data encryption used in many sensitive applications. Despite the emergence of the currently uncrackable triple-DES encryption standard, so named because of its 168-bit key length, some banks and financial institutions still relied on standard DES to carry out transactions.
With a cash prize thrown in for good measure, Netizens were motivated to get organized and tackle the problem. Tens of thousands of Internet users participated in programs to download blocks of possible encryption keys and test them against the contest’s encrypted message using a “brute force” approach, which involved trying every possible combination until the algorithm was unlocked.
A mere 212 days later, the code was broken by Distributed.net after its members sifted through fewer than half of the possible encryption keys. It hardly mattered — with more than 5 billion keys being checked per day by Distributed.net users, it would have taken them less than three months to polish off the rest of the possibilities.
Out of this enthusiasm grew a greater awareness of the unrealized power of idle CPUs and the birth of other organizations like Distributed.net, which is now a massive umbrella with some 50,000 active users hacking away at even stronger encryption. In effect, there’s a new make and model of supercomputer on the market. All you need are 10,000 friends to put their PCs to work on a single project.
THE ALIEN CONNECTION
For decades now, scientists affiliated with the SETI (Search for Extraterrestrial Intelligence) project have scanned the heavens, listening for signs of civilization beyond our solar system. Since losing federal funding in 1993, SETI enthusiasts have had to get creative. The SETI@Home project, run out of the University of California at Berkeley, started in May 1999 as an way to process the backlog of SETI readings from the giant Arecibo telescope in Puerto Rico.
SETI collects radio and other electromagnetic signals from deep space. Various celestial objects including stars and pulsars naturally generate radio signals, and much of what SETI collects are background noises generated from the Earth and the human population. SETI looks for strong signals that build and fade in intensity — as would a radio signal coming from deep space — which helps eliminate earthbound clutter.
SETI@Home is a small application for Windows, Mac and Unix-based computers that connects with a server at UC-Berkeley and downloads a 300-kilobyte “work unit” of radio sweep data. When your computer’s CPU is not being used at full capacity (which is actually most of the time), the SETI@Home client analyzes the radio data looking for strong signals that fit the SETI requirements. When a work unit is complete, the client machine uploads the results, downloads a new work unit, and starts the process anew. On new computers, this process can take just six or seven hours. On older PCs, work units might require 24 hours or more.
“The original goal of the project was to do something that would involve the general public in science and get them excited, not to get the most cycles per second,” said David Anderson, director of the SETI@Home project.
Before launching the project, Anderson calculated that some 100,000 participants would be needed in order to analyze as much data per day as the supercomputers already in SETI’s stable.
SETI@Home has grown to some 500,000 simultaneous users, with 4,000 new users joining every day. “It’s the world’s largest supercomputer, and ten times bigger than any computer on the planet,” said Dan Wertheimer, chief scientist of SETI@Home.
The far-flung supercomputer already has worked for a combined 180,000 years of computing time in just nine months, presently at a rate of 1,100 years per day. And the SETI researchers pulled it off for an investment of less than $500,000.
“We’re the first big distributed project that’s sent a lot of data both ways,” said Wertheimer, alluding to the fact that projects such as RC5 code-cracking do not send back much in the way of results unless they find the one right encryption key.
SETI@Home’s success has been its own enemy, however. The project has been so successful that the project administrators constantly have been challenged to keep the data servers running efficiently. What’s more, enthusiasm for the project has resulted in a glut of participants, and not enough data to go around. “We’re actually trying to slow down the computation,” Anderson said. To slow down the pipeline, the next revision of the SETI@Home software will scan for signals 10 times more faint, which will require longer processing times per work unit.
SETI@Home’s success gives promise to a whole new class of distributed computing projects. “Scientists have come up with research they’d like to do, but when they add up the numbers, they find that maybe it would take 10,000 years of computer time, so they put that idea on the shelf because it sounds ludicrous,” Anderson said. “We’ve shown you can go beyond your wildest dreams in the amount of work you can get done.”
BEYOND SETI
Stephen C. Hayne, associate professor of information systems at Arizona State University and chairman of the Association for Computing Machinery’s Special Interest Group Supporting Group Work, says the “divide and conquer” strategy employed by projects such as SETI@Home doesn’t always work. “There’s a class of problem where you can’t do that, because the computations rely on too much communication,” Hayne said.
Projects such as SETI@Home work, even for two-way communication, because although SETI wants to know the results of each individual computer’s analysis, that reporting happens only once per work unit and it can happen at any time. None of the other nodes working on the project care when the data is returned. For projects that require individual processing units to be in constant communication, the Internet can pose a problem.
Even in an age where broadband access has become affordable, network latencies are far greater than the lag time found in traditional multi-processor computers. In those sorts of closed environments, “you can feed off the timings between the processors, and bank on certain results,” Hayne said. A still-unstable Internet offers no such assurances.
This inter-process communication is the reason most distributed computing projects to date have been limited to relatively straightforward mathematical problems, like the signal-strength tests in SETI@Home or the encryption key tests of the RC5 challenges.
Security is another concern that has kept distributed computing projects relatively simplistic. Straightforward mathematical problems always can be quickly and easily verified by a project coordinator if a result is in doubt. But more complicated problems are not so easy to test, and results might be skewed, either unintentionally or in a malicious attempt to sabotage a project.
These problems are among the reasons the SETI@Home client, while not inherently proprietary, remains completely closed-source and why Distributed.net protects certain vital network portions of its code while making the computational sections open source.
BROTHER, CAN YOU SPARE A CYCLE?
Will major corporations be making a pitch for your unused computer time soon? “There’s no reason why Pixar couldn’t do the next Toy Story in a distributed model,” said Distributed.net’s McNett. From computer-generated special effects to drug interaction modeling, there are a staggering number of problems that could be farmed out to the general public. Unlike hunting for prime numbers or alien life forms, however, this sort of work is lucrative, and users will expect to be paid.
“There will be a massive market for CPU time, and organizations will bid on those cycles,” McNett predicts. That could take the form of discounts or rebates on Internet access, monthly checks or direct deposits based on work units completed or some other form of performance-based reward. It’s not inconceivable that the “free PC” wars could shift from a forced-advertising to a forced-distributed computing project before too long, if the new “CPU economy” continues to flourish. But what of the distributed computing pioneers, who might find themselves competing for users?
“That’ll be great,” SETI@Home’s Wertheimer said. “I’d love it if people went to Web sites and decided what to work on today.”
Even if your company doesn’t have a particularly compelling problem to farm out in a distributed model, your sea of corporate desktops can be put to work on any number of current distributed projects. “Every once in a while I get a call from someone who ran something where they shouldn’t have, but 99 percent of the time the software is unobtrusive,” McNett said.
Not only are distributed computing projects corporate-friendly, a number of corporations are taking an avid interest in participating. Companies such as Sun Microsystems, SGI, Intel and Compaq front the leaderboard of SETI@Home users.
If you want to get your company chugging on a distributed computing project, McNett suggests coordinating with a LAN administrator to install a copy on a manager’s machine (with his or her consent, of course.) After a week or so, they should recognize that the tool is not a hindrance to productive work, nor a rogue program that will crash the machine.
If that doesn’t work, hit them with ecology. Something like: “You are using an otherwise wasted resource, so it makes sense from a conservation standpoint.”
Nobody will be surprised if history records that computers solved some of mankind’s most difficult problems. However, it will be worth cracking a smile when the historians point out that the computers did it all in their spare time.
SPEED FREAKS
Several corporations, universities and organizations have formed SETI@Home teams to compete for the top spots in the project’s power rankings. A high ranking in the standings leads to bragging rights as well as free PR.
The SETI@Home statistical rankings are based on the number of data blocks processed over the life of the project, but the bragging rights are based on average time to complete a single block.
Among SETI@Home clients, the average Pentium-class PC running Windows can complete a block in about 26 hours. The typical Macintosh crunches a block in just under 19 hours. A Pentium PC running Linux takes about 11 hours.
The current speed leaders are Compaq alpha machines running Tru64 UNIX. These high-dollar setups can crank through a block in about an hour.
Bookmarks
Distributed.net:
http://www.distributed.net/
SETI@Home:
http://setiathome.ssl.berkeley.edu/
SETI@Home statistics:
http://setiathome.ssl.berkeley.edu/stats.html
Stone SouperComputer:
http://stonesoup.esd.ornl.gov/
