Communications of the ACM
Firing Squad Synchronization, Computer Science's Most Macabre-Sounding Problem
A California State University professor says programming a computer to sold the problem of getting a firing squad to shoot in unison must allow for synchronization without counting or even knowing the number of soldiers in the squad.
Credit: CC-BY-SA
Getting a firing squad to fire in sync is a puzzle that was 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.
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.
From Motherboard
View Full Article
Abstracts Copyright © 2015 Information Inc., Bethesda, Maryland, USA
No entries found