La computación amorfa se refiere a sistemas computacionales que utilizan un gran número de procesadores paralelos idénticos, cada uno de los cuales tiene una capacidad computacional e interacciones locales limitadas. El término Computación Amorfa fue acuñado en el MIT en 1996 en un artículo titulado "Manifiesto de Computación Amorfa" por Abelson, Knight, Sussman, et al.
Se pueden encontrar ejemplos de cálculos amorfos que ocurren naturalmente en muchos campos, tales como: biología del desarrollo (el desarrollo de organismos multicelulares a partir de una sola célula), biología molecular (la organización de compartimentos subcelulares y señalización intracelular), redes neuronales , e ingeniería química (sistemas que no están en equilibrio), por nombrar algunos. El estudio de la computación amorfa es independiente del hardware ; no se refiere al sustrato físico (biológico, electrónico, nanotecnología, etc.) sino más bien a la caracterización de algoritmos amorfos como abstracciones con el objetivo de comprender los ejemplos naturales existentes y la ingeniería de sistemas novedosos .
Las computadoras amorfas tienden a tener muchas de las siguientes propiedades:
- Implementado por dispositivos redundantes, potencialmente defectuosos y masivamente paralelos .
- Dispositivos que tienen memoria limitada y capacidades computacionales.
- Dispositivos asincrónicos.
- Dispositivos que no tienen conocimiento a priori de su ubicación.
- Dispositivos que se comunican solo localmente.
- Exhibir un comportamiento emergente o autoorganizado (patrones o estados más grandes que un dispositivo individual).
- Tolerante a fallas, especialmente a dispositivos con malformaciones ocasionales o perturbaciones de estado.
Algoritmos, herramientas y patrones
(Algunos de estos algoritmos no tienen nombres conocidos. Cuando no se conoce un nombre, se proporciona uno descriptivo).
- "Comunicación Fickian" . Los dispositivos se comunican generando mensajes que se difunden a través del medio en el que residen los dispositivos. La fuerza del mensaje seguirá la ley del cuadrado inverso como se describe en la ley de difusión de Fick . Los ejemplos de dicha comunicación son comunes en los sistemas biológicos y químicos.
- "Enlace de comunicación difusiva" . Los dispositivos se comunican mediante la propagación de mensajes a través de enlaces conectados de un dispositivo a otro. A diferencia de la "comunicación Fickiana", no hay necesariamente un medio difusivo en el que habitan los dispositivos y, por tanto, la dimensión espacial es irrelevante y la Ley de Fick no es aplicable. Se encuentran ejemplos en algoritmos de enrutamiento de Internet, como el algoritmo de actualización por difusión . La mayoría de los algoritmos descritos en la literatura sobre computación amorfa asumen este tipo de comunicación.
- "Propagación de ondas" . (Ref 1) Un dispositivo emite un mensaje con un recuento de saltos codificado. Los dispositivos que no han visto el mensaje anteriormente, incrementan el recuento de saltos y vuelven a transmitir. Una onda se propaga a través del medio y el conteo de saltos a través del medio codificará efectivamente un gradiente de distancia desde la fuente.
- "ID aleatorio" . Cada dispositivo se da a sí mismo una identificación aleatoria, siendo el espacio aleatorio lo suficientemente grande como para evitar duplicados.
- "Programa de punto de crecimiento" . (Coore). Procesos que se mueven entre dispositivos según el 'tropismo' (movimiento de un organismo debido a estímulos externos).
- "Coordenadas de onda" . Diapositivas DARPA PPT . Para ser escrito.
- "Consulta de barrio" . (Nagpal) Un dispositivo muestra el estado de sus vecinos mediante un mecanismo de empujar o tirar.
- "Presión de grupo" . Cada dispositivo mantiene un estado y lo comunica a sus vecinos. Cada dispositivo usa algún esquema de votación para determinar si cambiar o no de estado al estado de su vecino. El algoritmo divide el espacio de acuerdo con las distribuciones iniciales y es un ejemplo de un algoritmo de agrupamiento. [ cita requerida ]
- "Línea de auto mantenimiento" . ( Lauren Lauren, Clemente ). Se crea un gradiente desde un punto final en un plano cubierto con dispositivos a través de Link Diffusive Communication. Cada dispositivo es consciente de su valor en el gradiente y el id de su vecino que está más cerca del origen del gradiente. El punto final opuesto detecta el gradiente e informa a su vecino más cercano que es parte de una línea. Esto se propaga por el gradiente formando una línea que es robusta contra las interrupciones en el campo. (Ilustración necesaria).
- "Formación de clubes" . ( Coore, Coore, Nagpal, Weiss ). Los grupos de procesadores locales eligen un líder para que sirva como centro de comunicación local.
- "Formación coordinada" ( Nagpal ). Se forman varios degradados y se utilizan para formar un sistema de coordenadas mediante triangulación.
Investigadores y laboratorios
- Hal Abelson , MIT
- Jacob Beal , estudiante graduado del MIT (lenguajes de alto nivel para computación amorfa)
- Daniel Coore , Universidad de las Indias Occidentales (lenguaje de puntos de crecimiento, tropismo, serie de inversores desarrollados)
- Nikolaus Correll , Universidad de Colorado ( materiales robóticos )
- Tom Knight , MIT (computación con biología sintética)
- Radhika Nagpal , Harvard (sistemas autoorganizados)
- Zack Booth Simpson , Ellington Lab, Univ. de Texas en Austin. (Detector de bordes bacterianos)
- Gerry Sussman , laboratorio de inteligencia artificial del MIT
- Ron Weiss , MIT (activación de reglas, lenguaje de colonias microbianas, formación de patrones de coli)
Documentos
- La página de inicio de Computación amorfa
- Una colección de artículos y enlaces en el laboratorio de IA del MIT
- Computación amorfa (Comunicaciones de la ACM, mayo de 2000)
- Un artículo de revisión que muestra ejemplos del lenguaje de puntos de crecimiento de Coore, así como patrones creados a partir del lenguaje de activación de reglas de Weiss.
- "Computación amorfa en presencia de perturbaciones estocásticas"
- Un artículo que investiga la capacidad de las computadoras amorfas para lidiar con componentes defectuosos.
- Diapositivas de computación amorfa de la charla de DARPA en 1998
- Una descripción general de ideas y propuestas para implementaciones.
- PPT de Computación Amorfa y Celular de la Conferencia de la NASA de 2002
- Casi lo mismo que el anterior, en formato PPT
- Infraestructura para la aparición de ingeniería en redes de sensores / actuadores , Beal y Bachrach, 2006.
- Un lenguaje informático amorfo llamado "Proto".
- Patrones topológicos autorreparables Clement, Nagpal.
- Algoritmos de línea autorreparable y autosuficiente.
- Métodos robustos de sincronización amorfa , Joshua Grochow
- Métodos para inducir la sincronización temporal global.
- Autoensamblaje programable: construcción de una forma global utilizando interacciones locales de inspiración biológica y matemáticas de origami y diapositivas asociadas Tesis de doctorado de Nagpal
- Un lenguaje para compilar instrucciones de interacción local a partir de una descripción de alto nivel de una estructura plegada similar a un origami.
- Hacia un material programable , diapositivas asociadas a Nagpal
- Esquema similar al artículo anterior
- Estructuras autocurativas en computación amorfa Zucker
- Métodos de detección y mantenimiento de topologías inspiradas en la regeneración biológica.
- Ejecución en serie resiliente en máquinas amorfas [ enlace muerto permanente ] , Tesis de maestría de Sutherland
- Un lenguaje para ejecutar procesos en serie en computadoras amorfas.
- Paradigmas de estructura en una computadora amorfa , 1997 Coore, Nagpal, Weiss
- Técnicas para crear orden jerárquico en computadoras amorfas.
- Organización de un sistema de coordenadas global a partir de información local en una computadora amorfa , 1999 Nagpal.
- Técnicas para la creación de sistemas de coordenadas mediante formación de gradientes y análisis de límites de precisión.
- Computación amorfa: ejemplos, matemáticas y teoría , 2013 W Richard Stark.
- Este artículo presenta cerca de 20 ejemplos que varían de simples a complejos, se utilizan herramientas matemáticas estándar para demostrar teoremas y calcular el comportamiento esperado, se identifican y exploran cuatro estilos de programación, se prueban tres resultados de incomputabilidad y los fundamentos computacionales de un sistema de inteligencia dinámico y complejo. están esbozados.