Simulating Population Protocols by Gellular Automata
Tatsuya Yamashita, Masami Hagiya · 2018
In our previous research, we studied the computational universality of gellular automata, a variant of asynchronous cellular automata that are intended to be realized by a reaction-diffusion system in a gel material. In this paper, we characterize the computational power of gellular automata as a model of distributed computations by presenting gellular automata that simulate a population protocol on an undirected graph. We also show that such gellular automata can be embedded into a lattice space if the interaction graph of the population protocol is planar. These results demonstrate the versatility of gellular automata as a model of distributed computations.