Firing Squad Synchronization, Computer Science’s Most Macabre-Sounding Problem

by Ben Richmond, Motherboard

Getting a firing squad to fire in sync is a puzzle studied in computer science’s early days, because it was vital to automata theory. California State University professor Darin Goldstein says programming a computer to solve the problem must allow for synchronization without counting or even knowing the number of soldiers in the firing squad. Every soldier in the line is a finite state automaton – and a very simple one at that. They have no memory and can only receive very simple instructions.

The solution to the problem, worked out by computer science pioneers John McCarthy (an ACM A.M. Turing Award recipient) and Marvin Minsky in the early 1960s, was to send out multiple messages at differing speeds, one going three times faster that the other, enabling the first message to reach the other side of the line, bounce back and reach the other right at the line’s mid-point.

Goldstein says when the messages intersect, the soldier in the middle becomes another general, creating two lines. “And then as soon as you have that, you go again, you keep splitting the line in two over and over and eventually every soldier will consider himself a general,” he notes. “And as soon as they all know the guy to left and right is a general, they fire.”

This renders the line into a grid, the solving of which produces a three-dimensional object, Goldstein says. “The most general problem is the strongly-connected directed graph and that was solved multiple times,” he points out.  Read the article

DCL: I remember getting this problem to solve as a take-home quiz in Marvin Minsky’s class when I was a student at MIT!  Also, although the article says McCarthy solved it, I have my doubts. Minsky solved it, is far more likely.