A Stochastic Model of Self-Stabilizing Cellular Automata for Consensus Formation

In this paper we present a model of the dynamics of an interesting class of stochastic cellular automata. Such automata are variants of automata used for density classification and they are chosen because they can be effectively used to address consensus problems. After introducing the topic and the basic notation, we study the dynamics of such automata by means of simulations with varying periods and neighborhood structures. We use the results of simulations to extrapolate a stochastic model of the dynamics of such automata that can be used to estimate stabilization time.