News for hackers. Stuff that matters.
Re:The Firing Squad Problem by e12e on Friday February 07, 2014 @09:48AM (#7196439)
It would a appear a visual cue by the target would be superior... propagates to all soldiers at the speed of light, assuming normal rifles (range etc), all soldiers are likely to receive the signal at what for practical purposes are the same time -- the signal might be created by way of a mirror reflecting on the wall, so doesn't require any special technology, and can be projected almost instantaneously ... sadly such a practical solution makes for very a trivial fsm...
Re:The Firing Squad Problem by barrkel on Friday February 07, 2014 @09:53AM (#7196469)
Of course, that's not the point. The firing squad metaphor is just to describe the problem of coordinating a synchronous activity given a linear non-zero-time peer to peer communication mechanism.
Re:The Firing Squad Problem by RyanZAG on Friday February 07, 2014 @10:56AM (#7196818)
Not necesserily, it's still good to realize that there would be a more efficient solution. This applies in the real world too: you might be working out the best way to notify servers of an event through P2P, but it may be better to simply notify those servers in some broadcast pattern. (The idea of a mirror to notify all soldiers at once would be a broadcast pattern)
Re:The Firing Squad Problem by judk on Friday February 07, 2014 @11:29AM (#7197058)
Networks do not have the same physics/geometry as the vacuum of space, latency cannot be assumed to be 0.
Re:The Firing Squad Problem by jerf on Friday February 07, 2014 @11:39AM (#7197132)
The reason why latency in a network can not be zero is the geometry of space. In the real universe the only possible zero-latency (macroscopic) connection is the one that travels 0 distance.
Re:The Firing Squad Problem by pfarrell on Friday February 07, 2014 @11:39AM (#7197134)
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...

Re:The Firing Squad Problem by hamburglar on Friday February 07, 2014 @03:17PM (#7198454)
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. :)

Re:The Firing Squad Problem by e12e on Friday February 07, 2014 @04:56PM (#7199026)
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]