Research Grant Report — Cellular Automata Consensus: Convergence and Modifications

As you might recall, in November of last year we announced a grant for studying Cellular Automata and Autopeering Optimization. That work has now been completed by our outstanding grantees, and this post contains a summary of the research and its conclusions.

Although the outcome was not positive for Cellular Automata’s (CA) inclusion in future upgrades of the IOTA protocol, the research led to new insights that helped us with other aspects of Coordicide. It also underscores the importance of doing the rigorous research necessary to tackle difficult problems taken up by our team. This research is a wonderful example of venturing into the unknown, and as a necessary part of understanding what works, what doesn’t work, and why. Only by stepping into unknown territory, one might stumble upon unexpected aspects that can turn out to be highly beneficial.

We are grateful for the knowledge gained from this research. We are also grateful for the positive results of the research, which include a proposal for modifications to the voting protocol, and also an implementation for the ar-row autopeering algorithm. Much thanks to Radosław Michalski, Daria Dziubałtowska, and Piotr Macek for their excellent and thorough work, and for the text that follows!

Research Introduction

The purpose of our research project was to analyse the impact of graph configurations on reaching consensus for the CA algorithm. To do so, within the project we analyzed the structural properties of graphs generated by the ar-row and salt-based autopeering methods, i.e. the methods for establishing links between IOTA nodes. Secondly, we moved towards studying the impact of graph configurations, specifically regarding how the cellular automata-based consensus reaches stability and, if not, how to overcome these situations. Based on the results of these two analyses, we also proposed modifications to the voting protocol to avoid metastable situations resulting in split opinions on the ledger state. Lastly, we implemented a GoShimmer module for the ar-row autopeering algorithm. This blog post presents the results of the research.

Firstly, we’d like to point readers to another blog post that introduces the idea of consensus in the Tangle - in which you can find a more fundamental description of consensus and multiple strategies for maximizing the chances for reaching it. In our research project we focused on the cellular consensus also mentioned there. For more details, please refer to Section 6.2 of the Coordicide White Paper.

Autopeering algorithms

The goal of this part of the research was to evaluate two autopeering algorithms: salt-based and ar-row. Each of these two methods has different means of creating a graph structure and they differ on how nodes communicate with each other in order to find peers. Ideally, both of the methods are supposed to end up with k-regular graphs, i.e. graphs in which each vertex is connected to k neighbours. These graphs were later used for running the cellular automata algorithm to reach consensus. However, before doing so, we wanted to evaluate whether the graphs generated by salt-based an ar-row algorithms differ structurally.

We ran these methods for a selected number of <n, k> combinations, with n representing number of vertices, for multiple instances of graphs (in total we analysed 2,916,670 graphs). For the salt-based method we limited the number of rounds to a hundred, since in the majority of cases if graphs did not converge to k-regularity within a hundred rounds, they did not converge for a larger number of rounds as well.

From this part of research a number of conclusions can be drawn:

for the ar-row algorithm, reaching k-regularity is possible in two out of three cases
for the salt-based method, reaching k-regularity is hard to achieve, but the mean number of edges and its variance are, at least from our perspective, acceptable and close to k-regularity
ar-row is a method that due to its nature generates graphs an order of magnitude faster than salt-based algorithm
global graph measures of generated graphs (k-regularity, modularity, girth size, and diameter) reveal a high similarity between two methods, which has been statistically evaluated
local graph measures (clustering coefficient and betweenness) diverge only slightly - the differences between distributions have been quantified by using the Kullback-Leibler divergence measure

Cellular Automata consensus

As a second step, we implemented the Cellular Automata algorithm based on the description presented in the aforementioned white paper. The nodes were determining their own opinion based on the opinion of their neighbors from the previous round. In our implementation we deviated in one aspect from the version presented in the Coordicide paper: When no opinion had the majority, we did not use an undecided state. Instead, the node is changing its opinion to the opposite it had in the previous round. We tested the CA algorithm on graphs with different <n, k> combinations. For all our simulations we used a number of rounds M=100, the number of consecutive rounds with the same opinion for a node to become final l=4, and we used linear function as a monotonic function for punishing nodes that have less than k neighbours.

The most important part of this research was to count the number of metastable situations that occurred during CA simulation. As an excerpt from all results that we have, in Figure 1 and Figure 2 we present how the metastability depends of k and n (for salt-based and ar-row, respectively).

Figure 1. The percentage of metastable situations for different values of k and n forsalt-based.

Figure 2. The percentage of metastable situations for different values of k and n for ar-row.

Before going further, let's summarize what conclusions can be drawn for the analysis of CA with zero temperature:

in general, the percentage of metastable situations exceeded our expectations
for smaller k, independently of n, reaching the consensus is more difficult
there is a difference observed for ar-row and salt-based underlying graphs in terms of the percentage of metastable situations for CA (independently of initial states assigning method), but there is no clear winner
the gossip algorithm leads to less metastable situations for higher n, as compared to initiating nodes with random opinions
performed experiments haven't provided enough data to perform the estimation of metastable cases for larger n

Improved CA with zero temperature

The results for CA with zero temperature were not sufficiently good, so we manually analyzed some meta-stable situations for small graphs to try to find out why the algorithm failed to reach consensus and we pinpointed two crucial points which make it hard for the network to enter a stable state.

The first problem we noticed is when some nodes are changing opinions when their neighbourhood opinions were split 50/50. This caused some nodes to change their opinion in every round, which in consequence caused other nodes to change their opinion in consecutive rounds and did not allow the state to stabilize.

For testing, we changed this so that in the described situations the node changes its opinion randomly, so either stays with its current opinion or changes it. This made the results better for small graphs, however for large graphs (with 100 nodes), this turned out to make the results worse and we dropped this change.

The second challenge we found was that some nodes were changing opinions in every round back and forth, causing some of its neighbours to change opinions as well in consecutive rounds, not letting the network stabilize.

As the problem occurs because nodes change their opinion in every round, we decided to apply a change that allows nodes to change their opinion in two consecutive rounds only with small probability and with zero probability. From analysis on a small subset of large and small graphs, allowing nodes to change opinions in two consecutive rounds with 10% probability gave the best results.

Described modifications greatly improved the results, however meta-stable situations still sometimes occur. Further investigation did not lead us to any more improvements, as remaining metastable situations are still caused by nodes changing opinions back and forth. Those remaining meta-stable cases in our simulator are unfortunate enough that despite 10% probability of nodes changing opinion in two consecutive rounds, some nodes change their opinions in every round. We were not able to find a good enough fix to cover all cases, however described changes provided a great improvement.

As the results demonstrate (see Figure 3), the number of the metastable situations dropped

significantly. In this case, ar-row based graphs outperformed the salt-based ones, but the advancements were clearly observed for both families. This shows that there is a room for improvements even without the temperatures introduced to the system

Figure 3. Percentage of metastable situations for salt-based and ar-row autopeering methods for CA with improvements.

Thanks for reading! We hope you continue to follow our updates here on the blog, and you are also welcome to connect with Research team members 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.