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: v2 · 2026-08-30 · History
Domain-specific #: 1843
Origin domain: cellular automata
Subdomain: finite-state synchronization protocols
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.

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 prime: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) — more general patterns this builds on

Firing-Squad Synchronization Problem is a kind of Synchronization Prime

The minimal prospective placement is a strict composition/instantiates edge to live prime:synchronization.

Neighborhood in Abstraction Space¶

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

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08