- The research on cellular automata funded by the IOTA Foundation as an extension of the existing consensus mechanism has produced promising results.
- For consensus in a sharded IOTA Tangle, a combination of Fast Probalistic Consensus, cellular automata and the use of the reputation system Mana will be investigated.
The IOTA Foundation continues to support the investigation of new consensus models for the IOTA Tangle. Already in May of this year, it announced the investigation of cellular automata as a possible extension of IOTA’s consensus mechanism in the context of a Coordicide grant to Dr. André Vilela and Dr. Kenric Nelson.
The main purpose of the grant was, as stated at the time by the IOTA Foundation, to support “beyond the horizon” research to explore future possibilities for the protocol. According to the IOTA Foundation, although cellular automata are very difficult to analyze, they have great potential in terms of speed and communication efficiency. The research has been outsourced because “the IOTA team is very busy publishing Coordicide“.
Cellular automata as an extension of IOTA’s consensus model
As Andrew Greve of the IOTA Foundation has now explained in a new blog post, the three-month research has produced its first promising results. Vilela and Nelson from the University of Boston conducted simulations of cellular automata to determine the agreement and success rates for consensus in various voting scenarios between connected neighbors.
The simulations thus aimed to investigate whether cellular automata are feasible or not in the context of the IOTA Tangle. The aim was to design potentially useful approaches for the voting processes to reach a consensus. Regarding the results of the study, Greve stated:
Dr. Vilela and Dr. Nelson showed that the standard voter model yields a relatively low success rate on random graphs. However, they identified several mechanisms that greatly improve the convergence rate. As explained in the report, Dr. Vilela and Dr. Nelson provide lower bounds on k, the number of neighbors, required for good convergence.
They also discovered that convergence rates improve if ties (i.e. when exactly half of a node’s neighbors are of each color), are decided by a coin toss, rather than remaining the same color as before. These results encourage further theoretical and empirical research regarding the role of Cellular Automata for consensus in IOTA.
As stated in the results of the study, both researchers recommend that the IOTA Foundation should further investigate a “Swift Entropic Consensus”. With a sample of 1,000 random graphs per initial majority with 10,000 nodes and an average of 12 connected neighbors, the majority vote achieved 100% consensus for all studies across all initial majorities.
As a next step, the researchers propose to investigate the role of adversarial nodes in the majority voting process, as well as the influence of mana weighting on maintaining the integrity of the consensus process.
Due to the promising results, Greve explained that the IOTA Foundation will continue to support research into cellular automata and their integration into the IOTA consensus model. In particular, cellular automata could be of great interest for a consensus in a sharded Tangle, as Greve noted:
Although our research here is still overall in a preliminary stage, we are beginning our formal work on this topic, and we see a few promising directions which we intend to pursue. We are investigating whether consensus in a sharded Tangle can rely on a combination of consensus mechanisms, including FPC [Fast Probalistic Consensus] and CA, as well as the utilization of a reputation system. We look forward to offering more discussion on this topic in the near future.