Do you know what your computer is doing when you're not looking? Maybe you've signed up to participate in SETI@home, a program that harnesses the distributed computing power of volunteer PCs to look for radio signals from space. If so, you've downloaded special software. But a new kind of Internet-based distributed computing described today in Nature can use your machine without your knowledge or consent. Parasitic computing, as its creators call it, relies on the normal communication going on between Web servers to solve many pieces of a complex problem at the same time.
The researchers¿Albert-L¿szl¿ Barab¿si, Vincent Freeh, Hawoong Jeong and Jay Brockman of the University of Notre Dame¿decided to test their parasitic approach on what is known as an NP-complete problem. Such problems, which include the famous traveling-salesman problem, are standard tests of computing methods because they are defined by the fact that no known polynomial-time algorithm solves them. In this case, the team chose a satisfiability problem, which involves finding a solution to a Boolean equation that satisfies certain logical requirements.
Mathematicians often contend with NP-complete problems by generating large numbers of potential solutions that can then be tested¿ideally all at once, or in parallel. So Barab¿si and colleagues designed special messages to be distributed simultaneously to Web servers such that part of the message contained a possible solution to a satisfiability problem. Specifically, they coaxed target servers into testing whether or not the answers were valid by capitalizing on a calculation the targets do anyway: a simple "checksum" in the Transmission Control Protocol (TCP) that ordinarily tests whether a message has been corrupted en route.
The scientists designed the message so that the coopted checksum would send a response if the answer it tested were valid. If not, the TCP checksum fails and no reply is received. When they field-tested the scheme¿using an ordinary desktop computer and various unwitting Web servers across North America, Asia and Europe¿it worked like a charm. "The implementation represents only a proof-of-concept of parasitic computing," the authors emphasize, but add that they see no fundamental technical obstacles. That's not to say that there aren't possible complications. "Parasitic computing raises interesting ethical and legal questions regarding the use of a remote host without consent," they write, "challenging us to think about the ownership of resources made available on the Internet.