A 4-state solution to the Firing Squad Synchronization Problem based on hybrid rule 60 and 102 cellular automata

Ning Li, Liang Shi-li, Shuang Cui, Xu Mei-ling, Zhang LingarXiv 2012 · DOI · arXiv

Abstract

In this paper, we present a 4-state solution to the Firing Squad Synchronization Problem (FSSP) based on hybrid rule 60/102 Cellular Automata (CA). This solution solves the problem on the line of length $2^n$ with two generals. Previous work on FSSP for 4-state systems focused mostly on linear cellular automata, which synchronize an infinite number of lines but not all possible lines. We give time-optimal solutions to synchronize an infinite number of lines by rule 60 and rule 102 respectively, and construct a hybrid rule 60 and 102 states transition table. Compared to the known solutions of cellular automata, the hybrid CA way is simpler and faster, with a minimal time of $(n-1)$ steps.

TL;DR

This paper presents a novel 4-state solution to the classic Firing Squad Synchronization Problem (FSSP) specifically for cellular arrays of length $2^n$. By hybridizing Wolfram’s Rule 60 and Rule 102 and employing two "generals" (one at each end of the line), the authors achieve synchronization in just $(n-1)$ steps—outperforming the standard minimal time for single-general systems.

What Problem Does This Paper Address?

The Firing Squad Synchronization Problem (FSSP) is a foundational challenge in cellular automata (CA) research. Imagine a line of $n$ identical "soldiers" (finite automata). Initially, all are quiescent except for one "general" at the end. The goal is to design a transition rule—where each cell's next state depends only on itself and its immediate neighbors—such that all cells enter a specific "firing" state simultaneously for the first time.

Standard FSSP setup with a single general.

Researchers typically compete on two metrics:

  1. State Complexity: The minimum number of states per cell required to solve the problem.
  2. Time Complexity: The number of steps until synchronization.

While 6-state and 8-state solutions exist for general line lengths in "minimal time" ($2n-2$ steps), finding low-state solutions (like 4 states) is notoriously difficult. In fact, it has been proven that a 4-state solution for all possible line lengths in minimal time does not exist. This paper tackles a specific subset of the problem: synchronizing lines where the length is a power of two ($2^n$) using a very small state set.

Methods

The authors build upon the algebraic properties of elementary cellular automata, specifically Rule 60 and Rule 102.

  • Rule 60: A left-oriented rule where a cell's state is determined by its own state and its left neighbor. It essentially generates a Pascal’s triangle modulo 2.
  • Rule 102: The mirror image of Rule 60, where the state depends on the cell and its right neighbor.
  • The Hybrid Approach: Previous 4-state solutions often relied on a single general. This paper introduces a two-general configuration (one at the left end, one at the right). By combining Rule 60 and Rule 102 into a single transition table, the authors create a symmetrical "wave" of state changes that converge from both ends.
Spatio-temporal evolution of the hybrid Rule 60/102 system.

The transition functions are expressed algebraically (using modulo 2 arithmetic) to define how the four states—General ($G$), Quiescent ($Q$), an intermediate state ($x_1$), and Fire ($F$)—interact.

Key Insights and Ideas

  • Symmetry as a Shortcut: By using two generals instead of one, the authors effectively halve the distance information needs to travel. This allows for a synchronization time of $(n-1)$, which is significantly faster than the $2n-2$ steps required for single-general minimal-time solutions.
  • The Power of $2^n$: The choice of line length $2^n$ is not arbitrary. Rules 60 and 102 produce fractal patterns (Sierpinski triangles) that "complete" or reach a uniform state precisely at powers of two. The authors exploit this inherent mathematical property to trigger the "Fire" state simultaneously across the entire array.
  • State Efficiency: The paper demonstrates that by narrowing the scope to specific line lengths ($2^n$), the state complexity can be pushed down to just 4 states, which is near the theoretical minimum for any non-trivial synchronization.

Key Results

  • Optimal Time for $2^n$: The proposed hybrid CA synchronizes a line of $2^n$ cells in exactly $(n-1)$ steps.
  • Simplicity: Compared to previous 4-state solutions (like those by Jean-Baptiste Yunès), the hybrid Rule 60/102 approach is simpler to implement and faster in execution due to the dual-general setup.
  • Transition Tables: The paper provides complete transition tables that define the 4-state logic for both the individual rules and the hybrid system.

Limitations and Future Work

  • Length Constraint: The primary limitation is that this specific 4-state solution only works for lines of length $2^n$. It is not a "full" solution that can synchronize a line of any arbitrary length $n$.
  • Two Generals Required: The $(n-1)$ speedup depends on having a general at both ends, which changes the standard constraints of the original FSSP.
  • Future Directions: The authors suggest that this hybrid approach is a promising path for finding other non-minimal-time solutions with very few states. Further exploration of elementary CA rules could lead to solutions for a broader range of line lengths while maintaining low state complexity.

Summary updated

Abstract

In this paper, we present a 4-state solution to the Firing Squad Synchronization Problem (FSSP) based on hybrid rule 60/102 Cellular Automata(CA). This solution solves the problem on the line of length 2^n with two generals. Previous work on FSSP for 4-state systems focused mostly on linear cellular automata, where synchronizes an infinite number of lines but not all possible lines. We give time-optimal solutions to synchronize an infinite number of lines by rule 60 and rule 102 respectively, and construct a hybrid rule 60 and 102 states transition table. Compared to the known solutions of cellular automata, the hybrid CA way is simpler and faster, the minimal time is (n-1) step.
BibTeX
@misc{li2012state,
  author = {Ning Li and Liang Shi-li and Shuang Cui and Xu Mei-ling and Zhang Ling},
  title = {{A 4-state solution to the Firing Squad Synchronization Problem based on hybrid rule 60 and 102 cellular automata}},
  year = {2012},
  eprint = {1212.3069},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1212.3069},
}

Loading related content...

Figure