There is a group of N soldiers arranged in a straight line, standing side by side. Soldier number 1 is at the extreme left and soldier "N" is at the extreme right. Each soldier has a rifle that can be fired only once, a primitive timer, understands a finite list of commands, and can exist in a finite number of states, like a finite state machine.

Each soldier has the ability to communicate only with the two adjacent soldiers, and has no means of communication with more distant soldiers. The i-th soldier can not see or hear any signals given by the (i+2)th soldier, for example. There are no radios, cell phones, or megaphones.

Your mission as the commander is to devise an algorithm by which all soldiers fire their weapons simultaneously. Soldiers 1 and N are aware of the fact that they are "different" in that they each have only one neighbor. Other than that, however, the soldiers are initially all identical. The algorithm has to work for any value of N>2.

The primitive timers are synchronized and tick off once a second. Once a soldier receives new information, the earliest he can respond in any way is on the next tick of the clock. (I would say he/she, except that they are all identical). A soldier can give a signal to each neighbor simultaneously, based on the information he received one tick earlier. Whenever a soldier's state changes, his neighbors are aware of this one tick later. At time=0, soldier 1 is given the command to start the firing procedure

1. Devise an algorithm that results in all N soldiers firing simultaneously
2. As a function of N, how many clock ticks does this take?

1. The 1st soldier is given the number 0 at time t = 0.
2. At time t = 1, he transmits the data incremented by 1 to the next
soldier. Namely, the data 1 is transmitted to the soldier to the left
of him.
3. Similarly, at time 't', soldier number 't' transmits data 't' to
the 't+1'th solder, who receives it instantaneously.
4. When the data finally propogates to the Nth soldier, he at the
'n+1'th clock tick will transmit the data as it is to the to the
person to his right. So, the Nth soldier receives data 'n-1'. He will
transmit data 'n-1' ONLY.
5. the remaining soldiers will transmit data decremented by 1 to their
right neighbors at the next clock cycles after they receive the
data. thus, after N more clock cycles, the 1st soldier will get the
data 1.
6. Also, at each clock cycle, each soldier also decrements his number
that he got the 2nd time around. When this count goes to 0, the 1st
soldiers' count will also have gone to 0, when all of them should
fire.

This whole procedure takes exactly (2n+1) clock ticks.

Posted by dhruv on 2004-08-25 12:52:14