The Firing Squad Problem
www-cs-faculty.stanford.edu
www-cs-faculty.stanford.edu
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...
For example, a much better metaphor would be schoolchildren passing notes among neighbors every time the teacher turns their back, coordinating a simultaneous outburst.
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.
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.
If you want a hint for the bicycle problem, think about tangents.
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 :)
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.
No external reference clock is required, and assuming each node counts at exactly the same rate, all nodes act in unison.
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.
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.
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 think that this line may be your best indication. How exactly should you interpret this sentence? I don't know!
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.
[1] https://www.youtube.com/watch?v=4La78WtK4n8 [2] https://www.youtube.com/watch?v=3W10ywd_s6w
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?
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...
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. :)
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]
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.
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.