A State-Efficient Mapping Scheme for Designing Two-Dimensional Firing Squad Synchronization Algorithms

• Autorzy: Umeo H. , Maeda M. , Hisaoka M. , Teraoka M.
• Języki publikacji: EN

Abstrakty

EN

A simple and state-efficient mapping scheme is proposed for embedding any one-dimensional (1-D) firing squad synchronization algorithm onto two-dimensional (2-D) arrays, and some new 2-D synchronization algorithms based on the mapping scheme are presented. The proposed mapping scheme can be readily applied to the design of 2-D synchronization algorithms with fault tolerance, algorithms operating on multi-dimensional cellular arrays, and for the generalized case where the general is located at an arbitrary position on the 2-D array. First a six-state algorithm is developed that can synchronize any m ×n rectangular array in 2(m + n) - 4 steps. Then, a fourteen-state generalized algorithm is also developed that can synchronize any m×n rectangular array with the general at an arbitrary initial position (r, s) in m + n + max(r + s , m + n - r - s+ 2) - 4 steps. The latter algorithm is interesting in that it includes a new optimum-time synchronization algorithm as a special case where the general is located at one corner. We progressively reduce the number of internal states of each cellular automaton on rectangular arrays, achieving six states and fourteen states for a rectangular array in non-optimum and optimum-time complexities, respectively. These are the smallest number of states reported to date for synchronizing rectangular arrays.

Słowa kluczowe

EN

cellular automata; firing squad synchronization problem; fault-tolerant synchronization algorithm

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 74, nr 4
• Strony: 603--623
• Opis fizyczny: bibliogr. 26 poz., tab., wykr.

Twórcy

autor

Umeo H.

autor

Maeda M.

autor

Hisaoka M.

autor

Teraoka M.

• Faculty of Information Science and Technology, Osaka Electro-Communication University, Neyagawa-shi, Hatsu-cho, 18-8, Osaka, 572-8530, Japan,

Bibliografia

• [1] R. Balzer: An 8-state minimal time solution to the firing squad synchronization problem. Information and Control, vol. 10(1967), pp. 22-42.
• [2] A. Berthiaume, T. Bittner, L. Perkovi´c, A. Settle and J. Simon. (2004): Bounding the firing synchronization problem on a ring. Theoretical Computer Science, 320, pp. 213-228.
• [3] W. T. Beyer: Recognition of topological invariants by iterative arrays. Ph.D. Thesis, MIT, (1969), pp. 144.
• [4] E. Goto: A minimal time solution of the firing squad problem. Dittoed course notes for Applied Mathematics 298, Harvard University, (1962), pp. 52-59, with an illustration in color.
• [5] A. Grasselli: Synchronization of cellular arrays: The firing squad problem in two dimensions. Information and Control, vol. 28(1975), pp. 113-124.
• [6] J. J. Grefenstette: Network structure and the firing squad synchronization problem. J. of Computer and System Sciences, vol.26(1983), pp.139-152.
• [7] K. Kobayashi: The firing squad synchronization problem for two-dimensional arrays. Information and Control, vol. 34(1977), pp. 177-197.
• [8] M. Kutrib and R. Vollmar: The firing squad synchronization problem in defective cellular automata. Trans. of IEICE on Inf. and Syst., vol. E78-D, No. 7(1995), pp. 895-900.
• [9] J. Mazoyer: An overview of the firing squad synchronization problem. Lecture Notes on Computer Science, Springer-Verlag, vol. 316(1986), pp. 82-93.
• [10] J. Mazoyer: A six-state minimal time solution to the firing squad synchronization problem. Theoretical Computer Science, vol. 50(1987), pp. 183-238.
• [11] M. Minsky: Computation: Finite and infinite machines. Prentice Hall, (1967), pp. 28-29.
• [12] E. F. Moore: The firing squad synchronization problem. in Sequential Machines, Selected Papers (E. F. Moore ed.), Addison-Wesley, Reading MA., (1964), pp. 213-214.
• [13] F. R. Moore and G. G. Langdon: A generalized firing squad problem. Information and Control, vol. 12(1968), pp. 212-220.
• [14] H. B. Nguyen and V. C. Hamacher: Pattern synchronization in two-dimensional cellular space. Information and Control, vol. 26(1974), pp, 12-23.
• [15] H. Schmid and T. Worsch: The firing squad synchronization problem with many generals for one-dimensional CA. Proc. of IFIP World Computer Congress, 2004, pp.14.
• [16] A. Settle and J. Simon. (2002): Smaller solutions for the firing squad. Theoretical Computer Science, 276, 83-109.
• [17] I. Shinahr: Two- and three-dimensional firing squad synchronization problems. Information and Control, vol. 24(1974), pp. 163-180.
• [18] H. Szwerinski: Time-optimum solution of the firing-squad-synchronization-problem for n- dimensional rectangles with the general at an arbitrary position. Theoretical Computer Science, vol. 19(1982), pp. 305-320.
• [19] H. Umeo: A simple design of time-efficient firing squad synchronization algorithms with fault-tolerance. IEICE Trans. on Information and Systems, Vol. E87-D, No.3, 2004, pp.733-739.
• [20] H. Umeo, T. Sogabe and Y. Nomura: Correction, optimization and verification of transition rule set for Waksman's firing squad synchronization algorithms. Proc. of the 4th International Conference on Cellular Automata for Research and Industry, 2000, pp. 152-160.
• [21] H. Umeo, M. Hisaoka and T. Sogabe: A survey on optimum-time firing squad synchronization algorithms for one-dimensional cellular automata. Intern. J. of Unconventional Computing, 2005, vol. 1, pp.403-426.
• [22] H. Umeo, M. Hisaoka, M. Teraoka and M. Maeda: Several new generalized linear- and optimum-time synchronization algorithms for two-dimensional rectangular arrays. Proc. of 4th International Conference on Machines, Computations and Universality : MCU 2004, LNCS 3354 (M. Margenstern(Ed.), (2005), pp.223-232.
• [23] V. I. Varshavsky: Synchronization of a collection of automata with random pairwise interaction. Autom. and Remote Control, vol. 29(1969), pp. 224-228.
• [24] V. I. Varshavsky, V. B. Marakhovsky and V. A. Peschansky: Synchronization of interacting automata. Mathematical Systems Theory, Vol. 4, No. 3(1970), pp. 212-230.
• [25] R. Vollmar: Algorithmen in Zellularautomaten. Teubner, pp. 192, 1979.
• [26] A. Waksman: An optimum solution to the firing squad synchronization problem. Information and Control, vol. 9(1966), pp. 66-78.