Nodes in blockchain are peers due to the decentralized nature of blockchain. The inherent lack of trust in blockchain systems is particularly noteworthy because any node can send any information to any nodes in the blockchain. Peers must evaluate information and make agreement on their actions for blockchain to work properly.
NKN is designed to be a futuristic blockchain infrastructure that requires low latency, high bandwidth, extremely high scalability and low cost to reach consensus. These properties are crucial for future DApps. Thus, NKN needs new consensus algorithms that could satisfy such high requirements.
CA Consensus Modelled by Ising Cellular Automata (CA) is naturally a large distributed system with only local connections. The asymptotic behavior of the system is controlled by its updating rule. It is possible to achieve guaranteed global consensus in CA using message passing algorithm based only on sparse local neighbors for a set of updating rules.
Majority Vote Cellular Automata Majority Vote Cellular Automata (MVCA) is a Cellular Automata using majority vote as updating rule.
Using the mathematical framework originally developed for Ising model in physics, we found and proved that a class of CA rules will guarantee to reach consensus in at most O(N) iterations using only states of sparse neighbors by an exact map from CA to zero temperature Ising model. Some studies investigated the fault tolerance of Cellular Automata and how to increase robustness in Cellular Automata-Based systems. We further showed that the result is robust to random and malicious faulty nodes and compute the threshold when desired consensus cannot be made.