A FAMILY OF SMALLEST SYMMETRICAL FOUR-STATE FIRING SQUAD SYNCHRONIZATION PROTOCOLS FOR RING ARRAYS

摘要

An existence or non-existence of five-state firing squad synchronization protocol has been a longstanding and famous open problem for a long time. In this paper, we answer partially to this problem by proposing a family of smallest four-state firing squad synchronization protocols that can synchronize any one-dimensional ring cellular arrays of length n - 2{sup}k for any positive integer k. The number four is the smallest one in the class of synchronization protocols proposed so far.