Coordicide Grant Report — Cellular Automata in IOTA
In May of this year, we announced a Coordicide Grant to study Cellular Automata as a potential extension to IOTA’s consensus mechanism in future versions of the protocol. Today, we are pleased to share the results of that research. Dr. André Vilela and Dr. Kenric Nelson investigated the dynamic properties of Cellular Automata (CA) consensus algorithms.
The research included simulations of Cellular Automata using a majority model on ak-regular graph in order to determine the agreement and success rates for consensus given various vote scenarios among connected neighbors. The goal was to draft potentially viable approaches to the CA voting processes for achieving consensus.
Summary of the results
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 onk, 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.
Read the full report for all the details!
What’s next
We look forward to continuing our exploration of Cellular Automata and its application to IOTA. As we have discussed in previous posts, Cellular Automata is one avenue we are exploring for consensus in a sharded Tangle. Our work on putting the pieces of this next stage in IOTA’s research and development together will build on the grant work undertaken here.
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 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.
As always, you can stay up to date with the IOTA Research team in the #tanglemath channel on our Discord. You are also welcome to follow and participate in our technical discussions on our public forum: IOTA.cafe.
