Abstract:
This paper presents a novel shared memory model that simplifies the analysis of consensus on a Chain and a DAG. In this new model, referred to as the append memory model, nodes are allowed to write new values to the unordered memory, but not to overwrite already existing values. We show that although this model differs from the standard shared memory model with n shared read-write registers, many known results from the shared memory model still hold in the append memory model: It is, for example, impossible to establish consensus on n nodes with one crash failure if the nodes in the system are asynchronous. We also consider the append memory model in a synchronous setting with Byzantine failures. For this case, we show that Byzantine agreement cannot be solved in less than t+1 rounds, where t is the number of Byzantine nodes in the system. Assuming a probabilistic access restriction to the append memory, we compare the Byzantine agreement protocols on the Chain and the DAG. We show that the DAG structure achieves an almost optimal resilience (close to t<n/2) in contrast to the Chain structure that can tolerate less than t<n/(1+l*(n-t)) Byzantine nodes, where l is the rate at which the nodes access the memory.
