Self-stabilisation of Cellular Automata on Tilings

• Autorzy: Fatès Nazima , Marcovici Irèneb , Taati Siamak

Identyfikatory

DOI

10.3233/FI-222103

• Języki publikacji: EN

Abstrakty

EN

Given a finite set of local constraints, we seek a cellular automaton (i.e., a local and uniform algorithm) that self-stabilises on the configurations that satisfy these constraints. More precisely, starting from a finite perturbation of a valid configuration, the cellular automaton must eventually fall back into the space of valid configurations where it remains still. We allow the cellular automaton to use extra symbols, but in that case, the extra symbols can also appear in the initial finite perturbation. For several classes of local constraints (e.g., k-colourings with k ≠ 3, and North-East deterministic constraints), we provide efficient self-stabilising cellular automata with or without additional symbols that wash out finite perturbations in linear or quadratic time, but also show that there are examples of local constraints for which the self-stabilisation problem is inherently hard. We note that the optimal self-stabilisation speed is the same for all local constraints that are isomorphic to one another. We also consider probabilistic cellular automata rules and show that in some cases, the use of randomness simplifies the problem. In the deterministic case, we show that if finite perturbations are corrected in linear time, then the cellular automaton self-stabilises even starting from a random perturbation of a valid configuration, that is, when errors in the initial configuration occur independently with a sufficiently low density.

Słowa kluczowe

EN

tilings; shifts of finite type; cellular automata; self-stabilisation; noise; fault-tolerance; reliable computing; symbolic dynamics

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: Vol. 185, nr 1
• Strony: 27--82
• Opis fizyczny: Bibliogr.37 poz., rys.

Twórcy

autor

Fatès Nazima

• Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, Frances

autor

Marcovici Irèneb

• Université de Lorraine, CNRS, Inria, IECL, F-54000 Nancy, France.

autor

Taati Siamak

• Department of Mathematics, American University of Beirut, Beirut, Lebanon

Bibliografia

• [1] Dijkstra EW. Self-stabilizing systems in spite of distributed control. Communications of the ACM, 1974.17(11):643-644. doi:10.1145/361179.361202
• 2] Dolev S. Self-Stabilization. MIT Press, 2000. ISBN:9780262041782.
• [3] Altisen K, Devismes S, Dubois S, Petit F. Introduction to Distributed Self-Stabilizing Algorithms. Morgan & Claypool Publishers, 2019. doi:10.2200/S00908ED1V01Y201903DCT015.
• [4] Toom AL. Nonergodic Multidimensional System of Automata. Problems of Information Transmission,1974. 10(3):239-246.
• [5] Toom AL. Stable and attractive trajectories in multicomponent systems. In: Dobrushin RL, Sinai YG (eds.), Multicomponent Random Systems, pp. 549-575. Marcel Dekker. ISBN:9780824768317, 1980.
• [6] Gács P, Reif J. A simple three-dimensional real-time reliable cellular array. Journal of Computer and System Sciences, 1988. 36(2):125-147. doi:10.1016/0022-0000(88)90024-4.
• [7] Gács P. Reliable computation with cellular automata. Journal of Computer and System Sciences, 1986. 32(1):15-78. doi:10.1016/0022-0000(86)90002-4.
• [8] Gács P. Reliable cellular automata with self-organization. Journal of Statistical Physics, 2001. 103(1-2):45-267. doi:10.1023/A:1004823720305.
• [9] Bušić A, Fatès N, Mairesse J, Marcovici I. Density classification on infinite lattices and trees. Electronic Journal of Probability, 2013. 18:51. doi:10.1214/EJP.v18-2325.
• [10] de Oliveira PPB. On Density Determination With Cellular Automata: Results, Constructions and Directions. Journal of Cellular Automata, 2014. 9(5-6):357-385.
• [11] Richard G. On the Synchronisation Problem over Cellular Automata. In: Vollmer H, B Vallée (eds.), Proceedings of STACS 2017, volume 66 of LIPIcs. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017 pp. 54:1-54:13. doi:10.4230/LIPIcs.STACS.2017.54.
• [12] Fatès N. Remarks on the cellular automaton global synchronisation problem: deterministic versus stochastic models. Natural Computing, 2019. 18(3):429-444. URL https://hal.inria.fr/hal-01653631.
• [13] Fatès N, Marcovici I, Taati S. Cellular automata for the self-stabilisation of colourings and tilings. In: Reachability Problems, volume 11674 of Lecture Notes in Computer Science, pp. 121-136. Springer, 2019. doi:10.1007/978-3-030-30806-3 10.
• [14] Gács P, Kurdyumov GL, Levin LA. One-dimensional uniform arrays that wash out finite islands. Problems of Information Transmission, 1978. 14(3):223-226.
• [15] Gonzaga de Sá P, Maes C. The Gacs–Kurdyumov–Levin Automaton Revisited. Journal of Statistical Physics, 1992. 67(3/4):507-522. doi:10.1007/BF01049718.
• [16] Kari J, Le Gloannec B. Modified traffic cellular automaton for the density classification task. Fundamenta Informaticae, 2012. 116(1–4):141-156. doi:10.3233/FI-2012-675.
• [17] Maass A. On the sofic limit sets of cellular automata. Ergodic Theory and Dynamical Systems, 1995. 15(4):663-684. doi:10.1017/S0143385700008609.
• [18] TörmäI. Personal communication.
• [19] Toom AL, Vasilyev NB, Stavskaya ON, Mityushin LG, Kuryumov GL, Pirogov SA. Discrete local Markov systems. In: Dobrushin RL, Kryukov VI, Toom AL (eds.), Stochastic cellular systems: ergodicity, memory, morphogenesis. Manchester University Press. 1990. ISBN:9780719022067.
• [20] Marcus B, Pavlov R. An integral representation for topological pressure in terms of conditional probabilities. Israel Journal of Mathematics, 2015. 207(1):395-433.
• 21] Briceño R, Pavlov R. Strong Spatial Mixing in Homomorphism Spaces. SIAM Journal on Discrete Mathematics, 2017. 31(3):2110-2137. doi:10.1137/16M1066178.
• [22] Chandgotia N, Marcus B. Mixing properties for hom-shifts and the distance between walks on associated graphs. Pacific Journal of Mathematics, 2018. 294(1):41-69. doi:10.2140/pjm.2018.294.41.
• [23] Alon N, Briceño R, Chandgotia N, Magazinov A, Spinka Y. Mixing properties of colorings of the Zd lattice. Combinatorics, Probability and Computing, 2021. 30(3):360-373. doi:10.1017/S0963548320000395.
• [24] Berger R. The undecidability of the domino problem. Memoirs of the American Mathematical Society, 1966. 66.
• [25] Robinson RM. Undecidability and nonperiodicity for tilings of the plane. Inventiones Mathematicae, 1971. 12:177-209. doi:10.1007/BF01418780.
• [26] Grünbaum B, Shephard GC. Tilings and Patterns. W. H. Freeman and Co., 1987. ISBN:978-0-7167-1193-3.
• [27] Kari J. The Nilpotency Problem of One-Dimensional Cellular Automata. SIAM Journal on Computing, 1992. 21(3):571-586. doi:10.1137/0221036.
• [28] Lukkarila V. The 4-way deterministic tiling problem is undecidable. Theoretical Computer Science, 2009. 410(16):1516-1533. doi:10.1016/j.tcs.2008.12.006.
• [29] Pippenger N. Symmetry in self-correcting cellular automata. Journal of Computer and System Sciences, 1994. 49(1):83-95.
• [30] Fontes LR, Schonmann RH, Sidoravicius V. Stretched exponential fixation in stochastic Ising models at zero temperature. Communications in Mathematical Physics, 2002. 228:495-518. doi:10.1007/s002200200658.
• [31] Eisenberg B. On the expectation of the maximum of IID geometric random variables. Statistics & Probability Letters, 2008. 78(2):135-143. doi:10.1016/j.spl.2007.05.011.
• [32] Fatès N. A tutorial on elementary cellular automata with fully asynchronous updating. Natural Computing, 2020. 19(1):179-197. doi:10.1007/s11047-020-09782-7.
• [33] Lind D, Marcus B. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, 1995. ISBN:0-521-55124-2.
• [34] Durand B, Romashchenko A, Shen A. Fixed-point tile sets and their applications. Journal of Computer and System Sciences, 2012. 78(3):731-764. doi:10.1016/j.jcss.2011.11.001.
• [35] Taati S. Restricted density classification in one dimension. In: Kari J (ed.), Proceedings of AUTOMATA 2015, volume 9099 of LNCS. Springer, 2015 pp. 238-250. doi:10.1007/978-3-662-47221-7 18.
• [36] Çapuni I, Gács P. A reliable Turing machine, August 9, 2021. URL https://www.cs.bu.edu/fac/gacs/.
• [37] Baxter R. Exactly Solved Models in Statistical Mechanics. Academic Press, 1982. ISBN:0-12-083180-5

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023). (PL)