The Effect of Network Delays on Distributed Ledgers Based on Direct Acyclic Graphs: A Mathematical Model

Abstract

We present a new stochastic model for the evolution of Directed Acyclic Graphs (DAG)-based distributed ledgers (DL), under the presence of heterogeneous delay. This model is used to analyse the performance metrics of the DL, showing in particular that the number of unapproved messages does not diverge to infinity, even under the presence of delay. We propose an analysis based on conveniently defined sets, as well as an alternative drift-based analysis. The former allows to get a bound on the number of unapproved messages, while the latter, through a simpler analysis, allows to probe the existence of such bound. For particular scenarios, we are able to derive the expected value of the drift of unapproved messages, through a Markov process-based approach. State-of-the-art mathematical models trying to capture the impact of delays on the performance of such DLs rely on some particular simplifications. In contrast, through our model, we are able to analytically derive similar performance guarantees, in a more realistic setup. In particular, we focus on IOTA foundation's tangle, while our results can be extended to other DAG-based distributed ledgers. We compare our results to results obtained in a real testbed, showing good accordance between them.