Self-Stabilizing Distributed Algorithms by Gellular Automata
- 15 June 2021
- journal article
- research article
- Published by Wolfram Research, Inc. in Complex Systems
- Vol. 30 (2), 159-185
- https://doi.org/10.25088/complexsystems.30.2.159
Abstract
Gellular automata are cellular automata with the properties of asynchrony, Boolean totality and noncamouflage. In distributed computing, it is essential to determine whether problems can be solved by self-stable gellular automata. From any initial configuration, self-stable gellular automata converge to desired configurations, as self-stability implies the ability to recover from temporary malfunctions in transitions or states. This paper shows that three typical problems in distributed computing, namely, solving a maze, distance-2 coloring and spanning tree construction, can be solved with self-stable gellular automata.Keywords
This publication has 5 references indexed in Scilit:
- Turing-completeness of asynchronous non-camouflage cellular automataInformation and Computation, 2020
- Self-stabilizing Gellular AutomataPublished by Springer Science and Business Media LLC ,2019
- Pattern Formation on Discrete Gel Matrix Based on DNA ComputingNew Generation Computing, 2018
- Turing-Completeness of Asynchronous Non-camouflage Cellular AutomataLecture Notes in Computer Science, 2017
- Emulating cellular automata in chemical reaction–diffusion networksNatural Computing, 2015