5 ms·
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 sy
by judk 13y ago
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.
- jgrahamc 13y agoIn Hillis' book the clock is provided by a military drummer beating time on a drum.
- thaumasiotes 13y agoThat'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.
- chmike 13y agoI 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.
- gus_massa 13y agoIIUC 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/projects/2004-05/automata-theory/problem.html#comparison 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.
- chmike 13y agoThanks for clarifying things. Looking at the solution on wikipedia I also understood what constrain I was missing.