Home // FUTURE COMPUTING 2018, The Tenth International Conference on Future Computational Technologies and Applications // View article

Four-State Partial Synchronizers for a Large-Scale of Processors -Symmetric Synchronizers

Authors:
Hiroshi Umeo
Naoki Kamikawa

Keywords: cellular automata; FSSP; synchronization

Abstract:
The synchronization in cellular automata has been known as the Firing Squad Synchronization Problem (FSSP) since its development, where the FSSP gives a finite-state protocol for synchronizing a large scale of cellular automata. A quest for smaller state FSSP solutions has been an interesting problem for a long time. Umeo, Kamikawa and Yun`es [2009] answered partially by introducing a concept of partial FSSP solutions and proposed a full list of the smallest four-state symmetric powers-of- 2 FSSP protocols that can synchronize any one-dimensional (1D) ring cellular automata of length n = 2k for any positive integer k ≥ 1. Afterwards, Ng [2011] also added a list of asymmetric FSSP partial solutions, thus completing the four-state powers-of- 2 FSSP partial solutions. The number four is the lower bound in the class of FSSP protocols. A question: are there any other four-state partial solutions? remained. In this paper, we answer the question by proposing a new class of the smallest symmetric four-state FSSP protocols that can synchronize any 1D ring of length n = 2k−1 for any positive integer k ≥ 2. We show that the class includes a rich variety of FSSP protocols that consists of 39 symmetric solutions, ranging from minimum-time to linear-time in synchronization steps. In addition, we make an investigation into several interesting properties of these partial solutions, such as swapping general states and a duality property between them.

Pages: 4 to 9

Copyright: Copyright (c) IARIA, 2018

Publication date: February 18, 2018

Published in: conference

ISSN: 2308-3735

ISBN: 978-1-61208-608-8

Location: Barcelona, Spain

Dates: from February 18, 2018 to February 22, 2018