A Smallest Five-State Solution to the Firing Squad Synchronization Problem.

An existence or non-existence of five-state firing squad synchronization protocol has been a long-standing, famous open problem for a long time. In this paper, we answer partially to this problem by proposing a smallest five-state firing squad synchronization algorithm that can synchronize any one-dimensional cellular array of length n = 2k in 3n − 3 steps for any positive integer k. The number five is the smallest one known at present in the class of synchronization protocols proposed so far. [ABSTRACT FROM AUTHOR]