The Firing Squad Problem(www-cs-faculty.stanford.edu)
www-cs-faculty.stanford.edu
The Firing Squad Problem
http://www-cs-faculty.stanford.edu/~eroberts/courses/soco/projects/2004-05/automata-theory/problem.html
67 comments
When you keep presenting a supposedly unsolvable problem to people who don't know it, then you might get lucky. George Dantzig was one such person. He arrived late to class, saw some problems on the board, assumed they were homework, and solved them. He wasn't constrained by the common thought that these were "unsolvable".
They were not "unsolvable", they were simply not solved yet (at the time Dantzig saw them on the blackboard).
http://www.snopes.com/college/homework/unsolvable.asp
http://www.snopes.com/college/homework/unsolvable.asp
Did you read the comment? He said they were considered unsolvable at the time, not that they were unsolvable. Of course they're solvable - they were solved.
That is precisely my point. They were not considered "unsolvable" (i.e. impossible to solve), they were considered "unsolved" (i.e. not solved yet) and were presented as such. Do you really need me to explain distinctions in meaning here?
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.
For example, a much better metaphor would be schoolchildren passing notes among neighbors every time the teacher turns their back, coordinating a simultaneous outburst.
In Hillis' book the clock is provided by a military drummer beating time on a drum.
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.
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.
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.
Thanks for clarifying things. Looking at the solution on wikipedia I also understood what constrain I was missing.
A few years ago, a friend asked me if I had any interesting problems he and a coworker of his could work on for fun. One of the problems I gave him was this (although I presented it as a state machine problem, not a firing square problem).
In a burst of over-enthusiasm, I also quickly hacked together a simple state machine simulator that he and his coworker could use to test their proposed solution(s).
The problem specification, state machine simulator, and documentation are available here: https://github.com/tzs/problems-state-machine-sync
I told them I would consider it solved if they could describe the algorithm. They did not need to actually specify fully working state machines that dealt with all the details.
Much to my surprise, especially considering that my friend had not studied computer science beyond what was given in a high school programming class, not only did they solve the problem in a few days, they produced fully working state machines.
Another puzzle I gave them consisted of several images that show the tracks of a bicycle. One of the wheels is leaving a red track and one a blue track (color assignment was random for each image). Their task: determine in each image whether the bike was traveling left to right or right to left. Here are the images: http://imgur.com/a/hv0b0
It was also randomly determined for each image whether to draw the front wheel track first or rear wheel track first, so you cannot deduce anything from which track appears to be on top when they cross.
In a burst of over-enthusiasm, I also quickly hacked together a simple state machine simulator that he and his coworker could use to test their proposed solution(s).
The problem specification, state machine simulator, and documentation are available here: https://github.com/tzs/problems-state-machine-sync
I told them I would consider it solved if they could describe the algorithm. They did not need to actually specify fully working state machines that dealt with all the details.
Much to my surprise, especially considering that my friend had not studied computer science beyond what was given in a high school programming class, not only did they solve the problem in a few days, they produced fully working state machines.
Another puzzle I gave them consisted of several images that show the tracks of a bicycle. One of the wheels is leaving a red track and one a blue track (color assignment was random for each image). Their task: determine in each image whether the bike was traveling left to right or right to left. Here are the images: http://imgur.com/a/hv0b0
It was also randomly determined for each image whether to draw the front wheel track first or rear wheel track first, so you cannot deduce anything from which track appears to be on top when they cross.
Ok. I'm stumped. Could you give me a hint
If you want a hint for the firing squad, start out by limiting the number of participants to powers of two, and think recursively.
If you want a hint for the bicycle problem, think about tangents.
If you want a hint for the bicycle problem, think about tangents.
Anyone who drives a bycicle knows that the rear wheel follows a smooth path compared to the front wheel. So this image is easy. I guess there might be more tricky images. A straight line for instance ;)
This is an interesting theory problem, but it might be clearer to talk about shooters at a firing range, separated by partitions such that they can each only talk to their neighbors. The barriers eliminates the trivial solution of the shout: "Fire on the count of 3!" that common sense would provide.
The simplest solution would be to establish a clock, because with a clock you can say "Fire at 1pm exactly!". But even this is interesting because it requires shooters to know where they are in the line in order to take into account any signal propogation delay. If each person takes 1s to repeat a message that they hear, then it takes n seconds to go down the line, and each shooter must know how to compensate for that delay. E.g. the first shooter hears "it's noon", the next shooter hears "it's noon" but knows that he's 1s away from the source, and can calculate that the time is actually 12:01, the next shooter knows it's 12:02 etc. They could synchronize clocks, specify a time "shoot at 1pm!" and get the job done.
But what if we take away their clocks? This is where my intuition fails me, because I don't see how the problem can be solved without clocks. If you don't have clocks, you need to somehow get a signal to every shooter simultaneously, which I think is theoretically impossible, since without a clock the shooter cannot execute instructions on their own.
Which probably means I don't fully understand the scenario :)
The simplest solution would be to establish a clock, because with a clock you can say "Fire at 1pm exactly!". But even this is interesting because it requires shooters to know where they are in the line in order to take into account any signal propogation delay. If each person takes 1s to repeat a message that they hear, then it takes n seconds to go down the line, and each shooter must know how to compensate for that delay. E.g. the first shooter hears "it's noon", the next shooter hears "it's noon" but knows that he's 1s away from the source, and can calculate that the time is actually 12:01, the next shooter knows it's 12:02 etc. They could synchronize clocks, specify a time "shoot at 1pm!" and get the job done.
But what if we take away their clocks? This is where my intuition fails me, because I don't see how the problem can be solved without clocks. If you don't have clocks, you need to somehow get a signal to every shooter simultaneously, which I think is theoretically impossible, since without a clock the shooter cannot execute instructions on their own.
Which probably means I don't fully understand the scenario :)
Suppose you don't have absolute clocks (so you don't know when it's 1pm) but you do have the ability to count time steps. Then you can solve the problem by "pinging" down to the end of the line and back, counting along the way. The first soldier sees the returned ping and fires immediately. The second soldier (who knows he's second, since when the ping went out, the message was only at "1") fires one interval after the returned ping passes by him, so that's the same time as the first soldier does it. Likewise, the third soldier fires two intervals after hearing the returned ping.
Alas, in this scenario we don't even have the ability to count, since we have a limited number of internal states to use to store numbers. So the really clever part is to encode additional information in the flow of additional messages. For example, to find the middle soldier, we can send out two pings, one three times faster than the other. They meet when the slower ping has gone through half the soldiers, and the faster one has gone all the way down the line, and back through half the soldiers (it's three times faster). Additional pings of different speeds can bounce back and forth in order to divide the interval still further - effectively, recursing into narrower sub-lines. Everything is set up so that all of the sub-lines reach their minimal size - one soldier - at the same time, at which point they know it's time to fire. The "recursion" means that the number of states can be bounded, as there are only a few different "modes" for the soldiers to operate in, regardless of the length of the sub-line involved.
Alas, in this scenario we don't even have the ability to count, since we have a limited number of internal states to use to store numbers. So the really clever part is to encode additional information in the flow of additional messages. For example, to find the middle soldier, we can send out two pings, one three times faster than the other. They meet when the slower ping has gone through half the soldiers, and the faster one has gone all the way down the line, and back through half the soldiers (it's three times faster). Additional pings of different speeds can bounce back and forth in order to divide the interval still further - effectively, recursing into narrower sub-lines. Everything is set up so that all of the sub-lines reach their minimal size - one soldier - at the same time, at which point they know it's time to fire. The "recursion" means that the number of states can be bounded, as there are only a few different "modes" for the soldiers to operate in, regardless of the length of the sub-line involved.
I think the purpose is to solve the scenario where each node has a perfect internal clock, but no external reference clock. A rough solution is to initiate a count from the origin, starting from 0. Each node hears the previous neighbor's count, increments it by 1 and sounds off. When the end node is reached, it knows how far the signal propagated. At this point a reverse count is initiated, terminating in 0 at the origin. Each node along the way back hears the adjacent node begin its countdown, and starts its own countdown from its relative position. The return signal reaches the origin node just as the remainder of the nodes reach 0, and all node execute simultaneously on 0 (with appropriate modification for any fencepost problems).
No external reference clock is required, and assuming each node counts at exactly the same rate, all nodes act in unison.
No external reference clock is required, and assuming each node counts at exactly the same rate, all nodes act in unison.
the problem is with no clocks, and is possible.
you also can't count the soldiers because you don't have unlimited memory (states), so you might run out of memory (states) to count in.
you also can't count the soldiers because you don't have unlimited memory (states), so you might run out of memory (states) to count in.
you seem to understand the scenario fine, there's just a solution you missed. it's not obvious.
> At every count, each soldier looks at their neighbors, considers what they themselves were already doing, and decides what to do next, completely according to what they see.
Anyone else think this is an incredibly ugly problem statement? It's like they thought firing squads were cool and tried to shoehorn the problem into it any way they could.
Anyone else think this is an incredibly ugly problem statement? It's like they thought firing squads were cool and tried to shoehorn the problem into it any way they could.
Feynman gave the firing squad problem in his lectures on computation, so it can't be a modern shoehorn.
Its interesting to see people get stuck on the "Firing Squad" aspect of it. There is an insight there about communicating through metaphor effectively.
As a synchronization problem this one was a lot of fun, I too encountered it in the Feynman book and later used variants of it in interviewing folks for Google. Basically once you get into the realm of distribution the ability to get large groups of programs working together introduces a lot of complexity into an otherwise straightforward problem space.
An interesting variant is that you create a line of students. The teacher asks them to form a line at the door with the tallest student in front and the shortest in the back. How can any given student know its there turn to join the line at the door?
As a synchronization problem this one was a lot of fun, I too encountered it in the Feynman book and later used variants of it in interviewing folks for Google. Basically once you get into the realm of distribution the ability to get large groups of programs working together introduces a lot of complexity into an otherwise straightforward problem space.
An interesting variant is that you create a line of students. The teacher asks them to form a line at the door with the tallest student in front and the shortest in the back. How can any given student know its there turn to join the line at the door?
I'm assuming that when it says a "fixed number of states," it means that the number of states can't be tied to the number of soldiers in the line? (e.g., a five state solution would have to work for any number of soliders)
Realized my question may have come across as rhetorical, but I really am looking for clarification on the rules!
Yes you have a constant number of states at your disposal. Otherwise, there is a trivial solution that takes n or so time, matching the theoretical lower bound (imposed by the "speed of light" for information propagation in this kind of automaton), rendering the problem thoroughly uninteresting.
>Assuming that there is a fixed number of states, regardless of how many soldiers there are in the line...
I think that this line may be your best indication. How exactly should you interpret this sentence? I don't know!
I think that this line may be your best indication. How exactly should you interpret this sentence? I don't know!
I came here hoping to encounter a rousing debate on why we should use the firing squad for all executions, but this is much more interesting.
That does say something about how political HN has become.
This is a nice one to solve for yourself. The two-dimensional (and higher) problems are still research material.
I assume that it is research material if you are trying to find the solution with the minimal number of states or the fastest sync time or something like that?
The two (or higher) dimensional problem if you aren't requiring some kind of optimal or minimal solution is a trivial extension of the one dimensional problem. E.g., for two dimensions, you essentially do the one dimensional solution along the top row to sync up all the elements there, and then they simultaneously start the one dimensional solution on the columns.
The two (or higher) dimensional problem if you aren't requiring some kind of optimal or minimal solution is a trivial extension of the one dimensional problem. E.g., for two dimensions, you essentially do the one dimensional solution along the top row to sync up all the elements there, and then they simultaneously start the one dimensional solution on the columns.
Yes, I was talking about solutions with special properties, like eg being optimal or minimal in some sense.
It's curious - in biology here we see similar problems solved in 3D, but it's not always clear how it's solved. Take the first few divisions during gastrulation [1] and notice that every cell divides synchronously for the first few divisions even though no single signal should be able to propagate from end to end that fast. And in other 3D environments like the sphere of cells in breast tissue you have similar synchronies that must be achieved in an environment that does not allow for rapid signal exchange (such an environment [2]).
[1] https://www.youtube.com/watch?v=4La78WtK4n8 [2] https://www.youtube.com/watch?v=3W10ywd_s6w
[1] https://www.youtube.com/watch?v=4La78WtK4n8 [2] https://www.youtube.com/watch?v=3W10ywd_s6w
Turn on a light above the target's head. Shoot on target. Demote general for wasting everyone time.
Then the person who is the closest to the light will know that he is the one who killed the individual.
Arrange the soldiers in an arc (< 180 degrees, hopefully) around the target, rather than a line. Now each soldier is exactly the same distance from the target, and will see the light turn on at exactly the same time.
> Then the person who is the closest to the light will know that he is the one who killed the individual.
Apart from the possibility of arranging those firing in an arch (and providing a random selection with blanks[1) -- how on earth would a "soldier" know that? Anyone close enough to see the light above the curvature of the earth/within rifle range would effectively see the light at the same time (just based on the latency of the nervous system)...
[1] It seems to me that it would be much easier to tell if you'd fired a blank -- as the recoil would feel different?
Apart from the possibility of arranging those firing in an arch (and providing a random selection with blanks[1) -- how on earth would a "soldier" know that? Anyone close enough to see the light above the curvature of the earth/within rifle range would effectively see the light at the same time (just based on the latency of the nervous system)...
[1] It seems to me that it would be much easier to tell if you'd fired a blank -- as the recoil would feel different?
Also you're assuming perfect response times which is BS.
No, the way firing squads work is that a randomly-chosen member fires a blank. No one can know for certain if they delivered a lethal round.
While you may not know if your rifle has a blank, you'll definitely know if your rifle fired a blank due to the different force in recoil because you're accelerating the mass of gunpowder+lead vs gunpowder alone.
Not sure how true that is. How much recoil force is contributed by the bullet versus the gas that propels it?
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...
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.
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)
Networks do not have the same physics/geometry as the vacuum of space, latency cannot be assumed to be 0.
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.
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...
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...
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. :)
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. :)
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]
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]
It is a bit distracting to place a theoretical problem in an unnecessarily morbid context. We don't have to be dark to be cool. How about a "cheerleader coordination problem" or the "Sing Happy Birthday problem"?
If you're a computer scientist/engineer, and the first thought that goes through your mind when you read the description of a problem is "wow, that's offensive" or "wow, why describe the problem like that"....
How does the context of the problem statement have any bearing on a solution? outside of certain moral dilemmas in extreme instances, they don't.
Who cares if the problem was framed in a "morbid context"? it's done, it's over, how does quibbling over the "context" solve anything? It doesn't. It's a complete waste of time and energy, and solutions are hard enough to come by for easy problems, let alone difficult ones, we should be expending our energy on solutions, not whining about terminology, or context.
How does the context of the problem statement have any bearing on a solution? outside of certain moral dilemmas in extreme instances, they don't.
Who cares if the problem was framed in a "morbid context"? it's done, it's over, how does quibbling over the "context" solve anything? It doesn't. It's a complete waste of time and energy, and solutions are hard enough to come by for easy problems, let alone difficult ones, we should be expending our energy on solutions, not whining about terminology, or context.
I guess you could go back to 1957 and lecture John Myhill on this, or we could all just ignore the academic priority and rename the problem as you like and after you. For some problems with obvious racist or sexist "jokes" we do need to rename (and the original "jokesters" don't really deserve or respect for their original naming). But is this one really such a problem?
"It should be noted that no ethically-trained software engineer would ever consent to write a DestroyBaghdad procedure. Basic professional ethics would instead require him to write a DestroyCity procedure, to which Baghdad could be given as a parameter." (don't know the source of the quote)
In fact, "sing happy birthday problem" sounds offensive to me -- this is an incredibly stupid and annoying song. No reason to promote it. Sure firing squad is about killing people, but we already have laws regulating that and in most countries you won't see a sudden mob of gunmen lynching somebody in public places. I have seen no laws about subjecting innocent bystanders in say a restaurant to this horrible "song". I don't even mention the the main victim, who has to sit there with strained smile and suffer through that atrocious repetitive and dumb "singing"...
The jarring context may serve valid instructional purposes:
The vividness improves memorability.
Discarding colorful but logically-inessential details from a problem description is a useful skill that can benefit from practice.
The portrayal of life-or-death stakes draws interest by making the solution seem more urgent, and helpfully alludes to the real stakes, in commercial or military engineering, that are faced by those who are adept at such work.
The vividness improves memorability.
Discarding colorful but logically-inessential details from a problem description is a useful skill that can benefit from practice.
The portrayal of life-or-death stakes draws interest by making the solution seem more urgent, and helpfully alludes to the real stakes, in commercial or military engineering, that are faced by those who are adept at such work.
"Happy Birthday" is a copyrighted work in the United States. I hope you have all the correct licenses in place.
But the context captures the importance of the problem to computer science clear. Singing happy birthday in unison is not a particularly important problem :)
Killing others is?
The psychology of people on a firing squad is a real problem. To address this in real life, usually there is a "blank" round randomly placed into one of the guns. This tiny probability helps them, because they can tell themselves that maybe they didn't really participate in the killing. But they all have to fire at once, otherwise whoever fires first will be more worried that they fired the killing shot.
Why should they name the problem in a way you'd prefer instead of a way they'd prefer?
Why not with guns that put out happy birthday / surprise flags? Like in cartoons!
Those cartoons are now considered offensive.
Only by those who have nothing better to do than get "offended" by cartoons.
[deleted]
So I gave up and continued reading. Then somewhere in the 4th or 5th Chapter he says something like: Oh I hope you had fun with the Firing Squad Problem, I still work on it from time to time and hope to come up with a solution myself one day.
Facepalm.
Edit: Here is a link to the book, its enjoyable for experts and laymen alike. http://www.amazon.com/Feynman-Lectures-On-Computation-Richar...