<p>One approach for using internet routers etc as a computer was published in a
 <a href="http://www.nd.edu/~parasite/nature.pdf">letter</a> in Nature by Albert-Laszlo Barabasi, Vincent   W.  Freeh,  Hawoong Jeong
&amp; Jay B. Brockman. They called the idea <a href="http://en.wikipedia.org/wiki/Parasitic_computing">Parasitic Computing</a>. 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 <a href="http://www.szene.ch/parasit/">here</a> to a fully functioning virtual machine. Plenty of documentation (in German) and even the source code is provided.</p>

<p>The book <a href="http://rads.stackoverflow.com/amzn/click/1593270461">Silence on the Wire</a> 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. </p>

CC BY-SA 3.0
2011-05-24T19:49:58.060Z
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?
Vag
CC BY-SA 3.0
2011-05-25T08:24:23.940Z
@Vag: I've improved my answer with a link describing how this can be done.
Dave Clarke
CC BY-SA 3.0
2011-05-25T08:29:01.103Z
Cool! Sorry I can't accept two answers simultaneously!
Vag
CC BY-SA 3.0
2011-05-24T19:46:13.437Z
2011-05-25T08:23:55.640Z
2011-05-25T08:23:55.640Z
Dave Clarke
<p>This can be helpful:</p>

<p><strong><a href="http://en.wikipedia.org/wiki/Parasitic_computing">Parasitic computing</a></strong> 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. <em>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</em>. In this model, one machine forces target computers to solve a piece of a complex computational problem merely by engaging them in standard communication.</p>

<p>In the <a href="http://www.nd.edu/~parasite/">parasitic computing site</a> you can detailed information on <strong>how you can solve a 3-SAT problem using the checksum of TCP packets</strong>.</p>

<p>Other useful links:</p>

<ul>
<li><a href="http://www.scribd.com/doc/54525145/23496433-Parasitic-Computing">Seminar report on parasitic computing</a> by K.K.Maharana</li>
<li><a href="http://www.nd.edu/~parasite/nature.pdf">Nature's article on parasitic computing</a> (Aug 2001)</li>
</ul>

CC BY-SA 3.0
2011-05-25T08:16:48.727Z
2011-05-25T08:16:48.727Z
Marzio De Biasi
<p>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).</p>

<p>Is this possible, in principle?</p>

<p>Update.</p>

<p>To make the question more precise:</p>

<p>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?</p>

CC BY-SA 3.0
2011-05-24T19:36:34.697Z
The question does not look well-defined.  If it is, it is not understandable for those who have not read the mentioned book.
Tsuyoshi Ito
CC BY-SA 3.0
2011-05-24T19:39:04.663Z
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.
Vag
CC BY-SA 3.0
2011-05-24T19:42:25.770Z
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?" ?
Vag
CC BY-SA 3.0
2011-05-24T19:43:10.963Z
The author do not delve much in details, he wrote something like I said -- just computer on routers, without details.
Vag
CC BY-SA 3.0
2011-05-24T19:45:04.163Z
@ Tsuyoshi Ito: I've added tag "soft question" since if we state it more precisely we may alter the answer.
Vag
CC BY-SA 3.0
2011-05-24T19:47:04.863Z
Or it will be better to delete the question entirely?
Vag
CC BY-SA 3.0
2011-05-25T02:20:51.553Z
Vag, this is not a `soft-question`, please read the tag wiki. I think this question should be closed for several reasons, e.g. it is off-topic for cstheory, it is not a real question. Please read the FAQ.
Kaveh
CC BY-SA 3.0
2011-05-25T05:55:05.503Z
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
Suresh Venkat
CC BY-SA 3.0
2011-05-26T03:40:56.460Z
@Suresh, to me it seems like OP read a science-fiction book and then come up with "can this happen?" question, i.e. this does not seem like a research-related/level/oriented question that OP is seriously thinking about, IMHO it is more suitable for chat. But that is just my personal opinion.
Kaveh
CC BY-SA 3.0
2011-05-26T04:31:22.387Z
There's nothing wrong with being motivated by scifi :) - minority report becomes the kinect :). I personally thought the question was interesting (and so was Dave's answer).
Suresh Venkat
CC BY-SA 3.0
2011-05-26T08:13:35.187Z
@Kaveh: I completely understsand your point, so I must explain: I usually do not read anything except scientific papers and personal emails but in this case I made an exception because some physics professors adviced to read Egan's stories among other educational material and Egan is called "leader of super hard science fiction" who's writings consist of contemporarely scientifical thruths almost entirely. And I seriously thinking about mathematical definition of computation very often, reading works of Lamport and Gurevich etc and formalizing my thoughts in Coq.
Vag
CC BY-SA 3.0
2011-05-26T08:19:43.903Z
And I must add there are no (actual) comprehensive map of CS (nor science) so for any learner there are some areas that are completely hidden until someone points into important key words (as it happen in this case).
Vag
<computability><universal-computation>
Dark Integers: General Purpose Computations on Internet Routers
Vag
# Dark Integers: General Purpose Computations on Internet Routers

(Asked by: username_0 on 2011-05-24)

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?

**Tags:** computability, universal-computation
> **Comments:**
> **username_1**: The question does not look well-defined.  If it is, it is not understandable for those who have not read the mentioned book.  
> **username_0**: 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.  
> **username_0**: 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?" ?  
> **username_0**: The author do not delve much in details, he wrote something like I said -- just computer on routers, without details.  
> **username_0**: @ Tsuyoshi Ito: I've added tag "soft question" since if we state it more precisely we may alter the answer.  
> **username_0**: Or it will be better to delete the question entirely?  
> **username_2**: Vag, this is not a `soft-question`, please read the tag wiki. I think this question should be closed for several reasons, e.g. it is off-topic for cstheory, it is not a real question. Please read the FAQ.  
> **username_3**: 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  
> **username_2**: @Suresh, to me it seems like OP read a science-fiction book and then come up with "can this happen?" question, i.e. this does not seem like a research-related/level/oriented question that OP is seriously thinking about, IMHO it is more suitable for chat. But that is just my personal opinion.  
> **username_3**: There's nothing wrong with being motivated by scifi :) - minority report becomes the kinect :). I personally thought the question was interesting (and so was Dave's answer).  
> **username_0**: @Kaveh: I completely understsand your point, so I must explain: I usually do not read anything except scientific papers and personal emails but in this case I made an exception because some physics professors adviced to read Egan's stories among other educational material and Egan is called "leader of super hard science fiction" who's writings consist of contemporarely scientifical thruths almost entirely. And I seriously thinking about mathematical definition of computation very often, reading works of Lamport and Gurevich etc and formalizing my thoughts in Coq.  
> **username_0**: And I must add there are no (actual) comprehensive map of CS (nor science) so for any learner there are some areas that are completely hidden until someone points into important key words (as it happen in this case).  

---

## 2 answers

### Answer by username_5 on 2011-05-25. Score: 21 | Accepted answer

This can be helpful:

**[Parasitic computing](http://en.wikipedia.org/wiki/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](http://www.nd.edu/~parasite/) you can detailed information on **how you can solve a 3-SAT problem using the checksum of TCP packets**.

Other useful links:

* [Seminar report on parasitic computing](http://www.scribd.com/doc/54525145/23496433-Parasitic-Computing) by K.K.Maharana
* [Nature's article on parasitic computing](http://www.nd.edu/~parasite/nature.pdf) (Aug 2001)


---

### Answer by username_4 on 2011-05-24. Score: 17

One approach for using internet routers etc as a computer was published in a
[letter](http://www.nd.edu/~parasite/nature.pdf) in Nature by Albert-Laszlo Barabasi, Vincent W. Freeh, Hawoong Jeong
& Jay B. Brockman. They called the idea [Parasitic Computing](http://en.wikipedia.org/wiki/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](http://www.szene.ch/parasit/) to a fully functioning virtual machine. Plenty of documentation (in German) and even the source code is provided.

The book [Silence on the Wire](http://rads.stackoverflow.com/amzn/click/1593270461) 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.

> **Comments:**
> **username_0**: 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?  
> **username_4**: @Vag: I've improved my answer with a link describing how this can be done.  
> **username_0**: Cool! Sorry I can't accept two answers simultaneously!  

---

