Ken's POTW


Firing Squad
N soldiers stand in a row, shoulder to shoulder, facing the same direction.

The first soldier on the right is the drummer. Every second, the drummer gives a beat, heard by all the soldiers. On that beat, the soldiers modify their state based solely upon their current state and the state of their nearest neighbors. (Perhaps the state of a soldier is noticeable by their posture, stance, or some other visual clue.)

Currently, all the soldiers are in a quiescent state, awaiting orders.

The first soldier on the left is the General. The General changes his state to give the command "Fire!" Each second, the command is passed on, perhaps in both directions as needed. Some time later, all N soldiers fire at the same time.
  1. How could this occur? I'm only looking for a theoretical answer here. What would the algorithm be to get them all to fire at the same time?
  2. Each soldier is an agent, with its own rules for state-changes. Obviously, the General and the drummer will have special rules, since they have only one neighbor, but the rest should share the same set of rules. Can you determine a rule set (a state machine) for the General, drummer, and soldiers? How many states are needed? Can the state machines work for any N?

Source: Homework problem in a CompSci Agents course at Stanford University, Fall, 1991.


Solution
Mail to Ken