On the Stability of DAG-Based Distributed Ledger with Heterogeneous Delays

On the Stability of DAG-Based Distributed Ledger with Heterogeneous Delays

연구 분야: Databases

학회: International Conference on Network Games, Artificial Intelligence, Control and Optimization

Directed Acyclic Graphs (DAGs) are an appealing design for Distributed Ledger (DL) architectures. Specifically, DAG-based DLs offer valuable benefits compared to blockchains, such as improved scalability, lightweight consensus mechanisms and lower transaction costs. However, due to the communication delays and distributed nature of the DL, some transactions may remain unapproved. Previous works have provided bounds on the expected number of unapproved transactions when the transactions selection strategy is uniform. Still, a transaction should be preferably validated by multiple nodes so as to increase the trust in the ledger. In this paper, we introduce a bound on the expected number of transactions that are approved by at most one node. For this purpose, we define a new stochastic model based on stochastic sets, which captures the evolution of DAG-based DL. The proposed model enables us to establish a quadratic bound on the drift in the number of tips. We then demonstrate that the expected volume of transactions validated by at most one node is bounded. These results indicate that the occurrence of large volume of transactions validated by at most one node happens with sufficiently low probability.