Todos los soldados deben disparar al mismo tiempo.

Cuando era estudiante, vi un problema en un libro de texto de diseño de sistemas / lógica digital, sobre N soldados parados en una fila, y quería disparar al mismo tiempo. Una versión más difícil del problema fue que los soldados se paran en una red general en lugar de una fila. Estoy seguro de que este es un problema clásico, pero no recuerdo su nombre. ¿Puedes tu recordarme?

El problema se conoce como problema de sincronización del escuadrón de fusilamiento . El problema en sí mismo está estrictamente relacionado con los autómatas de estado finito.. Aquí, cada soldado es un autómata finito; sabes que el siguiente estado de cada soldado depende de su estado actual y de los estados actuales de sus dos vecinos (excepto el primero y el último soldado). El primer soldado en este entorno puede considerarse como el general de soldados que está a cargo de comenzar el ataque. El último soldado sabe que es el último. No hay comunicación global disponible; sin embargo, se puede usar un reloj global para sincronizar las transiciones de estado de los soldados. El problema requiere el diseño de un autómata soldado cuyo objetivo es que todos los soldados entren en el estado "DISPARO" exactamente en el mismo tic del reloj. Por cierto, el problema se puede resolver en tiempo para n soldados.$\Theta(n)$$n$