Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
A Snapshot of My Life Read chapter Read first chapter

2018 | OriginalPaper | Chapter

FSSP Algorithms for 2D Rectangular Arrays. Recent Developments

Author : Hiroshi Umeo

Published in: Reversibility and Universality

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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 the 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 this article, we give a survey on a class of minimum-time FSSP algorithms for two-dimensional (2D) rectangular arrays. The algorithms discussed here are all based on an L-shaped mapping, where the synchronized configurations on 1D arrays are mapped efficiently onto a 2D array in an L-shaped form, yielding a 2D minimum-time FSSP algorithm.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter A Snapshot of My Life
next chapter Abelian Invertible Automata
Literature
1.
Beyer, W.T.: Recognition of topological invariants by iterative arrays. Ph.D. Thesis, MIT, pp. 144 (1969)
2.
Moore, E.F.: The firing squad synchronization problem. In: Moore, E.F. (ed) Sequential Machines, Selected Papers, pp. 213–214. Addison-Wesley, Reading MA (1964)
3.
Moore, F.R., Langdon, G.G.: A generalized firing squad problem. Inf. Control 12, 212–220 (1968)CrossRefMATH
4.
5.
Umeo, H.: A simple design of time-efficient firing squad synchronization algorithms with fault-tolerance. In: IEICE Transactions on Information and Systems, vol. E87-D (3), pp. 733–739 (2004)
6.
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, Berlin (2009). A new edition will appear in 2020
7.
8.
Umeo, H., Ishida, K., Tachibana, K., Kamikawa, N.: A transition rule set for the first 2-D optimum-time synchronization algorithm. In: Proceedings of the 4th International Workshop on Natural Computing, PICT, vol. 2, pp. 333–341. Springer, Berlin (2009)
9.
Umeo, H., Kamikawa, N., Nishioka, K., Akiguchi, S.: Generalized firing squad synchronization protocols for one-dimensional cellular automata - a survey. In: Acta Physica Polonica B, Proceedings Supplement. vol. 3, pp.267–289 (2010)
10.
Umeo, H., Kubo, K.: A seven-state time-optimum square synchronizer. In: Proceedings of International Conference on Cellular Automata for Research and Industry, ACRI 2010, LNCS, vol. 6350, pp. 219–230 (2010)
11.
Umeo, H., Kubo, K., Nishide, K.: A class of FSSP algorithms for multi-dimensional cellular arrays. Commun. Nonlinear Sci. Numer. Simul. 21, 200–209 (2015)MathSciNetCrossRefMATH
12.
Umeo, H. Kubo, K., Takahashi, Y.: An isotropic optimum-time FSSP algorithm for two-dimensional cellular automata. In: Proceedings of the 12th International Conference on Parallel Computing Technologies, PaCT 2013, LNCS, vol. 7979, pp. 381–393 (2013)
13.
Umeo, H., Nomura, A.: A state-efficient zebra-like implementation of synchronization algorithms for 2D rectangular cellular arrays. In: BIOMATH, vol. 1, pp. 1–6 (2012)
14.
Umeo, H., Uchino, H.: A new time-optimum synchronization algorithm for rectangle arrays. Fundam. Inform. 87(2), 155–164 (2008)MathSciNetMATH
15.
Umeo, H., Yamawaki, T., Nishide, K.: An optimum-time firing squad synchronization algorithm for two-dimensional rectangle arrays –freezing-thawing technique based. J. Cell. Autom. 7, 31–46 (2012)MathSciNetMATH
16.
Umeo, H. Yunès, J.-B., Yamawaki, T.: A simple-optimum-time firing squad synchronization algorithms for two-dimensional arrays. In: Proceedings of 2009 International Conference on Computational Intelligence, Modelling and Simulation, CSSim 2009, IEEE Computer Society, pp. 120–125 (2009)
Metadata
Title
FSSP Algorithms for 2D Rectangular Arrays. Recent Developments
Author
Hiroshi Umeo
Copyright Year
2018
Book
Reversibility and Universality

Print ISBN: 978-3-319-73215-2

Electronic ISBN: 978-3-319-73216-9

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-3-319-73216-9_2

Premium Partner

    Image Credits