3 ms·

For n large enough, this visual based solution would not suffice. Light based communication is the fastest on the universe but not instantaneous. Imagine there

For n large enough, this visual based solution would not suffice. Light based communication is the fastest on the universe but not instantaneous. Imagine there exists a line of soldiers, 96 million miles long,... -Or- Imagine there exist n datacenters which need to coordinate an action with nanosecond accuracy and are connected by fiber optic cable...

hamburglar 13y ago
I think one of the interesting aspects of the problem is that it illustrates just how much more complicated a mechanism needs to be if you aren't allowed to introduce some basic functionality like clock synchronization. We know the automata have clocks, so if they're actually allowed to count cycles to keep a concept of synchronized time, then the problem becomes very simple: a counter is started at 0 and sent from one end of the line to the other. When it reaches the other end of the line, the last node knows how long before the signal can get back to the beginning of the line and sends 2n back across as the time everyone will fire. Super simple solution in 2n time. That's not to say it's a stupid problem -- it's both fun and useful to consider what exactly you'd need to do if you had to solve a problem with the given constraints, because it helps you understand the cost of those constraints and whether all the extra algorithm complexity is worth it. Not to mention that if you're just going to punk out and say you'll use synchronized clocks, then you've got a whole new set of issues. :)
e12e 13y ago
Well, you're missing the point of my (somewhat sardonic) post: if it's an (actual) firing squad, the distances involved (along with the latency for a human to pull a trigger, the time to target for the bullet[1] etc) are so different in order of magnitude from the speed of light, that it might as well be instantaneous (note also that there's a subtle feature in reflecting off the wall, as for a "sane" number of soldiers, it is possible to position them at an equal distance from the "signal spot" on the wall (and presumably the target[2] of the firing squad). It's hard to imagine a system made up of (human) soldiers that give better (temporal) accuracy than this, by using a counter and relayed messaging. I do of course realize that it's not the scenario that is problem to be solved, but the communication (and computation?) model of which it is supposed to be an example. Still think it can be useful to solve the (stated) problem, rather than trying to make the perceived model fit the actual problem -- when that model clearly has surplus complexity and/or artificial constraints. [1] or with powerful laser weapons, time-to-death after "impact"? ;-) [2] Now, assuming a single target might be a bad assumption. What if we want to kill all our intellectuals at once? [edit: Almost forgot - another reason why a visual cue might be good in this case, is that it seems safe to assume that each soldier will aim at the target, presumably by some form of light-guidiance, so a visual cue relies on constraints already part of the system]

hamburglar 13y ago

I think one of the interesting aspects of the problem is that it illustrates just how much more complicated a mechanism needs to be if you aren't allowed to introduce some basic functionality like clock synchronization. We know the automata have clocks, so if they're actually allowed to count cycles to keep a concept of synchronized time, then the problem becomes very simple: a counter is started at 0 and sent from one end of the line to the other. When it reaches the other end of the line, the last node knows how long before the signal can get back to the beginning of the line and sends 2n back across as the time everyone will fire. Super simple solution in 2n time. That's not to say it's a stupid problem -- it's both fun and useful to consider what exactly you'd need to do if you had to solve a problem with the given constraints, because it helps you understand the cost of those constraints and whether all the extra algorithm complexity is worth it. Not to mention that if you're just going to punk out and say you'll use synchronized clocks, then you've got a whole new set of issues. :)

e12e 13y ago

Well, you're missing the point of my (somewhat sardonic) post: if it's an (actual) firing squad, the distances involved (along with the latency for a human to pull a trigger, the time to target for the bullet[1] etc) are so different in order of magnitude from the speed of light, that it might as well be instantaneous (note also that there's a subtle feature in reflecting off the wall, as for a "sane" number of soldiers, it is possible to position them at an equal distance from the "signal spot" on the wall (and presumably the target[2] of the firing squad). It's hard to imagine a system made up of (human) soldiers that give better (temporal) accuracy than this, by using a counter and relayed messaging. I do of course realize that it's not the scenario that is problem to be solved, but the communication (and computation?) model of which it is supposed to be an example. Still think it can be useful to solve the (stated) problem, rather than trying to make the perceived model fit the actual problem -- when that model clearly has surplus complexity and/or artificial constraints. [1] or with powerful laser weapons, time-to-death after "impact"? ;-) [2] Now, assuming a single target might be a bad assumption. What if we want to kill all our intellectuals at once? [edit: Almost forgot - another reason why a visual cue might be good in this case, is that it seems safe to assume that each soldier will aim at the target, presumably by some form of light-guidiance, so a visual cue relies on constraints already part of the system]