This is an interesting theory problem, but it might be clearer to talk about shooters at a firing range, separated by partitions such that they can each only talk to their neighbors. The barriers eliminates the trivial solution of the shout: "Fire on the count of 3!" that common sense would provide.
The simplest solution would be to establish a clock, because with a clock you can say "Fire at 1pm exactly!". But even this is interesting because it requires shooters to know where they are in the line in order to take into account any signal propogation delay. If each person takes 1s to repeat a message that they hear, then it takes n seconds to go down the line, and each shooter must know how to compensate for that delay. E.g. the first shooter hears "it's noon", the next shooter hears "it's noon" but knows that he's 1s away from the source, and can calculate that the time is actually 12:01, the next shooter knows it's 12:02 etc. They could synchronize clocks, specify a time "shoot at 1pm!" and get the job done.
But what if we take away their clocks? This is where my intuition fails me, because I don't see how the problem can be solved without clocks. If you don't have clocks, you need to somehow get a signal to every shooter simultaneously, which I think is theoretically impossible, since without a clock the shooter cannot execute instructions on their own.
Which probably means I don't fully understand the scenario :)
Suppose you don't have absolute clocks (so you don't know when it's 1pm) but you do have the ability to count time steps. Then you can solve the problem by "pinging" down to the end of the line and back, counting along the way. The first soldier sees the returned ping and fires immediately. The second soldier (who knows he's second, since when the ping went out, the message was only at "1") fires one interval after the returned ping passes by him, so that's the same time as the first soldier does it. Likewise, the third soldier fires two intervals after hearing the returned ping.
Alas, in this scenario we don't even have the ability to count, since we have a limited number of internal states to use to store numbers. So the really clever part is to encode additional information in the flow of additional messages. For example, to find the middle soldier, we can send out two pings, one three times faster than the other. They meet when the slower ping has gone through half the soldiers, and the faster one has gone all the way down the line, and back through half the soldiers (it's three times faster). Additional pings of different speeds can bounce back and forth in order to divide the interval still further - effectively, recursing into narrower sub-lines. Everything is set up so that all of the sub-lines reach their minimal size - one soldier - at the same time, at which point they know it's time to fire. The "recursion" means that the number of states can be bounded, as there are only a few different "modes" for the soldiers to operate in, regardless of the length of the sub-line involved.
I think the purpose is to solve the scenario where each node has a perfect internal clock, but no external reference clock. A rough solution is to initiate a count from the origin, starting from 0. Each node hears the previous neighbor's count, increments it by 1 and sounds off. When the end node is reached, it knows how far the signal propagated. At this point a reverse count is initiated, terminating in 0 at the origin. Each node along the way back hears the adjacent node begin its countdown, and starts its own countdown from its relative position. The return signal reaches the origin node just as the remainder of the nodes reach 0, and all node execute simultaneously on 0 (with appropriate modification for any fencepost problems).
No external reference clock is required, and assuming each node counts at exactly the same rate, all nodes act in unison.
The simplest solution would be to establish a clock, because with a clock you can say "Fire at 1pm exactly!". But even this is interesting because it requires shooters to know where they are in the line in order to take into account any signal propogation delay. If each person takes 1s to repeat a message that they hear, then it takes n seconds to go down the line, and each shooter must know how to compensate for that delay. E.g. the first shooter hears "it's noon", the next shooter hears "it's noon" but knows that he's 1s away from the source, and can calculate that the time is actually 12:01, the next shooter knows it's 12:02 etc. They could synchronize clocks, specify a time "shoot at 1pm!" and get the job done.
But what if we take away their clocks? This is where my intuition fails me, because I don't see how the problem can be solved without clocks. If you don't have clocks, you need to somehow get a signal to every shooter simultaneously, which I think is theoretically impossible, since without a clock the shooter cannot execute instructions on their own.
Which probably means I don't fully understand the scenario :)