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

You'd think that the question of how to get everyone in a firing squad line to fire at the same time is best left to states desperate to keep capital punishment going without lethal injection drugs, but it might be a surprise to find that the question was also studied in the early days of computer science.

Of course, in a world where something called the "prisoner's dilemma" is invoked for social sciences and economics, bizarre or macabre-sounding thought problems pop up with some regularity. But man, the firing squad synchronization problem has got to be one of the bleakest.

To get a better grasp on the problem, the solution, and why it was ever a problem to begin with, I called up Darin Goldstein, a computer science professor in California State University Long Beach's computer science and computer engineering school, who has published papers on the problem, and remains in thrall of the problem's elegance.

He described the firing squad synchronization problem like this: Imagine a firing squad, all standing in a line, with a general on one end, who needs to tell the squad when to all shoot their guns at once. Firing at the same time was paramount for execution squads, so that no one would know who fired the fatal shot. This notion was so important thatat some points in history, some bullets would be substituted with blanks, and the riflemen wouldn't even know which they were firing.

According to the problem, the general stands at one end of the line and needs a way to tell everyone to fire at once, and doesn't want to use an audible countdown because, as Goldstein put it, "that would be horrible." So the only way for the line to communicate is for the riflemen to pass the message on to the soldier directly next to his left or right—as was the case in very early computing.

The question, first formulated in the 1950s, was essential to automata theory, which became the foundation of computer science, Goldstein explained.

"Alan Turing came up with the general model for what a computer should look like," he said, taking things back to the very beginning. "He came up with the idea of a computer with a brain, the automata, and then memory, which is a long ticker tape with cells on it that you can write things on. If you have a computer, you have a CPU (the brain) and the hard drive (the memory). And there are other parts, but that's the basic idea. Brain and memory."

"The brain that Turing came up with had no memory. The brain was just in a state, and that's what you're thinking about at that time," he said. "So every soldier in the line is an automata. They have no memory and can only receive very simple instruction. They can remember what they heard last time—and that's the automata: what you're thinking about."

Goldstein said the elegance of the problem was cool, and originally he thought it was going to be a really important problem.

"We have a lot of mobile devices, and if you think about taking these devices and making them the absolute smallest, they wouldn't have hard drives. If you miniaturize a phone or computer to the size of a dust particle, computers wouldn't be able to identify themselves at all, they could only receive and send and only keep a very small amount of information, depending on what they hear," he said. "There was some talk a while ago, if you want to, you can take these dust things and spread them—insert them—and they could do things. With a lot of these things, they could collect information, but how could they collect information without holding anything? How do you make a conglomeration of things that can't think, think?"

The solution to the line of soldiers, Goldstein said, is something that a smart computer science person could work out in a few hours. Computer science pioneers John McCarthy and Marvin Minksy published this solution in the early 60s. If you want to go deep into the weeds on this, check out Stanford's treatment of it, but Goldstein explained it really well.

"What's the absolute minimum time you think [synchronization] could be done?" Goldstein asked me. "Say there are n soldiers. How long would it take to synchronize?"

I guessed N-times the amount of time it takes to tell each other and Goldstein said that most of the time people just say the general should just start a countdown at the number of soldiers—so, if there's 10 soldiers in the line, he tells the first soldier "10" and that soldier tells the next one "nine," and then so forth. You only need 10 types of messages, and it seems to work, right?

"That's not legal though," Goldstein said, because to really solve the problem, the general can't know how many people are in the line. "That number isn't a constant. The solution that you get has to be a constant size, no matter how long the line. So if you [use a solution that requires your soldiers operate with] a 1,000 messages, that solution stops working once you reach 1,001 soldiers."

Goldstein said the way you program has to be "quasi-clever," and you have to be able to synchronize without counting or even knowing the number of soldiers.

Minksy and McCarthy's solution was to send out multiple messages at different speeds, one going three times faster that the other, which allows the first message to reach the other side of the line, bounce back and reach the other right at the line's mid-point. When the messages intersect, Goldstein said, the middle guy becomes another general, and now you have 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 said. "And as soon as they all know the guy to left and right is a general, they fire."

So without ever knowing how many soldiers are in the line, you get them all primed and firing together.

A solution that uses only six states, currently the fewest. Look at how it scales!

After having solved the firing squad in a line problem, mathematicians began generalizing.

"Instead of line, they go to a grid, and once you solve the grid you go to a three-dimensional object. And then once you go to a 3D object, you move on to a general undirected graph, and once you do that you do a directed graph and on and on and on," Goldstein said. "Really, the most general problem is the strongly-connected directed graph and that was solved multiple times."

People also tried to work out faster solutions and ones that used ever simpler soldiers and were able to prove that the firing squad synchronization problem can't be solved in minimal time if the soldiers are only capable of four states—soldiers who can only operate with four types of messages. The lowest functional model, for now, uses six states. You can guess where Goldstein's headed with this.

"But five [states] have been open for about 30 years," Goldstein said. "So nobody knows five, and that annoys me. I really badly want to figure out five, because I feel like I could settle the problem."

And there's nothing worse than an unsettled problem, particularly one that's this unsettling.