Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-19T10:44:10.267Z Has data issue: false hasContentIssue false
  • English
  • Français

An intrinsically non minimal-time Minsky-like 6-states solution to the Firing Squad synchronization problem

Published online by Cambridge University Press:  18 January 2008

Jean-Baptiste Yunès
Jean-Baptiste Yunès*
Affiliation:
LIAFA, Université Paris 7 Denis Diderot, 175 rue du chevaleret, 75013 Paris, France; [email protected]
Get access

Abstract

Here is presented a 6-states non minimal-time solution which is intrinsically Minsky-like and solves the three following problems: unrestricted version on a line, with one initiator at each end of a line and the problem on a ring. We also give a complete proof of correctness of our solution, which was never done in a publication for Minsky's solutions.

Keywords

Firing squadsynchronization
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 42 , Issue 1: A nonstandard spirit among computer scientists:a tribute to Serge Grigorieff at the occasion of his 60th birthday , January 2008 , pp. 55 - 68
Copyright
© EDP Sciences, 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Balzer, R., An 8-state minimal time solution to the firing squad synchronization problem. Inform. Control 10 (1967) 22–42. CrossRef
J. Duprat, Proof of correctness of the Mazoyer's solution of the firing squad problem in Coq. http://hdl.handle.net/2332/792 (2002).
E. Goto, A Minimum Time Solution of the Firing Squad Problem. Course Notes for Applied Mathematics 298, Harvard University (1962).
Grigorieff, S., Synchronization of a bounded degree graph of cellular automata with non uniform delays in time $\delta\lfloor \log_m(\delta)\rfloor$ . Theor. Comput. Sci. 356 (2006) 170–185. CrossRef
Jiang, T., The synchronization of non-uniform networks of finite automata. Inform. Control 97 (1992) 234–261.
Kobayashi, K., The firing squad synchronization problem for a class of polyautomata networks. J. Comput. Syst. Sci. 17 (1978) 300–318. CrossRef
M. Kutrib and R. Vollmar, The firing squad synchronization problem in defective cellular automata. IEICE T. Inf. Syst. E78-D (1995) 895–900.
Mazoyer, J., A six-state minimal time solution to the firing squad synchronization problem. Theor. Comput. Sci. 50 (1987) 183–238. CrossRef
J. Mazoyer, A Minimal Time Solution to the Firing Squad Synchronization Problem with Only One Bit of Information Exchanged. Rapport Technique LIP 89.03, École Normale Supérieure de Lyon (1989).
M. Minsky, Computation: Finite and Infinite Machines. Prentice-Hall (1967).
E.F. Moore, The Firing Squad Synchronization Problem, in Sequential Machines. Selected Papers, edited by E.F. Moore Addison-Wesley, Reading MA (1964) 213–214.
Noguchi, K., Simple 8-state minimal time solution to the firing squad synchronization problem. Theor. Comput. Sci. 314 (2004) 303–334. CrossRef
L. Pierre, Private communication.
Róka, Z., The firing squad synchronization problem on Cayley graphs. Theor. Comput. Sci. 244 (2000) 243–256. CrossRef
Romani, F., Cellular Automata Synchronization. Inform. Sciences 10 (1976) 299–318. CrossRef
P. Rosensthiel, J. Fiksel and A. Holliger, Intelligent Graphs: Networks of Finite Automata Capable of Solving Graph Problems, in Graph Theory and Computing, edited by R.C. Read, Academic Press (1972).
Settle, A. and Simon, J., Smaller solutions for the firing squad. Theor. Comput. Sci. 276 (2002) 83–109. CrossRef
Shinahr, I., Two and three dimensional firing squad synchronization problem. Inform. Control 24 (1974) 163–180. CrossRef
Szwerinski, H., Time-optimal solution of the firing squad synchronization problem for n-dimensional rectangles with the general at an arbitrary position. Theor. Comput. Sci. 19 (1982) 305–320. CrossRef
H. Umeo, An Efficient Design of Two-Dimensional Firing Squad Synchronization Problem. Eighth International Workshop on Cellular Automata, Prague, Czechia (2002).
H. Umeo, A simple design of time-efficient firing squad synchronization algorithms with fault-tolerance. IEICE T. Inf. Syst. E87-D(3) (2004).
Umeo, H., Maeda, M. and Hongyo, K., A design of symmetrical six-state 3n-step firing squad synchronization algorithms and their implementations. Proceedings of ACRI. Lect. Notes Comput. Sci. 4173 (2006) 157–168. CrossRef
Waksman, A., An optimum solution to the firing squad synchronization. Probl. Inf. Control 9 (1966) 66–78. CrossRef
Yunès, J.-B., Seven states solutions to the firing squad synchronization. Probl. Theor. Comput. Sci. 127 (1994) 313–332. CrossRef
Yunès, J.-B., Fault tolerant solutions to the firing squad synchronization problem in linear cellular automata. J. Cell. Automata 1 (2006) 253–268.