News for hackers. Stuff that matters.
Re:The Firing Squad Problem by judk on Friday February 07, 2014 @11:35AM (#7197092)
This is one of those problems where the illustration is severely misleading from the intended theoretical problem. The problem assumes that all nodes share a synchronized time step, but do not have a clock, and only communicate by trading notes, which is an incredibly awkward assumption. The problem works better without the title and metaphor.

For example, a much better metaphor would be schoolchildren passing notes among neighbors every time the teacher turns their back, coordinating a simultaneous outburst.

Re:The Firing Squad Problem by jgrahamc on Friday February 07, 2014 @12:13PM (#7197361)
In Hillis' book the clock is provided by a military drummer beating time on a drum.
Re:The Firing Squad Problem by thaumasiotes on Saturday February 08, 2014 @07:35AM (#7201030)
That's an unfortunate metaphor; it completely spoils the problem. Just have the drummer give the signal to fire, and all the soldiers will hear him simultaneously.
Re:The Firing Squad Problem by chmike on Saturday February 08, 2014 @01:11AM (#7200447)
I still don't get it because for me the minimal time is n. The general pass a note with the value n to the firts squad, which decrease it by one and pass it to the next squad, etc. If passing the note to the next squad is performed at each clock beat and each suqad decrements the value he got, then they will all reach 0 at the same time. I guess I'm missing some constrains because I don't see why I don't get 2n-2 as minimal time.
Re:The Firing Squad Problem by gus_massa on Saturday February 08, 2014 @07:17AM (#7201006)
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.

Re:The Firing Squad Problem by chmike on Saturday February 08, 2014 @07:48AM (#7201051)
Thanks for clarifying things. Looking at the solution on wikipedia I also understood what constrain I was missing.