14
$\begingroup$

Greg Egan in his fiction "Dark Integers" (story about two universes with two different mathematics communicating by means of proving theorems around of inconsistence in arithmetic) claims that it is possible to build general purpose computer solely on existing internet routers using only its basic functionality of packet switching (and checksum correction, to be precise).

Is this possible, in principle?

Update.

To make the question more precise:

What is an absolutely minimal set(s) of properties the router network must have that it will be possible to build general purpose computer on top of it?

$\endgroup$
  • 3
    $\begingroup$ The question does not look well-defined. If it is, it is not understandable for those who have not read the mentioned book. $\endgroup$ – Tsuyoshi Ito May 24 '11 at 19:36
  • 1
    $\begingroup$ Perhaps the question will be better defined if I formalize it. But to do that correctly I must be on more than half way to the answer. $\endgroup$ – Vag May 24 '11 at 19:39
  • 1
    $\begingroup$ It will be better to add "So, the question: having only a network of IP packet switching machinery, it is possible to build on top of that a general purpose computer? Or I must to go further and assume a) having one shot packet originator or or b) having controllable constant packet source?" ? $\endgroup$ – Vag May 24 '11 at 19:42
  • 1
    $\begingroup$ The author do not delve much in details, he wrote something like I said -- just computer on routers, without details. $\endgroup$ – Vag May 24 '11 at 19:43
  • 3
    $\begingroup$ Not sure why this is off topic. It's definitely a little out there, and slightly vague. But it's an interesting question about universal models of computation $\endgroup$ – Suresh Venkat May 25 '11 at 5:55
21
$\begingroup$

This can be helpful:

Parasitic computing is an example of a potential technology that could be viewed simultaneously as a threat or healthy addition to the online universe. On the Internet, reliable communication is guaranteed by a standard set of protocols, used by all computers. These protocols can be exploited to compute with the communication infrastructure, transforming the Internet into a distributed computer in which servers unwittingly perform computation on behalf of a remote node. In this model, one machine forces target computers to solve a piece of a complex computational problem merely by engaging them in standard communication.

In the parasitic computing site you can detailed information on how you can solve a 3-SAT problem using the checksum of TCP packets.

Other useful links:

$\endgroup$
17
$\begingroup$

One approach for using internet routers etc as a computer was published in a letter in Nature by Albert-Laszlo Barabasi, Vincent W. Freeh, Hawoong Jeong & Jay B. Brockman. They called the idea Parasitic Computing. Their idea is to use the checks performed in the TCP protocols to perform calculations and solve NP-complete problems off-line, albeit on-line. The work has been extended here to a fully functioning virtual machine. Plenty of documentation (in German) and even the source code is provided.

The book Silence on the Wire provides a description of how this idea can be extended to use the packets floating around the internet as RAM by sending ill-formed packets containing data which subsequently get bounced back. The amount of RAM is equal to the number of packets sent out times the size of the packets.

$\endgroup$
  • 1
    $\begingroup$ RAM is good. But what about ALU? How to perform, say, compound computation consisting of two computations and third one using results of these two? $\endgroup$ – Vag May 24 '11 at 19:49
  • 1
    $\begingroup$ @Vag: I've improved my answer with a link describing how this can be done. $\endgroup$ – Dave Clarke May 25 '11 at 8:24
  • 1
    $\begingroup$ Cool! Sorry I can't accept two answers simultaneously! $\endgroup$ – Vag May 25 '11 at 8:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.