Enteros oscuros: cálculos de uso general en enrutadores de Internet

14

Greg Egan en su ficción "Dark Integers" (historia sobre dos universos con dos matemáticas diferentes que se comunican mediante la demostración de teoremas de inconsistencia en la aritmética) afirma que es posible construir una computadora de propósito general únicamente en enrutadores de Internet existentes utilizando solo su funcionalidad básica de conmutación de paquetes (y corrección de suma de verificación, para ser precisos).

¿Es esto posible, en principio?

Actualizar.

Para hacer la pregunta más precisa:

¿Cuál es un conjunto absolutamente mínimo de propiedades que la red del enrutador debe tener para que sea posible construir una computadora de propósito general sobre ella?

computability universal-computation Vag
fuente
3
La pregunta no se ve bien definida. Si es así, no es comprensible para aquellos que no han leído el libro mencionado.
Tsuyoshi Ito
1
Quizás la pregunta se definirá mejor si la formalizo. Pero para hacerlo correctamente debo estar a más de la mitad de la respuesta.
Vag
1
Será mejor agregar "Entonces, la pregunta: tener solo una red de maquinaria de conmutación de paquetes IP, ¿es posible construir encima de eso una computadora de propósito general? O debo ir más allá y asumir que a) tener un paquete único ¿o b) que tiene una fuente de paquete constante controlable? " ?
Vag
1
El autor no profundiza mucho en los detalles, escribió algo como dije: solo computadora en enrutadores, sin detalles.
Vag
3
No estoy seguro de por qué esto está fuera de tema. Definitivamente es un poco por ahí, y un poco vago. Pero es una pregunta interesante sobre los modelos universales de cómputo
Suresh Venkat,

Respuestas:

21

Esto puede ser útil:

La computación parasitaria es un ejemplo de una tecnología potencial que podría verse simultáneamente como una amenaza o una adición saludable al universo en línea. En Internet, la comunicación confiable está garantizada por un conjunto estándar de protocolos, utilizado por todas las computadoras. Estos protocolos pueden ser explotados para computar con la infraestructura de comunicación, transformando Internet en una computadora distribuida en la que los servidores realizan cómputos involuntariamente en nombre de un nodo remoto . En este modelo, una máquina obliga a las computadoras objetivo a resolver una parte de un problema computacional complejo simplemente involucrándolos en la comunicación estándar.

En el sitio de computación parásita , puede obtener información detallada sobre cómo puede resolver un problema de 3-SAT utilizando la suma de verificación de los paquetes TCP .

Otros enlaces útiles:

Marzio De Biasi
fuente
17

Un enfoque para el uso de routers de Internet, etc como un ordenador fue publicado en una carta en la naturaleza por Albert-Laszlo Barabási, Vincent W. Freeh, Hawoong Jeong & Jay B. Brockman. Llamaron a la idea Computación parasitaria . Su idea es utilizar las comprobaciones realizadas en los protocolos TCP para realizar cálculos y resolver problemas NP-completos fuera de línea, aunque en línea. El trabajo se ha extendido aquí a una máquina virtual totalmente funcional. Se proporciona mucha documentación (en alemán) e incluso el código fuente.

El libro Silence on the Wire proporciona una descripción de cómo se puede extender esta idea para usar los paquetes que flotan en Internet como RAM enviando paquetes mal formados que contienen datos que posteriormente se recuperan. La cantidad de RAM es igual a la cantidad de paquetes enviados por el tamaño de los paquetes.

Dave Clarke
fuente
1
La RAM es buena ¿Pero qué hay de ALU? ¿Cómo realizar, digamos, el cálculo compuesto que consiste en dos cálculos y el tercero usando los resultados de estos dos?
Vag
1
@Vag: he mejorado mi respuesta con un enlace que describe cómo se puede hacer esto.
Dave Clarke
1
¡Frio! Lo siento, no puedo aceptar dos respuestas simultáneamente.
Vag