Nonexistence of Minimal-time Solutions for Some Variations of the Firing Squad Synchronization Problem having Simple Geometric Configurations
Kojiro Kobayashi
We prove nonexistence of minimal-time solutions for three variations of FSSP. Configurations of these variations are paths in the twodimensional grid space having simple geometric shapes. In the first variation a configuration is an L-shaped path such that the ratio of the length of horizontal line to that of the vertical line is fixed. The general may be at any position. In the second and the third variations a configuration is a rectangular wall such that the ratio of the length of the two horizontal walls to that of the two vertical walls is fixed. The general is at the left down corner in the second variation and may be at any position in the third variation. We use the idea used in the proof of Yamashita et al’s recent similar result for variations of FSSP with sub-generals.
Keywords: Firing squad synchronization problem, optimal-time solution, nonexistence proof, sub-general, cellular automata, distributed computing