TDEB Top Bar

Trending
Semiconductor Industry News — The Digital Electronics Blog
Follow Us

TDEB Masthead

The Semiconductor Hub

Semiconductors.  Chips and Systems.  Innovation.

Indexed by leading Search Engines, AI and referenced by Engineers worldwide 500+ Articles 10M+ Pageviews 30+ Reports 50+ Citations

Feynman's Firing Squad Puzzle: Synchronizing Finite State Machines

Murugavel Ganesan
by
0
Share Facebook X LinkedIn WhatsApp Email

In The Feynman Lectures on Computation, Richard Feynman poses a neat puzzle about synchronizing finite state machines that act as a general and a line of soldiers. He could solve it, but not in the minimum possible time, and he closed his description with a Fermat-like remark: someone had found a minimum-time solution, it was very difficult, and the reader should not be so ambitious.

The original version of this post quoted another writer's introduction and a long passage from the book. It has been replaced with a summary in our own words, an explanation of how the puzzle is solved, and the history of the minimum-time answer.

The puzzle in plain words

Feynman sets it as Problem 3.4, just before he introduces Turing machines. Picture a long line of N identical finite state machines, the "soldiers", with a "general" at one end. Time moves in discrete steps. The rules are:

  • At each step, every machine's next state depends only on its own state and the states of its two immediate neighbors.
  • All soldiers start in the same quiet state. The general starts things off with a single "fire" signal to the soldier next to him and then does nothing more.
  • The method must work for any N. Since each soldier is a finite state machine with a fixed number of states, no soldier can count the line or be given a number.
  • The goal is for all soldiers to enter a special "fire" state at the same step, for the first time, in the shortest possible time.

The difficulty is that no soldier knows how long the line is, and each one can only talk to its neighbors. Yet they must all agree on the same instant.

Why it matters to digital designers

This is the classic firing squad synchronization problem, first proposed by John Myhill in 1957 (Wikipedia: firing squad synchronization problem). It is a pure form of a real design question: how do many identical local cells, each seeing only its neighbors, reach a global agreement? The same idea appears in systolic arrays, cellular automata, distributed reset and start-up in large arrays of processing elements, and in network protocols where nodes have only local knowledge.

The key idea: find the middle

The usual solution splits the line in half, again and again. The general sends two signals down the line at once: a fast one that moves one soldier per step, and a slow one that moves one soldier every three steps. The fast signal reaches the far end, bounces back and meets the slow signal exactly in the middle. The soldier (or pair) there becomes a new general for each half, and the process repeats in both halves at once. When every segment is a single soldier, all of them fire together.

Deep dive: the numbers and details

This part holds the timing of the halving solution, the minimum-time bound and the history of the state counts. Skip it if the overview is all you need.

Why the signals meet in the middle

Let the line have length n. The fast signal (speed 1) travels to the end and back, so after time t (for t > n) it is at position 2n - t. The slow signal (speed 1/3) is at position t/3. They meet when 2n - t = t/3, that is t = 3n/2, at position n/2. The midpoint is found without anyone counting.

Total time of the halving solution

Each level costs about 3/2 times the length of the current segment, and the segments halve each time:

T(n) = 3n/2 + T(n/2) = 3n/2 + 3n/4 + 3n/8 + ... ≈ 3n

This is the McCarthy and Minsky style solution, which takes about 3n steps. For a line of 100 soldiers it fires at around step 300.

The minimum possible time: 2n - 2

No solution can be faster than 2n - 2 steps. The signal from the general needs n - 1 steps to reach the last soldier, and the last soldier cannot know it is last until it has seen that it has no neighbor. Information about the far end then needs another n - 1 steps to get back to the soldier next to the general, who cannot fire until it knows the length of the line. So the total is at least (n - 1) + (n - 1) = 2n - 2.

Soldiers nHalving solution (about 3n)Minimum time (2n - 2)
10about 3018
100about 300198
1,000about 3,0001,998

The minimum-time solutions reach this bound by sending many signals at different speeds (1, 1/3, 1/7 and so on) so the line is divided into halves, quarters and eighths in parallel rather than one level after another.

History of minimum-time solutions

YearWhoStates per soldier
1957John Myhill poses the problem-
1962Eiichi Goto, first minimum-time solutionThousands
1966Waksman16
1967Balzer, who also argued no 4-state solution exists8
1987Mazoyer, best known solution6

Source: Firing squad synchronization problem: solutions. Balzer's search for 4-state solutions was later found to be incomplete, but a corrected search confirmed that none exists. Whether a 5-state solution exists is still an open question.

Thinking about it as a hardware designer

  • State encoding: a 6-state soldier needs 3 flip-flops; Goto's thousands of states would need over 10. The race to fewer states is a race to smaller cells.
  • Local rules only: each cell's next-state logic has three inputs (left, self, right), so it is a pure lookup table. With 6 states that is 6 x 6 x 6 = 216 entries, plus boundary cases.
  • Simulation exercise: coding the halving solution in Verilog or VHDL as an array of identical cells is a good way to practice parameterized, generate-based design and to check that every cell fires on the same clock.

Further reading

Murugavel Ganesan
About the Author
Murugavel Ganesan
Product Director | SerDes · IVN · Edge AI · Compute | Ex Intel · Infineon

A semiconductor product leader working across product architecture, definition, strategy, and silicon and software execution, from concept through volume production. He has worked with teams across Asia, Europe and the USA, including at Intel, Infineon and ArrayComm.

His work covers ASICs, SoCs, FPGAs and chiplets for wireless, wireline, automotive, IoT and AI, including PCIe, CXL and DDR interfaces alongside RF and mixed-signal design.

Share Facebook X LinkedIn WhatsApp Email

Post a Comment

0 Comments

Your comments will be moderated before it appears here.

Post a Comment (0)

#buttons=(Ok, Go it!) #days=(20)

Our website uses cookies to enhance your experience. Learn more
Ok, Go it!