Firing squad synchronization problem

Firing squad synchronization problem

The firing squad synchronization problem is a problem in computer science and cellular automata first proposed by John Myhill in 1957 and published (with a solution) in 1962 by Edward Moore. The problem is analogous to problems of logical design, systems design, and programming, and can be stated as follows:

:Consider a finite amount - but arbitrarily many - of identical finite state machines (soldiers) arranged in a line. At time t=0, every soldier is initialized to the same state, except for the soldier on the far left (the general). At every time t>0, the state of every soldier is dependent upon its state and the state of its two neighbors at time t-1 (except for the two soldiers at either end, whose state depends only upon itself and its one neighbor). In addition, a soldier cannot change state at time t if its state and its neighbors' states at time t-1 is equal to the initial state. The problem is to define such a set of rules for the soldiers such that all soldiers enter for the first time a distinguished state (fire) at the same time.


The first solution to the FSSP was found by John McCarthy and Marvin Minsky and was published in Sequential Machines by Moore. A solution using a minimal amount of states was introduced by Jacques Mazoyer in 1988, whose solution uses only six states. [Mazoyer 1987 ] In addition, he also proved that no four state solution exists. It is still unknown whether a five state solution exists.

A solution using a minimal amount of time was later found by Professor E. Goto at M.I.T., whose solution uses thousands of states and requires exactly 2n-2 units of time for n soldiers. It is proven that a solution using a smaller amount of time cannot exist.

General solution

A general solution to the FSSP involves propagating two waves down the line of soldiers: a fast wave and a slow wave moving three times as slow. The fast wave bounces off the other end of the line and meets the slow wave in the centre. The two waves then split into four waves, a fast and slow wave moving in either direction from the centre, effectively splitting the line into two equal parts. This process continues, subdividing the line until each division is of length 1. At this moment, every soldier fires. This solution requires 3n units of time for n number of soldiers.

Optimal solution for the line

An optimal 2n-2 time solution was first described in (Waksman,1966). The general sends to the right signals S_1, S_2, S_3, ldots, S_i at speeds 1,1/3,1/7,...,1/(2^{i-1}-1). The signal S_1 reflects at the right end of the line (like the fast wave in the preceding section), and meets signal S_i (for igeq 2) at cell n/2^{i-1}. When S_1 reflects, it also creates the new general at the right end.

Signals S_i are constructed using auxiliary signals, which propagate to the left. Every second time the signal moves (to the right), it send an auxiliary signal to the left. S_1 moves on its own at speed 1, signal S_i for igeq 2 moves only when they get an auxiliary signal.


Several generalizations of the FSSP have been conjectured and studied, including the FSSP on one-dimensional lines with the general at an arbitrary location, closed rings, Cayley graphs, squares, rectangles, cubes, and general networks.

External links

* [] "Firing Squad Problem"
* [] "On Formulations of Firing Squad Synchronization Problems"
* [] "Firing squad synchronization"


* cite journal
title = An Optimum Solution to the Firing Squad Synchronization Problem
author = Abraham Waksman
first = Abraham
last = Waksman
pages = 66--78
journal = Information and Control
month = feb
year = 1966
volume = 9
number = 1
doi = 10.1016/S0019-9958(66)90110-0

* cite journal |last=Mazoyer |first=Jacques |title=A six-state minimal time solution to the firing squad synchronization problem |journal=Theoretical Computer Science | volume = 50| number = 2
year = 1987 | pages = 183--238|doi = 10.1016/0304-3975(87)90124-1

* cite journal
last=Balzer | first=Robert | title = An 8-state Minimal Time Solution to the Firing Squad Synchronization Problem | journal = Information and Control
year = 1967
month = jan
number = 1
volume = 10
bibsource = "DBLP,"
pages = 22--42 | doi = 10.1016/S0019-9958(67)90032-0

* cite journal
first = Ilka
last = Shinahr
title = Two- and three-dimensional firing-squad synchronization problem
journal = Information and Control
pages = 163--180
year = 1974
volume = 24
publisher = Academic Press
address = New York-San Francisco-London-San Diego
doi = 10.1016/S0019-9958(74)80055-0

* cite journal
title = A Generalized Firing Squad Problem
author = F. R. Moore and G. G. Langdon
pages = 212--220
journal = Information and Control
month = mar
year = 1968
volume = 12
number = 3
references = cite{IC::Waksman1966

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Задача синхронизации стрелков — Задача синхронизации стрелков  задача из области информатики и клеточных автоматов, впервые предложенная Джоном Майхиллом в 1957 году и опубликованная (с решением) в 1962 году Эдвардом Муром[1]. Формулируется следующим образом: Рассмотрим… …   Википедия

  • John Myhill — John R. Myhill (Senior) was a mathematician. He received his Ph.D. from Harvard University under Willard Van Orman Quine in 1949. He was professor at SUNY Buffalo from 1966 until his death in 1987. He also taught at several other universities.In… …   Wikipedia

  • Cellular automaton — A cellular automaton (plural: cellular automata) is a discrete model studied in computability theory, mathematics, theoretical biology and microstructure modeling. It consists of a regular grid of cells , each in one of a finite number of states …   Wikipedia

  • FSSP — may refer to:*Families of structurally similar proteins, a protein structures database *Firing squad synchronization problem, a problem in computer science and cellular automata *Frances Slocum State Park, a state park in Luzerne County,… …   Wikipedia

  • Jacques Mazoyer — Jacques Mazoyer, ancien élève de l École polytechnique (promo 1968) est un chercheur en informatique théorique français, qui est connu pour ses résultats sur les automates cellulaires, en particulier le problème de la synchronisation d une ligne… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”