Complex Systems

Self-Stabilizing Distributed Algorithms by Gellular Automata Download PDF

Taiga Hongu
Masami Hagiya

The University of Tokyo
Tokyo, Japan


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.