Firing-Squad Synchronization Problem¶

Find one finite local rule that, from a single endpoint trigger, makes every cell in an arbitrarily long finite cellular-automaton line enter a firing state simultaneously for the first time.

Version: v3 · 2026-09-19 · History
Domain-specific #: 1843
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomains: Cellular Automata, Finite State Synchronization Protocols → Mathematics
Aliases: Firing synchronization problem, FSSP, Firing squad problem

Core Idea¶

The firing-squad synchronization problem (FSSP) asks whether one finite-state, nearest-neighbor rule can make every cell in a finite but arbitrarily long line enter a distinguished firing state on the same update, for the first time, when initially only one endpoint cell is activated. The interior cells are indistinguishable and do not know the line length. Information travels only through local state transitions, so the common firing time must be constructed from signals that propagate through the array.

The problem is a canonical test of distributed synchronization under severe informational constraints. It joins a universal protocol requirement—one fixed state set and transition function must work for every permitted length—with a safety condition—no cell fires early—and a liveness condition—all cells eventually fire together.

How would you explain it like I'm…

Everybody Shout Together

Imagine a long line of kids who can only whisper to the kid right next to them. Nobody knows how long the line is. A kid at one end says 'start!' The puzzle is to find one set of whisper rules that makes every kid clap at exactly the same moment, with nobody clapping too early, no matter how long the line is.

The Same-Moment Line Puzzle

The Firing-Squad Synchronization Problem imagines a row of identical little machines, each able to look only at its two neighbors. Each machine has only a small, fixed set of moods, or states, and they all follow the same rulebook, step by step together. At the start, only the machine at one end is switched on, and nobody knows how long the row is. The goal is a single rulebook that makes every machine enter a special 'fire' state at the very same step, for the first time, whatever the row's length. To do this, signals have to travel back and forth along the row to work out where the middle is. The firing-squad story is just a way to remember the puzzle.

Cellular Automaton Synchronization Problem

The Firing-Squad Synchronization Problem asks for one rule for a line of cells, like a one-dimensional cellular automaton. Each cell has finitely many states and updates based only on itself and its nearest neighbors. Starting with only one endpoint activated, the rule must make every cell enter a 'firing' state at the same time step, for the first time. It must work for a line of any finite length, even though the cells are identical and don't know that length. Since information only spreads locally, the solution uses signals moving at different speeds to locate midpoints and divide the line recursively. The problem combines three requirements. It must be universal (one rule for every length), safe (no cell fires early), and live (all cells eventually fire together). Waksman found a solution in the fastest possible time, and Mazoyer later found one using only six states.

The FSSP asks for a single finite-state, nearest-neighbor transition rule on a finite line of cells of arbitrary length n. Initially every cell is quiescent except one endpoint, the 'general'. The rule must drive all cells into a distinguished firing state simultaneously, with no cell entering it earlier. Interior cells are identical and have no access to n, so the global firing time must be built from signals propagating through the array via local transitions. Standard constructions send signals at different speeds whose meetings mark midpoints, then recurse on subsegments until every cell is a boundary. The problem formalizes distributed synchronization under extreme informational limits. It has a universal protocol requirement (fixed state set and transition function for all n), a safety property (no premature firing) and a liveness property (eventual simultaneous firing). Waksman gave an optimum-time construction, and Mazoyer later gave a six-state solution, anchoring research that trades time against the number of local states. The firing-squad narrative is only a mnemonic for a homogeneous array that infers its global extent to coordinate a unique simultaneous event.

Scope of Application¶

The core node covers the classical finite one-dimensional, nearest-neighbor, synchronous cellular automaton with one endpoint general. The research literature varies state count, firing time, neighborhood, geometry, reversibility, communication alphabet, number and position of generals, and fault assumptions. Surveys treat the problem as a persistent benchmark for cellular synchronization, including one- and two-dimensional arrays.

Variants belong under the node only when they retain the recognition task: a size-independent local finite-state protocol must cause a globally simultaneous first activation from constrained initial information.

Clarity¶

A candidate protocol passes only if it quantifies over all supported lengths. Test (n=1) and small lengths, but do not infer general correctness from simulation. Then verify three properties separately: every execution eventually reaches a firing round; all cells fire on that round; and none fires earlier.

Manages Complexity¶

FSSP compresses distributed coordination into a precise benchmark. Geometry, memory, communication radius, initialization, safety, liveness, and performance are explicit, allowing algorithms to be compared rather than described informally.

Signal constructions turn unknown global size into locally representable events. Fast and slow waves, reflections, recursive midpoint marking, or related state patterns cause different parts of the array to discover a shared deadline without storing (n) numerically. The protocol encodes global structure temporally in the interactions of finite signals.

Abstract Reasoning¶

Let (Q) be a finite state set with quiescent (q), general (g), firing (f), and boundary symbol \(b\notin Q\). A radius-one rule

\[ \delta:(Q\cup\{b\})^3\rightarrow Q \]

updates every cell synchronously. For each length (n), initialize (c_0(0)=g) and (c_i(0)=q) for (i>0). A solution requires a time (T(n)) such that (c_i(T(n))=f) for every (i), while \(c_i(t)\ne f\) for every (i) and (t<T(n)).

Knowledge Transfer¶

Literal transfer occurs in cellular-automaton geometries and locally connected finite-state arrays that preserve the task. Higher-dimensional grids, multiple-general variants, and reversible automata extend the same benchmark while changing lower bounds or construction techniques.

The portable residue is Synchronization: align separate processes so a critical event co-occurs. FSSP adds homogeneous finite cells, a quiescent background, a single endpoint trigger, unknown size, local propagation, first-fire safety, and uniformity across all lengths. Those commitments make it domain-specific.

Relationships to Other Abstractions¶

Current abstraction Firing-Squad Synchronization Problem Domain-specific

Parents (1) — outgoing typed relations

Firing-Squad Synchronization Problem is a kind of Synchronization Prime

The problem realizes synchronization as a constrained construction task; it is not a taxonomic subtype of every synchronized phenomenon.

Hierarchy paths (7) — routes to 6 parentless roots

Firing-Squad Synchronization Problem → is a kind of Synchronization → is a kind of Coordination → presupposes Concurrency

Show alternative paths (6)

Neighborhood in Abstraction Space¶

Firing-Squad Synchronization Problem sits in a sparse region of the domain-specific corpus (88^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Automata & Formal Grammar Models (9 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25