Measuring the influence of the network structure for the vote propagation in the cellular automata consensus

The design of fault-tolerant systems in a distributed setting highly depends on the selected consensus mechanism and its peer-to-peer network setup. Even though both topics were extensively studied as separate concepts, little to no attention has been given to either layer and the direct impact one has on the other. In this paper, we investigate how the network layer in a distributed system influences the system’s ability to reach an agreement. As a voting protocol, we choose the cellular automata (CA) with majority dynamics. CA is well-fitted for this research question due to its simplicity and small message complexity. In CA, votes are exchanged through connections established with the peering mechanism. Therefore, CA is highly dependent on the networking layer, which can amplify effects on vote propagation. The network layer in our experiment was generated with two selected peering algorithms: kademlia and salt-based. The results of our simulations indicate that increasing the number of allowed connections for a node affects the consensus reaching differently for both algorithms. While salt-based metastability resilience increases with higher node degree, for kademlia we can observe the opposite effect.