Self-Stabilizing Distributed Algorithms by Gellular Automata
Taiga Hongu
Masami Hagiya
The University of Tokyo
Tokyo, Japan
hongu314@g.ecc.u-tokyo.ac.jp
hagiya@is.s.u-tokyo.ac.jp
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: gellular automata; solving a maze; distance-2 coloring; spanning tree construction; self-stability
Cite this publication as:
T. Hongu and M. Hagiya, “Self-Stabilizing Distributed Algorithms by Gellular Automata,” Complex Systems, 30(2), 2021 pp. 159–185.
https://doi.org/10.25088/ComplexSystems.30.2.159
