15
$\begingroup$

When I was a student, I saw a problem in a digital systems/logic design textbook, about N soldiers standing in a row, and want to shoot at the same time. A more difficult version of the problem was that the soldiers stand in a general network instead of a row. I am sure this is a classical problem, but I cannot remember its name. Can you remind me?

$\endgroup$
21
$\begingroup$

The problem is known as Firing squad synchronization problem. The problem itself, is strictly related to finite state automata. Here, each soldier is a finite automaton; you know that the next state of each soldier depends on its current state and the current states of its two neighbors (except for the first and last soldier). The first soldier in this setting can be though of as the soldiers general who is in charge of starting the attack. The last soldier knows it is the last one. No global communication is available; however, a global clock can be used to synchronize the state transitions of the soldiers. The problem require designing a soldier automaton whose goal is for all soldiers to enter the "SHOOT" state on exactly the same clock tick. By the way, the problem can be solved in $\Theta(n)$ time for $n$ soldiers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.