IIUC the idea is that they want a fixed number of states, that doesn’t depend of n.
Another idea is that nobody knows the exact value of n, so the first task of the soldiers is to count themselves. Then the idea is that a signal propagates form one end of the line to the other end and back, and the time is ~2n. Using two signals that propagate with different velocities they can “count” with a finite number of states.
For example, see the fist graphic “Anonymous, 3n time, 160 soldiers, 13 states” in http://www-cs-faculty.stanford.edu/~eroberts/courses/soco/pr... . They first find the middle of the line, and hen they continue doing binary partitions until all the partitions have length 1, and then they fire. The final step is local, each one has to check that they local partition has length 1 and the nearby partitions have length 1, but the binary split is responsible for making all the partitions of roughly the same size.
Another idea is that nobody knows the exact value of n, so the first task of the soldiers is to count themselves. Then the idea is that a signal propagates form one end of the line to the other end and back, and the time is ~2n. Using two signals that propagate with different velocities they can “count” with a finite number of states.
For example, see the fist graphic “Anonymous, 3n time, 160 soldiers, 13 states” in http://www-cs-faculty.stanford.edu/~eroberts/courses/soco/pr... . They first find the middle of the line, and hen they continue doing binary partitions until all the partitions have length 1, and then they fire. The final step is local, each one has to check that they local partition has length 1 and the nearby partitions have length 1, but the binary split is responsible for making all the partitions of roughly the same size.