Improving Cellular Automata for Distributed Ledgers

Abstract

Every distributed system in which there is no central coordinator requires some form of agreement on its state and other aspects. Depending on the setting, there is also some possibility of additional risks, such as malicious or failing nodes, and this also contributes to the challenge of reaching consensus. In this work we investigate the problem of metastability in peer-to-peer networks that are used for distributed ledgers, especially focusing on cellular automata protocol with majority dynamics. Our results demonstrate that networks using this protocol do not reach consensus easily, even in the absence of an adversary. As a remedy for that, we propose a set of fixtures significantly increasing the probability of reaching network agreement that in best cases allow for achieving it two orders of magnitude more often compared to the basic cellular automata approach.