Home → News → Firing Squad Synchronization, Computer Science's Most... → Full Text

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

By Motherboard

July 17, 2015

[article image]

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