A Small Five-State Non-Optimum-Time Solution to the Firing Squad Synchronization Problem

Abstract

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 small five-state firing squad synchronization algorithm that can synchronize any one-dimensional cellular array of length n = 2 ^k in 3n − 3 steps for any positive integer k.