Autómata celular asíncrono

Los autómatas celulares , al igual que otros modelos de sistemas multiagente , suelen tratar el tiempo como discreto y las actualizaciones de estado como síncronas . El estado de cada celda del modelo se actualiza simultáneamente, antes de que los nuevos estados influyan en las demás. En cambio, un autómata celular asíncrono puede actualizar las celdas individualmente, de forma que el nuevo estado de una celda afecte al cálculo de los estados de las celdas vecinas.

Las implementaciones de actualización síncrona pueden analizarse en dos fases. La primera, la interacción, calcula el nuevo estado de cada celda en función de su entorno y la regla de actualización. Los valores de estado se almacenan temporalmente. La segunda fase actualiza los valores de estado copiando los nuevos estados a las celdas.

En cambio, la actualización asíncrona no separa necesariamente estas dos fases: en el caso más sencillo (actualización totalmente asíncrona), los cambios de estado se implementan de inmediato.

El enfoque síncrono presupone la existencia de un reloj global para garantizar que todas las celdas se actualicen simultáneamente. Si bien resulta conveniente para la preparación de sistemas informáticos , esta suposición podría ser poco realista si el modelo pretende representar, por ejemplo, un sistema vivo donde no hay evidencia de la presencia de dicho dispositivo.

Un método general, descubierto de forma independiente en repetidas ocasiones (por K. Nakamura en la década de 1970, por T. Toffoli en la de 1980 y por C.L. Nehaniv en 1998), permite emular con exactitud el comportamiento de un autómata celular síncrono mediante uno asíncrono, construido como una simple modificación del primero (Nehaniv, 2002). Sin embargo, la corrección de este método solo se ha demostrado rigurosamente más recientemente (Nehaniv, 2004). En consecuencia, se deduce inmediatamente de los resultados sobre autómatas celulares síncronos que los autómatas celulares asíncronos son capaces de emular, por ejemplo, el Juego de la Vida de Conway , la computación universal y la autorreplicación (como en un constructor universal de Von Neumann ). Además, la construcción general y la demostración también se aplican a la clase más general de redes de autómatas síncronos (redes no homogéneas de autómatas sobre grafos dirigidos, que permiten entradas externas , lo que incluye a los autómatas celulares como caso especial), mostrando de manera constructiva cómo su comportamiento puede realizarse de forma asíncrona mediante una red de autómatas asíncronos correspondiente.

Varios estudios han implementado modelos asíncronos y han encontrado que su comportamiento difiere de los síncronos. Bersini y Detours (1994) han demostrado cuán sensible es el Juego de la Vida de Conway al esquema de actualización. Cualquier comportamiento interesante desaparece en el caso asíncrono. Harvey y Bossomaier (1997) señalaron que la actualización estocástica en redes booleanas aleatorias resulta en la expresión de atractores puntuales solamente: no hay comportamiento cíclico repetible, aunque introdujeron el concepto de atractores cíclicos sueltos. Kanada (1994) ha demostrado que algunos modelos CA unidimensionales que generan patrones no caóticos cuando se actualizan síncronamente generan patrones de borde de caos cuando se aleatorizan. Orponen (1997) ha demostrado que cualquier red actualizada síncronamente de unidades lógicas de umbral (ver Neurona artificial ) puede ser simulada por una red que no tiene restricciones en el orden de las actualizaciones. Sipper et al. (1997) investigaron la evolución de CA no uniformes que realizan tareas de computación específicas. Estos modelos relajan el requisito normal de que todos los nodos tengan la misma regla de actualización. En sus modelos, los nodos se organizaban en bloques. Los nodos dentro de un bloque se actualizaban de forma síncrona, pero los bloques se actualizaban de forma asíncrona. Experimentaron con tres esquemas: (1) en cada paso de tiempo, se elegía un bloque al azar con reemplazo; (2) en cada paso de tiempo, se elegía un bloque al azar sin reemplazo; (3) en cada paso de tiempo, se elegía un bloque según un orden de actualización fijo.

Existen diferentes tipos de actualización asíncrona, y distintos autores los han descrito de diversas maneras. Los esquemas que se muestran en las imágenes a continuación son los siguientes (Cornforth et al., 2005):

• El esquema síncrono: todas las celdas se actualizan en paralelo en cada paso de tiempo. Este es el modelo convencional, que se presenta aquí a modo de comparación.
• El esquema aleatorio independiente: en cada paso de tiempo, se elige una celda al azar con reemplazo y se actualiza.
• El esquema de orden aleatorio: en cada paso de tiempo, todos los nodos se actualizan, pero en orden aleatorio.
• El esquema cíclico consiste en que, en cada paso de tiempo, se elige un nodo según un orden de actualización fijo, que se decidió aleatoriamente durante la inicialización del modelo.
• El sistema de sincronización automática consiste en que cada celda dispone de un temporizador independiente, inicializado con un periodo y una fase aleatorios. Al expirar el periodo, la celda se actualiza y el temporizador se reinicia. La actualización es autónoma y se realiza a ritmos diferentes para cada celda.
• El esquema de autosincronización es similar al esquema sincronizado, pero la fase de los temporizadores se ve afectada por el acoplamiento local con los vecinos, lo que permite alcanzar la sincronización local.

Los diagramas de estado-tiempo que se muestran a continuación ilustran las diferencias que se producen al modificar el esquema de actualización del modelo de autómatas celulares sin cambiar ningún otro parámetro. La regla utilizada, la regla 30 , es la misma para todos los diagramas.

A menudo, se utilizan modelos como los autómatas celulares para comprender mejor los procesos que ocurren en la vida real. Al construir modelos simplificados, se pueden obtener nuevos conocimientos. Siempre surge la pregunta de cuán simples deben ser estos modelos para describir adecuadamente lo que se está modelando. El uso de modelos asíncronos puede aportar un mayor nivel de realismo al modelo. Todos los esquemas descritos anteriormente tienen su aplicación en la vida real. El esquema aleatorio independiente podría ser apropiado para modelar redes sociales o la comunicación en redes informáticas . El esquema sincronizado podría ser apropiado para modelar colonias de insectos , mientras que el esquema autosincronizado podría aplicarse al tejido neuronal .

• H. Bersini y V. Detours, 1994. La asincronía induce estabilidad en modelos basados ​​en autómatas celulares, Actas de la IV Conferencia sobre Vida Artificial , páginas 382–387, Cambridge, MA, julio de 1994, vol. 204, n.º 1–2, págs. 70–82.
• Cornforth, D, Green, D, & Newth, D 2005, Procesos asíncronos ordenados en sistemas multiagente, Physica D , vol 204, no. 1–2, pp. 70–82.
• Cornforth, D, Green, DG, Newth D y Kirley M 2002, ¿Marchan las hormigas artificiales al unísono? Procesos asíncronos ordenados y modularidad en sistemas biológicos . En Standish, Bedau, Abbass, Actas de la Octava Conferencia Internacional sobre Vida Artificial , Sídney, pp. 28-32.
• Fatès N., (2014), Un recorrido guiado por los autómatas celulares asíncronos, Journal of Cellular Automata : Vol. 9(5–6), pp. 387–416, preimpresión
• Fatès N., y Morvan M., (2005), Un estudio experimental de la robustez ante la asincronía para autómatas celulares elementales, Sistemas complejos : Volumen 16 / Número 1, págs. 1-27.
• Fatès N., Morvan M., N. Schabanel y E. Thierry, (2006), Comportamiento totalmente asíncrono de autómatas celulares elementales doblemente quiescentes, Theoretical Computer Science : Volumen 362, pp. 1 - 16.
• Harvey I., y Bossomaier TRJ, (1997). Tiempo desfasado: atractores en redes booleanas asíncronas. En Husbands y Harvey (eds.), Actas de la Cuarta Conferencia Europea sobre Vida Artificial , 67–75, MIT Press .
• Kanada Y. (1994). Los efectos de la aleatoriedad en autómatas celulares 1D asíncronos . Vida artificial IV .
• Nehaniv, CL (2002). Evolución en autómatas celulares asíncronos, Vida artificial VIII , 65–73, MIT Press.
• Nehaniv, CL (2004). Las redes de autómatas asíncronos pueden emular cualquier red de autómatas síncronos, International Journal of Algebra & Computation , 14(5–6):719-739.
• Orponen, P. (1997). Computación con redes lógicas de umbral verdaderamente asíncronas. Theoretical Computer Science 174(1–2):123-136.
• Sipper M, Tomassini M. y Capcarrere MS (1997). Evolución de autómatas celulares no uniformes, asíncronos y escalables. Actas de la Conferencia Internacional sobre Redes Neuronales Artificiales y Algoritmos Genéticos (ICANNGA97) , Springer-Verlag.
• Laboratorio Virtual de la Universidad de Monash: Simulaciones en línea de actualización asíncrona en autómatas celulares.