This project investigates the robustness of one-dimensional consensus-based cellular automata under the influence of noise. Specifically, it aims to determine the noise threshold beyond which global consensus fails to emerge. Remarkably, when the initial density of red squares is 50%, the system exhibits behavior reminiscent of a critical point, making it natural to analyze such a problem within the framework of critical phenomena. The impact of inserting random noise on each step was investigated in terms of the noise-threshold to achieve consensus, as well as the impact of scaling the system size. By deepening the fundamental understanding of phase transition- and critical behaviors in cellular automata, the present study may offer valuable insights into consensus-based mechanisms, being blockchain technology a natural example.

Introduction and motivation

Cellular automata (CA) are discrete, computational platforms that have proved to be remarkably powerful in modeling complex behaviors using simple rules. Introduced by John von Neumann in the 1940s to study self-replicating systems, CA consist of a grid of cells, each of which can adopt a finite number of states and evolve over time according to a set of deterministic or probabilistic rules based on the states of neighboring cells. One of the most iconic examples is Stephen Wolfram’s classification of elementary cellular automata, which revealed that even extremely simple systems (like Rule 30 or Rule 110) can generate patterns exhibiting randomness, self-organization, and even universal computation capabilities [1]. The importance of cellular automata extends far beyond pure mathematics or computer science. In Physics, CA have been employed to study non-equilibrium phase transitions, fluid dynamics through lattice gas automata, and even phenomena like pattern formation and domain growth in spin systems [2]. In Biology, CA have been employed to model morphogenesis, population dynamics, and the spread of diseases, due to their ability to capture local interactions and emergent global behavior [3]. Furthermore, CA have gained renewed interest in the era of decentralized computing and complex systems science. Their rule-based, local-update nature makes them ideal for parallel computation and for modeling systems where global behavior emerges from local rules.
​
Next, we discuss local and full consensus in terms of cellular automata. Figure 1 shows a typical example of a local consensus, i.e., after a few steps the cellular automata does not achieve a line with either full red or yellow squares.
Out[]=
​
Red cell %
0.7
Figure 1 – Manipulate plot of the time evolution of Rule 232 cellular automaton. The initial density of red cells can be changed.
No full consensus is achieved in this way for any 0 < p < 1, only the so-called local consensus. Below, an example considering both 40% (p = 0.4) and 60% (p = 0.6) of initially red cells considered in the 7 neighborhoods rule [1]:
Out[]=
Out[]=
In both cases of Fig. 2 and 3, full consensus is achieved, i.e., a final line with either full yellow or red squares is obtained after a given number of steps. Consensus can be also visualized in terms of average density versus steps (time) for distinct initial densities, namely [4]:
Out[]=
Upon considering the the result for p = 0.5, we observe that the average density is constant and no consensus is achieved, which perfectly describes the situation in which the system “can’t make up its mind”. The latter presents a critical point behavior [5-8]. To observe this behavior in terms of a cellular automaton diagram, we need to sum up the results for p = 0.5, so that:
Out[]=
​
p
0.5
Figure 5 – Manipulative plot of the superposition of 100 space-time evolutions of a 7 neighbor cellular automaton for a given initial density p. Note that for p = 0.5, there is no consensus of either yellow or red color.
It becomes evident that, right at p = 0.5, no consensus is achieved even for a large number of steps, which is in-line with a constant average density shown in Fig. 4. Next, in order to check for the role played by noise level added into the system, a random noise is added into the CA. To do that, after applying the rule to the CA, a random number of squares have their colors flipped, i.e., if the chosen squares are red they become yellow and vice versa. The number of squares flipped n depend on the noise level ε and the CA length L by the form:
n=ε*L.(1)
If ε is set to be 0.05 and l = 100, for instance, 5 squares will have their color flipped on each step. More details can be found in Ref. [4]. Upon analyzing the average density in terms of the noise level and the initial density, a phase diagram can be obtained, which resembles the one for a critical point [5-10]:
Out[]=
Upon analyzing Fig.6, one can notice that there are clear regions that consensus is fully or locally achieved, but for a high noise level, no consensus is reached. Local consensus can be understood in terms of having a final density that is close to but not exactly 0 or 1. An example is found below:
Out[]=
It becomes evident that for p = 0.4 with noise, the average density converges to a value close to 0 but not exactly zero, so that it can be defined as local consensus. Hence, the goal of this project is to investigate the robustness of CA to random noise strength, which will be explored in the following.

Results

Consensus threshold

To investigate the robustness of the CA to reach consensus, we can first determine the threshold at which consensus is achieved. For doing that, a simple algorithm can be written so that it highlights the final average densities below or above a certain pre-determined value.
We can start by considering three cases at which consensus is reached, namely when the average density is: i) < 0.1 or > 0.9; ii) < 0.05 or > 0.95; and iii) < 0.03 or > 0.97.
The results clearly show that, depending on the criteria to achieve consensus, clear lines separating the consensus to no consensus regions are indicated. We can also explore how consensus is affected upon skipping the addition of noise in the first steps.
The results shown in Fig. 9 demonstrate that the initial condition is key for determining how fast consensus is achieved. For the case with noise at every step, consensus is achieved later than the one with noise added after step 5, both CAs achieving an average density close to zero after a few steps. However, for the case of noise every step, a remarkable situation was found. After a high number of steps, the systems flipped to an average density 0 to 1. Such a behavior is, however, suppressed upon increasing the system’s length. This is an interesting situation because it seems consensus is step-dependent and even though the CA seem to be converged, it might suddenly flip its consensus considering long time (step) scales.

Information entropy and consensus

Thus, since there are only two states, namely red and yellow, S can be straightforwardly computed employing the following protocol:
◼
  • The CA rule is applied for a particular value of initial density and, in each step, noise is added depending on the considered noise level, following Eq. (1);
    • ◼
  • After computing for all considered steps, the average density is achieved for that particular initial density and noise level considered;
    • ◼
  • Based on the final average density, entropy is computed in terms of the probability of each red and yellow squares employing Eq. (2);
    • ◼
  • Such a calculation is repeated for several initial densities and averaged over many runs for smoothing, resulting in the average entropy versus initial density for particular values of noise level, which is shown below.
    • Upon analyzing the behavior of the average entropy versus initial density for various noise levels in Fig. 10, one can infer that average entropy is maximized right at p = 0.5, i.e., at the “critical point”. Upon increasing ε, the average entropy variation is suppressed meaning that the CA is being tuned away from the critical point.
    Figure 11 shows the averaged entropy versus initial density for distinct noise levels on top of the plane formed by the initial density and the noise level, i.e., the phase diagram depicted in Fig. 6. Note that upon increasing the noise level the maximum of the averaged entropy is suppressed since the CA is away from the critical point and noise level is so high that no consensus is achieved.
    Figure 12 depicts a density plot of the average entropy versus noise level versus initial density. For zero noise level, entropy is maximized right at the critical point. However, upon increasing the noise level right at p = 0.5, entropy increases because of the inherent mixing between the two states, eventually reaching a constant value for high noise level. Next, we analyse the behavior of the average upon increasing the system size right at the critical point.

    Size-effects in average entropy

    Upon increasing the size of the 1D CA without noise, the entropy is maximized and pinned at p = 0.5 and it increases upon increasing the length.

    Concluding Remarks

    The 1D CA for rule 625 with random noise introduced at every step is governed by a critical point that makes consensus to be achieved only away from it. The determination of the threshold lines for achieving consensus or local consensus was made, so that it can be tuned depending on the desired consensus threshold. The average entropy is maximized right at the critical point due to the competition between the two phases, preventing thus consensus to be achieved in the vicinity of the critical point. Upon increasing the system length, the average entropy is also increased due to more states being available with their corresponding probabilities. The present work unveils the entropic landscape around the critical point in order to optimize the achievement of consensus in CA-based systems, which is particularly important to blockchain technologies.

    Acknowledgments

    I would like to express my sincere gratitude to my post-doc supervisor Prof. Dr. Mariano de Souza from the São Paulo State University for his huge support, as well as for the insightful discussions and valuable proposals regarding this project. I am also thankful to my mentor, Rafael Caballero, for his continuous support. My special thanks to Stephanie Bowyer for her key-role in helping me secure the financial support necessary to attend the Wolfram Summer School, and for always being ready to assist me in every possible way. I am also grateful to Daniel Carvalho, Bowen Ping, and Tarang Janawalkar for their valuable assistance with coding-related matters. Last but not least, I extend my deeply appreciation to Stephen Wolfram and the entire Wolfram staff for providing such a transformative, life-changing experience, which I am sure will resonate with me for many years.

    References

    1
    .
    S. Wolfram, A new kind of Science (Wolfram Media Inc., 2002).
    2
    .
    B. Chopard, M. Droz, Cellular Automata Modeling of Physical Systems (Cambridge University Press, 1998).
    3
    .
    G.B. Ermentrout, L. Edelstein-Keshet, Journal of Theoretical Biology 160, 97 (1993).
    4
    .
    S. Wolfram (2021), "The Problem of Distributed Consensus,” Stephen Wolfram Writings. writings.stephenwolfram.com/2021/05/the-problem-of-distributed-consensus.
    5
    .
    H.E. Stanley, Introduction to phase transitions and critical phenomena (Oxford University Press, 1987).
    6
    .
    L. Bartosch, M. de Souza, M. Lang, Physical Review Letters 104, 245701 (2010).
    7
    .
    S.M. Soares, L. Squillante, H.S. Lima, C. Tsallis, M. de Souza Physical Review B 111, L060409 (2025).
    8
    .
    L. Squillante, L.S. Ricco, A.M. Ukpong, R.E. Lagos-Monaco, A.C. Seridonio, M. de Souza, Physical Review B 108, L140403 (2023).
    9
    .
    L. Squilllante, I. F. Mello, A.C. Seridonio, M. de Souza, Materials Research Bulletin 142, 111413 (2021).
    10
    .
    L. Squillante, I.F. Mello, G.O. Gomes, A.C. Seridonio, R.E. Lagos-Monaco, H.E. Stanley, M. de Souza, Scientific Reports 10, 7981 (2020).
    11
    .
    J. von Neumann, Mathematische Grundlagen der Quantenmechanik (Springer, 1932).

    Cite This Notebook

    Critical Behavior and Noise Threshold in Consensus-Based Cellular Automata​
    by Lucas Squillante​
    Wolfram Community, STAFF PICKS, July 9, 2025
    ​https://community.wolfram.com/groups/-/m/t/3497150