Coordicide Grant Report — Cellular Automata in IOTA

The full article was originally published by Andrew Greve on Medium. Read the full article here.

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 a k-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 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.

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:

The full article was originally published by Andrew Greve on Medium, where people are continuing the conversation by highlighting and responding to this story. Read the full article here.

You might also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. AcceptRead More

Did you know?

Buy in without the stress of trying to time the market

when you setup a savings plan. If you haven’t started a plan yet, head to your Bitpanda account to get started!

Purchasing cryptocurrencies comes with a number of risks.
Never invest money that you can't afford to lose.

You can automatically invest

in IOTA with Bitpanda Savings!