Wednesday, March 11, 2009 ... Deutsch/Español/Related posts from blogosphere

Firing squad synchronization problem

Back in 1992, when we came to the college as freshmen, my roommates majoring in computer science told me about a homework they were asked to solve. On Monday, I found it was called the firing squad synchronization problem and its history goes back to 1957 (although the solution was only published in 1962).



You have a sequence of P soldiers. Each of them is doing something - adopting one of a finite, fixed, P-independent number of states - at each unit of time. However, their state at some moment can only depend on their state and their neighbors in the previous moment of time. Consequently, signals can only propagate by a maximum speed, the "speed of light", or more slowly.

The task is to design the soldiers so that they will "fire" simultaneously some time after the general - the soldier at the left end - gives them the signal. So I solved it (they didn't; and my time needed to solve it was surely closer to 5 minutes than 5 years that was apparently needed historically - but to bound my boasting a little bit, let's admit that they didn't have good enough computers at that time). Here's a Mathematica 7 notebook doing the job; the original 1992 Turbo Pascal source is at the bottom.




The strategy is simple. The general sends two signals. One propagates by the speed of light, "c", and the other by "c/3". The faster one gets reflected and meets the slower one exactly in the middle. The middle soldier (or two soldiers) become new local "generals" and are sending similar signals to both sides. When the density of signals becomes high enough, everyone fires. Here is what P=39 soldiers will do; I needed about 19 characters and 3P units of time:

g.....................................f
hs....................................f
i.s...................................f
j1.s..................................f
j2..s.................................f
j3...s................................f
j.1...s...............................f
j.2....s..............................f
j.3.....s.............................f
j..1.....s............................f
j..2......s...........................f
j..3.......s..........................f
j...1.......s.........................f
j...2........s........................f
j...3.........s.......................f
j....1.........s......................f
j....2..........s.....................f
j....3...........s....................f
j.....1...........s...................f
j.....2............s..................f
j.....3.............s.................f
j......1.............s................f
j......2..............s...............f
j......3...............s..............f
j.......1...............s.............f
j.......2................s............f
j.......3.................s...........f
j........1.................s..........f
j........2..................s.........f
j........3...................s........f
j.........1...................s.......f
j.........2....................s......f
j.........3.....................s.....f
j..........1.....................s....f
j..........2......................s...f
j..........3.......................s..f
j...........1.......................s.f
j...........2........................sf
j...........3.........................z
j............1.......................zf
j............2......................z.f
j............3.....................z..f
j.............1...................z...f
j.............2..................z....f
j.............3.................z.....f
j..............1...............z......f
j..............2..............z.......f
j..............3.............z........f
j...............1...........z.........f
j...............2..........z..........f
j...............3.........z...........f
j................1.......z............f
j................2......z.............f
j................3.....z..............f
j.................1...z...............f
j.................2..z................f
j.................3.z.................f
j..................k..................f
j.................zls.................f
j................z.m.s................f
j...............z.4n1.s...............f
j..............z..5n2..s..............f
j.............z...6n3...s.............f
j............z...4.n.1...s............f
j...........z....5.n.2....s...........f
j..........z.....6.n.3.....s..........f
j.........z.....4..n..1.....s.........f
j........z......5..n..2......s........f
j.......z.......6..n..3.......s.......f
j......z.......4...n...1.......s......f
j.....z........5...n...2........s.....f
j....z.........6...n...3.........s....f
j...z.........4....n....1.........s...f
j..z..........5....n....2..........s..f
j.z...........6....n....3...........s.f
jz...........4.....n.....1...........sf
s............5.....n.....2............z
js...........6.....n.....3...........zf
j.s.........4......n......1.........z.f
j..s........5......n......2........z..f
j...s.......6......n......3.......z...f
j....s.....4.......n.......1.....z....f
j.....s....5.......n.......2....z.....f
j......s...6.......n.......3...z......f
j.......s.4........n........1.z.......f
j........s5........n........2z........f
j........cg........n........cg........f
j.......zdhs.......n.......zdhs.......f
j......z.ei.s......n......z.ei.s......f
j.....z.4fj1.s.....n.....z.4fj1.s.....f
j....z..5fj2..s....n....z..5fj2..s....f
j...z...6fj3...s...n...z...6fj3...s...f
j..z...4.fj.1...s..n..z...4.fj.1...s..f
j.z....5.fj.2....s.n.z....5.fj.2....s.f
jz.....6.fj.3.....snz.....6.fj.3.....sf
s.....4..fj..1.....q.....4..fj..1.....z
js....5..fj..2....zns....5..fj..2....zf
j.s...6..fj..3...z.n.s...6..fj..3...z.f
j..s.4...fj...1.z..n..s.4...fj...1.z..f
j...s5...fj...2z...n...s5...fj...2z...f
j...cg...fj...cg...n...cg...fj...cg...f
j..zdhs..fj..zdhs..n..zdhs..fj..zdhs..f
j.z.ei.s.fj.z.ei.s.n.z.ei.s.fj.z.ei.s.f
jz.4fj1.sfjz.4fj1.snz.4fj1.sfjz.4fj1.sf
s..5fj2..zs..5fj2..q..5fj2..zs..5fj2..z
js.6fj3.zfjs.6fj3.zns.6fj3.zfjs.6fj3.zf
j.k.fj.k.fj.k.fj.k.n.k.fj.k.fj.k.fj.k.f
jzlsfjzlsfjzlsfjzlsnzlsfjzlsfjzlsfjzlsf
s.m.zs.m.zs.m.zs.m.q.m.zs.m.zs.m.zs.m.z
jknkfjknkfjknkfjknknknkfjknkfjknkfjknkf
---------------------------------------

I was playing with that because of a mistake I did. At some moment, I thought that the time needed for synchronization scaled like the number of soldiers multiplied by their logarithm (and it looks similar to the fast scramblers that underlie the thermalization in black holes). The logarithm measures the number of hierarchies. However, there's no logarithm: I forgot to appreciate that the shorter sequences are synchonized more quickly. So let me avoid any talk about this mistake. ;-)

Could the world work like one of these causal cellular automata? Well, the speed limit is promising. But such discrete systems can't really be relativistic, despite the existence of the speed limit. See Computational universe vs Lorentz symmetry. Equally importantly, the postulates of quantum mechanics are completely violated, too.

So the answer is probably No, and despite the superficial similarities with the propagation of signals by the speed "c" and "c/3", it remains more appropriate to assign similar homework problems to computer science students rather than the physicists.

Add to del.icio.us Digg this Add to reddit