Abstract
Synchronization of large-scale networks is an important and fundamental computing primitive in parallel and distributed systems. The synchronization in cellular automata, known as firing squad synchronization problem (FSSP), has been studied extensively for more than fifty years, and a rich variety of synchronization algorithms has been proposed. In the present paper, we give a brief survey on a class of non-optimum-time 3n-step FSSP algorithms for synchronizing one-dimensional (1D) cellular automata of length n in \(3n \pm O(\log n)\) steps and present a comparative study of a relatively large-number of their implementations. We also propose two smallest-state, known at present, implementations of the 3n-step algorithm. The paper gives the first complete transition rules sets for the class of non-optimum-time 3n-step FSSP algorithms developed so far.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Balzer, R.: An 8-state minimal time solution to the firing squad synchronization problem. Inf. Control 10, 22–42 (1967)
Fischer, P.C.: Generation of primes by a one-dimensional real-time iterative array. J. of ACM 12(3), 388–394 (1965)
Gerken, H.-D.: Über Synchronisations-Probleme bei Zellularautomaten. Diplomarbeit, Institut für Theoretische Informatik, Technische Universität Braunschweig, pp. 50 (1987)
Goto, E.: A minimal time solution of the firing squad problem. Dittoed Course Notes for Applied Mathematics, 298, pp. 52–59. Harvard University (1962)
Herman, G.T.: Models for cellular interactions in development without polarity of individual cells. I. General description and the problem of universal computing ability. Int. J Syst. Sci. 2(3), 271–289 (1971)
Herman, G.T.: Models for cellular interactions in development without polarity of individual cells. II. Problems of synchronization and regulation. Int. J Syst. Sci. 3(2), 149–175 (1972)
Kobuchi, Y.: A note on symmetrical cellular spaces. Inf. Process. Lett. 25, 413–415 (1987)
Mazoyer, J.: A six-state minimal time solution to the firing squad synchronization problem. Theor. Comput. Sci. 50, 183–238 (1987)
Minsky, M.: Computation: Finite and Infinite Machines, pp. 28–29. Prentice Hall, New Jersey (1967)
Moore, E.F.: The firing squad synchronization problem. In: Moore, F. (ed.) Sequential Machines: Selected Papers, pp. 213–214. Addison-Wesley, Reading MA. (1964)
Sanders, P.: Massively parallel search for transition-tables of polyautomata. In: Proceedings of the VI International Workshop on Parallel Processing by Cellular Automata and Arrays, (Jesshope, C., Jossifov, V., Wilhelmi, W. (eds.) Akademie, pp. 99–108 (1994)
Szwerinski, H.: Symmetrical one-dimensional cellular spaces. Inf. Control 67, 163–172 (1982)
Umeo, H.: Firing squad synchronization problem in cellular automata. In: Meyers, R.A. (ed.) Encyclopedia of Complexity and System Science, vol. 4, pp. 3537–3574. Springer, Heidelberg (2009)
Umeo, H., Kamikawa, N., Yunès, J.B.: A family of smallest symmetrical four-state firing squad synchronization protocols for ring arrays. Parallel Process. Lett. 19(2), 299–313 (2009)
Umeo, H., Maeda, M., Hongyo, K.: A design of symmetrical six-state 3n-step firing squad synchronization algorithms and their implementations. In: El Yacoubi, S., Chopard, B., Bandini, S. (eds.) ACRI 2006. LNCS, vol. 4173, pp. 157–168. Springer, Heidelberg (2006)
Vollmar, R.: Some remarks about the “Efficiency” of polyautomata. Int. J. Theor. Phys. 21(12), 1007–1015 (1982)
Waksman, A.: An optimum solution to the firing squad synchronization problem. Inf. Control 9, 66–78 (1966)
Yunès, J.-B.: Seven states solutions to the firing squad synchronization problem. Theor. Comput. Sci. 127(2), 313–332 (1994)
Yunès, J.-B.: An intrinsically non minimal-time Minsky-like 6-states solution to the firing squad synchronization problem. Theor. Inf. Appl. 42(1), 55–68 (2008)
Yunès, J.-B.: Simple new algorithms which solve the firing squad synchronization problem: a 7-states 4n-steps solution. In: Durand-Lose, J., Margenstern, M. (eds.) MCU 2007. LNCS, vol. 4664, pp. 316–324. Springer, Heidelberg (2007)
Yunès, J.B.: A 4-states algebraic solution to linear cellular automata synchronization. Inf. Process. Lett. 19(2), 71–75 (2008)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Umeo, H., Maeda, M., Sousa, A., Taguchi, K. (2015). A Class of Non-optimum-time 3n-Step FSSP Algorithms - A Survey. In: Malyshkin, V. (eds) Parallel Computing Technologies. PaCT 2015. Lecture Notes in Computer Science(), vol 9251. Springer, Cham. https://doi.org/10.1007/978-3-319-21909-7_22
Download citation
DOI: https://doi.org/10.1007/978-3-319-21909-7_22
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-21908-0
Online ISBN: 978-3-319-21909-7
eBook Packages: Computer ScienceComputer Science (R0)