Todos os soldados devem atirar ao mesmo tempo

Quando eu era estudante, vi um problema em um livro didático de sistemas digitais / de lógica, sobre N soldados seguidos e quero atirar ao mesmo tempo. Uma versão mais difícil do problema era que os soldados estavam em uma rede geral, em vez de uma fila. Estou certo de que este é um problema clássico, mas não consigo me lembrar do nome. Você pode me lembrar?

O problema é conhecido como problema de sincronização do esquadrão de tiro . O problema em si está estritamente relacionado aos autômatos de estados finitos. Aqui, cada soldado é um autômato finito; você sabe que o próximo estado de cada soldado depende do estado atual e dos estados atuais de seus dois vizinhos (exceto o primeiro e o último soldado). O primeiro soldado nesse cenário pode ser considerado o general dos soldados encarregado de iniciar o ataque. O último soldado sabe que é o último. Nenhuma comunicação global está disponível; no entanto, um relógio global pode ser usado para sincronizar as transições de estado dos soldados. O problema exige a criação de um autômato para soldados, cujo objetivo é que todos os soldados entrem no estado "DISPARAR" exatamente no mesmo relógio. A propósito, o problema pode ser resolvido em$\Theta(n)$ hora de $n$ soldados