Problema de sincronización del pelotón de fusilamiento

El problema de sincronización del pelotón de fusilamiento es un problema de informática y de autómatas celulares cuyo objetivo es diseñar un autómata celular que, partiendo de una única célula activa, llegue a un estado en el que todas las células estén activas simultáneamente. Fue propuesto por primera vez por John Myhill en 1957 y publicado (con una solución de John McCarthy y Marvin Minsky ) en 1962 por Edward F. Moore .

El nombre del problema proviene de una analogía con los pelotones de fusilamiento del mundo real : el objetivo es diseñar un sistema de reglas según el cual un oficial pueda ordenar a un equipo de ejecución que dispare de manera que sus miembros disparen sus rifles simultáneamente.

Más formalmente, el problema se refiere a autómatas celulares , conjuntos de máquinas de estados finitos llamadas "celdas" dispuestas en una línea, de modo que en cada paso de tiempo cada máquina pasa a un nuevo estado en función de su estado anterior y de los estados de sus dos vecinas en la línea. Para el problema del pelotón de fusilamiento, la línea consta de un número finito de celdas, y la regla según la cual cada máquina pasa al siguiente estado debería ser la misma para todas las celdas interiores a la línea, pero se permite que las funciones de transición de los dos puntos finales de la línea difieran, ya que a estas dos celdas les falta un vecino en uno de sus dos lados.

Los estados de cada celda incluyen tres estados distintos: "activa", "quiescente" y "activa", y la función de transición debe ser tal que una celda que está en estado quiescente y cuyas vecinas están en estado quiescente permanezca en estado quiescente. Inicialmente, en el tiempo t = 0 , todos los estados están en estado quiescente excepto la celda del extremo izquierdo (la general), que está activa. El objetivo es diseñar un conjunto de estados y una función de transición tales que, sin importar cuán larga sea la línea de celdas, exista un tiempo t tal que cada celda pase al estado de activación en el tiempo t , y tal que ninguna celda pertenezca al estado de activación antes del tiempo t .

La primera solución al FSSP fue encontrada por John McCarthy y Marvin Minsky y fue publicada en Sequential Machines por Moore . Su solución implica propagar dos ondas a lo largo de la línea de soldados: una onda rápida y una onda lenta que se mueve tres veces más lento. La onda rápida rebota en el otro extremo de la línea y se encuentra con la onda lenta en el centro. Las dos ondas luego se dividen en cuatro ondas, una onda rápida y una onda lenta que se mueven en cualquier dirección desde el centro, dividiendo efectivamente la línea en dos partes iguales. Este proceso continúa, subdividiendo la línea hasta que cada división tiene una longitud de 1. En este momento, todos los soldados disparan. Esta solución requiere 3 n unidades de tiempo para n soldados.

Eiichi Goto (1962) fue el primero en encontrar una solución que utiliza una cantidad mínima de tiempo (que es 2 n  − 2 unidades de tiempo para n soldados)  , pero su solución utilizaba miles de estados. Waksman (1966) la mejoró a 16 estados, y Balzer (1967) la mejoró aún más a ocho estados, al tiempo que afirmaba haber demostrado que no existe una solución de cuatro estados. Peter Sanders descubrió más tarde que el procedimiento de búsqueda de Balzer estaba incompleto, pero logró reafirmar el resultado de la no existencia de cuatro estados mediante un procedimiento de búsqueda corregido. La mejor solución conocida actualmente, que utiliza seis estados, fue presentada por Jacques Mazoyer (1987). Todavía se desconoce si existe una solución de cinco estados.

En las soluciones de tiempo mínimo, el general envía a la derecha las señales S ₁ ,  S ₂ ,  S ₃ , ...,  S _i a velocidades 1, 1/3, 1/7, ..., 1/(2 ^{i −1}  − 1)  . La señal S ₁ se refleja en el extremo derecho de la línea y se encuentra con la señal S _i (para i  ≥ 2 ) en la celda n /2 ^{i −1}  . Cuando S ₁ se refleja, también crea un nuevo general en el extremo derecho. Las señales S _i se construyen utilizando señales auxiliares, que se propagan a la izquierda. Cada segunda vez que una señal se mueve (a la derecha), envía una señal auxiliar a la izquierda. S ₁ se mueve por sí sola a la velocidad 1, mientras que cada una de las señales más lentas se mueve solo cuando recibe una señal auxiliar.

El problema de sincronización del pelotón de fusilamiento se ha generalizado a muchos otros tipos de autómatas celulares, incluidas las matrices de células de dimensiones superiores (Shinahr 1974). También se han considerado variantes del problema con diferentes condiciones iniciales (Kobayashi y Goldstein 2005).

Las soluciones al problema del pelotón de fusilamiento también pueden adaptarse a otros problemas. Por ejemplo, Patrick Fischer  (1965) diseñó un algoritmo de autómata celular para generar los números primos basándose en una solución anterior al problema de sincronización del pelotón de fusilamiento.

• Balzer, Robert (1967), "Una solución de tiempo mínimo de 8 estados para el problema de sincronización del pelotón de fusilamiento", Información y Control , 10 (1): 22–42, doi : 10.1016/S0019-9958(67)90032-0.
• Fischer, Patrick C. (1965), "Generación de números primos mediante una matriz iterativa unidimensional en tiempo real", Journal of the ACM , 12 (3): 388–394, doi : 10.1145/321281.321290.
• Goto, Eiichi (1962), Una solución de tiempo mínimo para el problema del pelotón de fusilamiento , notas del curso Dittoed para Matemáticas Aplicadas 298, Cambridge, MA: Harvard University, págs. 52–59Como lo cita Waksman (1966).
• Kobayashi, Kojiro; Goldstein, Darin (2005), "Sobre las formulaciones de problemas de sincronización de pelotones de fusilamiento", Computación no convencional (PDF) , Lecture Notes in Computer Science, vol. 3699, Springer-Verlag, págs. 157–168, doi :10.1007/11560319_15.
• Mazoyer, Jacques (1987), "Una solución de tiempo mínimo de seis estados para el problema de sincronización del pelotón de fusilamiento", Theoretical Computer Science , 50 (2): 183–238, doi :10.1016/0304-3975(87)90124-1.
• Moore, FR; Langdon, GG (1968), "Un problema generalizado de pelotón de fusilamiento", Información y Control , 12 (3): 212–220, doi :10.1016/S0019-9958(68)90309-4.
• Shinahr, Ilka (1974), "Problema de sincronización de pelotones de fusilamiento bidimensionales y tridimensionales", Información y Control , 24 (2): 163–180, doi :10.1016/S0019-9958(74)80055-0.
• Waksman, Abraham (1966), "Una solución óptima al problema de sincronización del pelotón de fusilamiento", Información y Control , 9 (1): 66–78, doi :10.1016/S0019-9958(66)90110-0.

• Weisstein, Eric W. "El problema del pelotón de fusilamiento". MathWorld .
• Una visualización y explicación de una de las soluciones.