Distributed Consensus with Cellular Automata & Related Systems Research Conference
What this covers
Begins at 3:09 This conference will be of interest to those interested in the leading edge of blockchain algorithms and their connection to areas such as physics, complex systems, discrete mathematics and computation theory. Agenda for the event found here: https://www.wolfram.com/events/distributed-consensus/agenda/
Outline of Conference 0:00 Stream starts 3:09 Jon Woodard gives an intro 3:47 Stephen begins his opening keynote 1:11:06 Yilun Zhang gives his keynote 1:40:21 Pedro Paulo Balbi presentation 2:10:15 Part 1 of Q&A 2:41:06 Vero Estrada-Galiñanes presentation 3:24:48 Henryk Fukś presentation 4:03:19 William Sanders presentation 4:33:06 Part 2 of Q&A 4:55:04 Intermission... 5:07:44 Christian Pasquel resumes the stream 5:08:01 Peter Gacs presentation 5:45:19 Eric Goles presentation 6:14:51 Emin Gün Sirer presentation 6:54:42 Aaron Schutza presentation 7:29:50 Part 3 of Q&A
Some topics and approaches involved: Graph Cellular Automata, Probabilistic Cellular Automata, Fault-Tolerant Cellular Automata, Voter Models, Directed Percolation, Spin Systems, Phase Transitions, Byzantine Attacks, Statistical Physics, Discrete Mathematics, Computational Experiments, Computation Theory, Dynamical Systems Theory, Distributed Algorithms, Randomized Algorithm, Adaptive Algorithms Automated Theorem Proving, Error Correction
Invited Speakers: Stephen Wolfram (Keynote), Yilun Zhang, Cofounder & CTO, NKN Labs (Keynote), Pedro Paulo Balbi Professor at the School of Computing and Informatics, Mackenzie University (Brazil), Vero Estrada-Galiñanes Associate Professor of Science and Technology, University of Stavanger (Norway/Switzerland), Henryk Fukś Professor of Mathematics, Brock University (Canada), Peter Gacs Boston University (USA), Eric Goles Professor of Theoretical Computer Science, Adolfo Ibañez University (Chile), William Sanders Director of Research, IOTA Foundation, Aaron Schutza Director of Research, Topl (USA) and Emin Gün Sirer Founder & CEO, AVA Labs & Associate Professor of Computer Science, Cornell University (USA)
A Bibliography of Distributed Consensus with Cellular Automata & Related Systems: https://www.wolframcloud.com/obj/sw-writings/DistributedConsensus/bibliography.pdf
The Problem of Distributed Consensus: https://writings.stephenwolfram.com/2021/05/the-problem-of-distributed-consensus/
Follow us on our official social media channels.
Twitter: https://twitter.com/WolframResearch/ Facebook: https://www.facebook.com/wolframresearch/ Instagram: https://www.instagram.com/wolframresearch/ LinkedIn: https://www.linkedin.com/company/wolfram-research/
Contribute to the official Wolfram Community: https://community.wolfram.com/ Stay up-to-date on the latest interest at Wolfram Research through our blog: https://blog.wolfram.com/ Follow Stephen Wolfram's life, interests, and what makes him tick on his blog: https://writings.stephenwolfram.com/
Source description (no synthesized summary yet).
Cellular automata provide a powerful framework for understanding and designing distributed consensus algorithms, bridging theoretical computer science with practical blockchain systems by enabling scalable, Byzantine-fault-tolerant protocols that leverage local majority rules and random topologies.
- Cellular automata with majority rules and asymmetric neighborhoods can suppress finite minorities and achieve consensus even under noise, as demonstrated by foundational work on the GKL rule and tomb layering constructions
- Graph-based cellular automata with random topologies achieve logarithmic convergence time independent of network size, scaling to millions of nodes while requiring only polylogarithmic messages per node
- Modern consensus protocols like Avalanche, NKN, and IOTA implement cellular automata principles through iterative gossip and random sampling, proving that theoretical results translate directly to deployable systems with sub-second finality
This asset isn't compiled yet
You're seeing its claims, ranked. Compile it to build the argument threads, weight them, and check each claim against your library — the full view.
Cellular automata on graphs with random topologies where each node has k neighbors with k proportional to log(n) achieve consensus convergence time of O(log n / log log n), which is faster than high-dimensional grid topologies and represents the information-theoretic lower bound because the diameter of such graphs scales as log(n) / log(k-1)
“if we look at the sparse random graph with average degree k uh being proportional to log n where n is the number of nodes in the network and the coefficient should be larger than 1 for it to be connected the diameter of such graph is is about log n over log k in this case it's log n over log log n so the diameter is quite small smaller than the uh grid topology with the sigma on with same degree so it has very high effective dimension and it is a very good topology for consensus because it has very fast convergence time”
The Gax-Kadumov-Levin (GKL) rule, a one-dimensional cellular automaton that operates on a cell and its three neighbors on each side, successfully suppresses finite minorities and achieves consensus regardless of initial configuration, making it a foundational result for understanding distributed consensus in the presence of noise
“in 1978 uh there was this rule was suggested um by peter gax who's with us here today uh kadumov and leonard levin um and uh this is a a particular cellular automaton rule operating not just on a uh a cell and its two neighbors but a cell and its three neighbors on each side and if we run that particular rule let's say we run it with predominantly red initial conditions after a little while all the yellow will disappear and we will get just pure red”
The distributed consensus problem fundamentally involves determining what the majority or consensus state is among a collection of nodes, which can be efficiently solved using distributed algorithms running computations in parallel rather than sequentially visiting each node
“we just want to determine what the majority or consensus color of these nodes is... one obvious method to do this is just uh sequentially visit each node and then tally up all the colors... but it's potentially much more efficient if we can use a distributed algorithm where we're running computations in parallel across all these various nodes”
The history of cellular automata in distributed systems spans decades from von Neumann's 1950s work on reliable computing from unreliable components through Tomb's 1974 non-ergodic probabilistic cellular automaton to the GKL rule in 1978 and culminates in modern protocols like Avalanche and NKN
“in the at the beginning of the 1950s um when uh people were interested well actually probably arose even earlier than that people were starting to build complicated electrical electromechanical systems and the problem was there were components in those systems that were unreliable yet you wanted to make the whole system be reliable how could you make the whole system be reliable even when some of the underlying components um were uh were unreliable and so the the obvious idea was to use redundancy”
The majority rule cellular automaton on arbitrary graphs is P-complete to predict, meaning that determining whether a specific node will change state by time t is as hard as solving any problem in the complexity class P, but on planar graphs the problem remains P-complete due to the existence of a crossover gadget allowing signal routing without signal intersection
“one the decision problem for us is the print problem so given an initial condition and a specific node at value zero opinion zero does their existing positive such this node becomes one okay and our theorem we prove it with the pedometer was is the following if the maximum degree if we if we take the class of graphs where the maximum degree is bigger than five uh the press problem is p complete”
In a Nakamoto-style proof-of-stake consensus protocol like Ouroboros Praos, the staking procedure's property of independent aggregation uniquely determines the staking threshold and simplifies security analysis by ensuring that malicious actors gain no advantage from splitting resources into multiple accounts, making the protocol's behavior analyzable as a Markov chain with computable transition probabilities
“the quality of independent aggregation holds which eases the analysis um for calculating the probability of all these events and the distributions that play out of this process so primarily we're concerned in prowess with this active slots coefficient which dictates how many empty slots and how many occupied slots would be on average”
NKN's consensus has been live on a public network for three years and is currently powering against midnight with around one hundred thousand consensus nodes globally, making it the world's largest blockchain network by node count
“we have implemented these consensus algorithm and name it moca short for majority vote cellular automata we open sourced it on github as part of our full node implementation so you can check it out if you are interested and the consensus moca has been live on public uh network for three years and it is now powering against midnight which has around us a hundred thousand consensus node globally which is which is the world's largest blockchain network”
Rule 184, a simple one-dimensional cellular automaton where cells move left or stay put based on local configuration, exhibits second-order phase transitions in block probabilities as a function of initial density when extended to infinite systems, with the probability of '11' blocks discontinuous at density 0.5 in the derivative but continuous in value
“if i plot probability of occurrence of one one after any iteration against density then initially this is a parabola this black curve when n is equal to zero then it becomes blue line a green line after ten iterations and after infinitely many iterations it converges to this piecewise linear function so this actually is right here it's covered by other curves so maybe you don't see it but it is actually something which looks like a second order face transition”
The DAG-based structure of Avalanche allows multiple transactions to be voted on simultaneously by leveraging dependency relationships: voting to accept a transaction in the DAG implicitly votes to accept all its ancestors, amortizing the consensus cost across many transactions
“what one could do is you can entangle the decisions you can say look i can so i might be deciding between alice pays bob and al space charlie over here and i this is a consensus instance i'm going to be doing this this avalanche thing up here but there are other people who could build on it there's david paying paying eve over here and and so on um what one could do is one could create a graph of dependent transactions so that the vote for for somebody deep in the graph low in this picture this is a this is a three like picture here of somebody who votes here implicitly votes for everything that preceded him”
Rule 30, a simple cellular automaton with a three-cell neighborhood, generates pseudorandom sequences that are unpredictable despite the rule being completely deterministic, making it useful as a random number generator and potentially for generating randomness in distributed systems
“this is a really good source of random numbers that if you look at the center column here it's something we've used as a random sequence generator for a very long time and so it's sort of this remarkable result that even though the rule is very simple the actual behavior that's generated is very complicated”
Proof-of-work based consensus protocols like Bitcoin consume environmental energy equivalent to multiple nations' electricity production, and this energy expenditure is decoupled from the actual security value provided since more energy expenditure does not increase the price floor of the token or improve its actual utility, making it economically wasteful
“nakamoto consensus consumes immense amounts of energy it's on par with the netherlands right now it's more than two denmark's it's more than three ireland's it's more than four nuclear power plants worth of energy going into just keeping this ledger there is no connection between the energy burned and value of the token you can burn as much as you like doesn't establish a price floor for your token it's an environmental disaster”
The fundamental challenge of distributed consensus is related to the principle of computational equivalence: as systems become more sophisticated to handle complex consensus requirements, they become computationally universal, which makes it impossible to formally prove they cannot do undesired things because such proofs would require solving the undecidable halting problem
“once you make the thing sophisticated and what it's doing it will tend to be computational universal a lot of science that i've done suggests that computational universality is very ubiquitous even among very simple systems and um that uh that means as soon as the thing is computational universal there's sort of it's undecidably difficult to verify that it can't possibly do anything wrong”
Ergodicity is a key property distinguishing non-ergodic infinite cellular automata that can maintain long-term order from ergodic ones that will eventually visit all possible states, and the distinction is crucial for understanding whether a cellular automaton can preserve information against noise
“if you take a probability sir probably 600 automaton and we say it's essentially if it forgets everything about its initial configuration and more precisely what this means is that that there is some fixed measure in you such that that on any finite set of cells if you look at the probability of this finite set of cells being in a particular array of states then this probability will converge to the corresponding probability new probability of this independently of what the initial configuration works right so it really forgets everything about the initial configuration”
The Tomb rule is asymmetric in its neighborhood and can erase finite islands of one state surrounded by another state, whereas symmetric majority rule cannot, because the asymmetry allows the rule to have a preferred direction of propagation that shrinks boundaries
“the simple rule of thumb rule you can extend it to also larger alphabets so so uh we can say that that the majority because we will use this the majority if there is a low majority it really doesn't matter what to do but let us say then you don't change the state but if there is if then if the northern and eastern neighbors are different from you and equal to each other you have to change them so one of the basic questions that was already considered here earlier is how to suppress a finite minority right in an infinite system”
In one-dimensional cellular automata with periodic boundary conditions and finite size, no rule can achieve perfect density classification where all initial configurations converge to the correct consensus value; there will always be some pathological configurations
“there are bad news about about this problem uh so as i said uh it has been proven that no single rule can solve this problem and further further to the original proof in 95 there was also a proof that you could extend the problem to the k every case beyond the binary case and the kre case i cannot be solved either”
Avalanche protocol achieves transaction finality in approximately 2 seconds (or 300 milliseconds in practice on current networks), compared to 60 minutes for Bitcoin and 555 seconds for Ethereum, while tolerating Byzantine attackers controlling up to 60% of the network
“the bitcoin latency is one hour okay you have to wait for six confirmations for a pretty small attacker actually it turns out if the attacker is bigger you have to wait more than an hour for ethereum corresponding security it has more frequent blocks probably probability probabilities are on its side it's about 555 seconds that's math that was done by a phd student in in london um and uh there are other protocols that do sortition so you know a good protocol in the classical uh setting is algorand and it takes 50 seconds for this decision now avalanche takes it says two here uh we conservatively say two in the current network it's about 300 milliseconds”
In NKN's consensus protocol using cellular automata with random topology, malicious nodes achieve maximum disruption through the flip-side attack: setting their initial state to the minority opinion and never changing it, and the protocol is secure against this attack if and only if the fraction of malicious nodes is less than the absolute difference in honest node counts between the two states
“the most effective way to attack the correctness of the system is to use something i called flip side attack and the attack is pretty simple the attacker will set all their malicious nodes initial state to the minority state of the network and they will not change their malicious note state during the consensus no matter what this the attack is considered to be successful if the honest node will convert to the minority state that's breaking the correctness of the consensus”
Byzantine-resilient consensus protocols based on cellular automata are fundamentally superior to classical quorum-based protocols because they don't require knowing exact network membership, tolerate Byzantine adversaries larger than a majority in some cases, scale to millions of nodes rather than hundreds, and degrade gracefully rather than having sharp security thresholds
“another fact that's uh very interesting classical protocols these protocols that i talked to you about that are based on collecting signatures from a parliament they they do not degrade gracefully they degrade the moment the attacker is bigger than 33 percent it's a well-known result so as an attacker you know exactly when you're going to succeed uh in contrast in avalanche and similar networks what there is is there is a parameterized security component”
NKN uses verifiable delay functions and blockchain-based randomness to generate node identities that cannot be controlled by attackers: a new node must first commit a transaction with proof-of-work, wait for several blocks (during which the node has no control over block producers), and then its identity is computed from the block hash of the block confirming its transaction, making it impossible to predict or grind for favorable positions
“in order to get a random id into the system he not only needs to like pay some cpu power he also needs to pay some like financial token into it and after that he gets randomized if he don't like it well um he can he can't get the money back but so so when you're doing that you said this is your scheme for generating the the random id is based you said on on the the series of blocks that were made but but you have a very decentralized”
Entanglement codes for distributed storage use XOR operations to create interdependent chains of data blocks where repairing any failed block requires only two chunks regardless of chain length, achieving storage overhead of factor α (number of parity blocks per data block) while distributed repair only requires two chunks to be downloaded even for large failures
“basically when we are uploading a blog or a file to the system we create some redundant block the first block can be sync as it's just a copy of the block and then a new a new the green chunk is added to the system and to create the new redundant block this redundant block is basically the xor of the previous two blocks in this chain that keeps growing”
Cellular automata can model failure and repair dynamics in storage systems, allowing comparison of different redundancy strategies (replication, erasure coding, entanglement codes) by simulating how block availability degrades over time under various repair policies
“in this framework a cell represents a chunk of data a file or a storage device so healthy styles in this case are blocks and the idea here is that is that i let the system decay so i wanted to uh understand what happens if the system doesn't receive any maintenance and and then i start playing with also with another module that has the system that is that actually injects failure so makes the situation worse”
The minority network majority rule with different tie-breaking strategies (prudent, risky, fixed) produces different dynamics: prudent converges to fixed points or 2-cycles, risky can produce very long cycles or complex behavior, and fixed strategy creates deterministic consensus on finite toruses
“in case of tie there are three possibilities a the prudent behavior say in case of die the central guy remains in his opinion in case of risky behavior it changes to the opposite one and the vs behavior always stay one opinion say for instance one so we will study it and the the interesting thing is that the the behavior is different uh from these three kind of thai cases”
In fast probabilistic consensus (FPC) for IOTA, attackers cannot maintain a metastable state in the network because the random threshold changes unpredictably after each round, making it impossible for attackers to coordinate a response that keeps the network balanced
“what happens with the byzantine resistance of um of the fpc with with regards to this random threshold well suppose character is trying to maintain us um a split and is trying to keep the average opinion of every node to be one half okay well then what happens is that um eventually um just randomly the um the threshold is either going to be uh at some point is going to be close to either beta or one minus beta right and depending on where a actually is um it will definitely be uh the average will either be definitely below a for all of the nodes you're definitely above a for all of the notes all right”
Merkle tree data structures used for content addressing in decentralized storage systems are vulnerable to cascading failures where loss of any internal node makes data at multiple chunks unreachable, and this vulnerability increases with tree depth and uneven replication across peers
“the problem is the cascading failure so if we lose one of these internal nodes we cannot locate the data so the current solution now is high levels of replication and as we can see in our own cluster we make sure we have a 1000 nodes of the password network and we have seen that not supplied replication but in the decentralized network we cannot expect much so the replication is uneven so some some chunks are replicated nine times sanctions are replicating 150 times”
Asynchronous cellular automata with random majority updates do not achieve the same level of reliable consensus as synchronous versions, but can be improved by adding state to track the local time modulo 3 for each node so neighbors know whether they should wait for updates from each other, though this introduces new challenges with deadlocks in 2D and long waiting chains that degrade error correction
“asynchronous updating destroys kind of the the nice consensus properties of these particular rules i did a bit of a search for rules that would even with a asynchronous updating would successfully preserve consensus this is the the best out of about two million what was it uh yeah a million range two rules the results are pretty crummy”
Block time distributions in Nakamoto consensus (Bitcoin) follow an exponential distribution, whereas some alternatives like Tacticos (Topple's protocol) produce more stable block time distributions with faster convergence, enabling better resource planning
“this is a modification that i was inspired to pursue while i was implementing this uh for our consensus layer so topple is an esg and impact focused uh application layer one blockchain company and we're integrating and uh developing all our own infrastructure so a high level overview and this is kind of the main uh three bullet points of the talk we introduced this new staking procedure and i'm going to go over the background as required”
Fireflies and other biological systems achieve synchronization through mechanisms similar to cellular automata, where local interactions lead to global coordination without central control
“yet another branch that just became aware of a few days ago was uh people studying synchronization of fireflies and much beyond people like steve strogatz and duncan watts and they too had uh knew about actually the gkl rule and started studying this question of consensus”