# A Markov Process Theory for Network Growth Processes of DAG-based Blockchain
Systems

Xing-Shuo Songa, Quan-Lin Lib, Yan-Xia Changb, Chi Zhangb
aSchool of Economics and Management
Yanshan University, Qinhuangdao 066004, China
bSchool of Economics and Management
Beijing University of Technology, Beijing 100124, China

###### Abstract

Note that the serial structure of blockchain has a number of essential
pitfalls, and, thus, a data network structure and its DAG-based blockchain are
introduced to resolve the blockchain pitfalls. From such a network
perspective, analysis of the DAG-based blockchain systems becomes interesting
but difficult and challenging. So, the simulation models are adopted widely.
In this paper, we first describe a simple Markov model for the DAG-based
blockchain with IOTA Tangle by means of two layers of tips and internal tips’
impatient connection behavior. Then we set up a continuous-time Markov process
to analyze the DAG-based blockchain system and show that this Markov process
is a level-dependent quasi-birth-and-death (QBD) process. Based on this, we
prove that the QBD process must be irreducible and positive recurrent.
Furthermore, once the stationary probability vector of the QBD process is
given, we provide performance analysis of the DAG-based blockchain system.
Nextly, we propose a new effective method for computing the average sojourn
time of any arriving internal tip at this system by means of the first passage
times and the PH distributions. Finally, we use numerical examples to check
the validity of our theoretical results and indicate how some key system
parameters influence the performance measures of this system. Therefore, we
hope that the methodology and results developed in this paper shed light on
the DAG-based blockchain systems such that a series of promising research can
be developed potentially.

Keywords: Blockchain; Direct Acyclic Graph (DAG); IOTA; Tangle; Tip; QBD
process; Performance analysis; Sojourn time.

##  1 Introduction

Blockchain technologies originated from Bitcoin by Nakamoto [66] in 2008\.
Since then, blockchain has attracted tremendous attention from both
practitioners and academics in many different areas, such as finance,
reputation system, security, public service, anti-corruption, Internet of
Things, and so on. Blockchain has many remarkable and excellent features, for
example, decentralization, distributed structure, availability, persistency,
consistency, anonymity, immutability, auditability, and accountability.
Bitcoin and Ethereum are regarded as the two most representative blockchain
technologies that have primarily contributed to such popularity gain. So far,
blockchain technologies have significantly enabled a wide spectrum of
applications from “cryptocurrency, financial service, reputation system,
security, public service, smart contracts, Internet of Things” to “healthcare,
energy management, supply chain management, sharing economy, social
governance, insurance, law, art among others”. Readers may refer to recent
survey papers for details, among which are Wang et al. [97], Gorkhali et al.
[39], Belchior et al. [5] and Huang et al. [46].

It is worthwhile to note that Bitcoin stores transactions in a publicly
available ledger. Each block contains a finite batch of transactions and the
blocks are strung together in a chronological order such that they can
construct a chain of blocks. The consistency of the ledger comes from the
structural extension in the series of the blocks. The newly added block is
viewed as legitimate only if it is consistent with the chain of all those
blocks in front of it. After Bitcoin, other cryptocurrencies, like Ethereum
and Litecoin, originate from extending and generalizing the useful
functionalities of Bitcoin. But they still retain the block-to-block series
connection of physical structure. For Bitcoin, Ethereum and other blockchain
systems, when there is an honest mining pool (note that the multiple honest
mining pools can merge into a total honest mining pool) and multiple different
dishonest mining pools in the system, it can cause multiple block branches on
this tree. In this case, the blockchain can be set up by pegging each main
chain at each round, which is a competitive result from a tree of blocks by
means of the longest chain principle. Notice that the backbone of this tree is
built by the honest mining pool, while the other branches are built by only
the dishonest mining pools under a physical setting that a dishonest mining
pool can only build one branch at most. See Li et al. [59, 60] for more
details.

However, the serial structure of blockchain (including a blockchain generated
from the tree of blocks with multiple branches) has a number of essential
pitfalls, such as poor performance and scalability, limited transaction
throughput, high transaction cost, long confirmation delay, huge energy
expenditure (Proof of Work), and so forth. To resolve these blockchain
pitfalls, a DAG data network structure was introduced to the blockchain
technologies (called a DAG-based blockchain) in order to replace the serial
structure of the blockchain. On one hand, the DAG-based blockchain has quickly
emerged in the context of the Internet of Things, e.g., see Ferrag et al.
[30], Lo et al. [63], Viriyasitavat et al. [90], Cullen et al. [21] and
Alshaikhli et al. [1]. On the other hand, the DAG-based blockchain has
increasingly been adopted in the field of Distributed Ledger Technology, e.g.,
see Zhu et al. [106], Gorbunova et al. [38], Park et al. [70] and Benčić and
Žarko [6].

To develop the DAG-based blockchain and facilitate secure payments and
communication between devices of the Internet of Things, the IOTA Foundation
proposed a new protocol called IOTA, which has a DAG data network structure.
Readers may refer to papers, such as Popov [75, 76], Popov and Buchanan [77],
and Popov et al. [78, 79]. From the Popov’s papers, it is easy to see that all
the transactions would be approved and stored permanently on the IOTA Tangle.
In addition, to further understand the basic elements of the IOTA Tangle,
readers may refer to Conti et al. [18], Attias and Bramas [3], and Fan [27]
for more details.

So far, the Internet of Things has gained rapid development and has also been
applied to many different practical fields, such as logistics, supply chain
management, healthcare, smart city, intelligent transportation, intelligent
security, intelligent building, intelligent home, heritage protection,
positioning and navigation, video surveillance, and so on. It is well known
that the Internet of Things will generate massive amounts of data every day.
In this case, blockchain is a key technology for setting up a necessary and
effective platform to store and manage the data from Internet of Things. Also,
in this research line, it is the key to apply the IOTA Tangle to Internet of
Things due to the fact that the DAG-based blockchain has high transaction
throughput, good performance, and low cost. To this end, readers may refer to
survey papers by Alshaikhli et al. [1] and Lo et al. [63]; Distributed Ledger
Technology by Cullen et al. [20, 21], Park et al. [70] and Siim [84]; and
industrial Internet of Things by Cui et al. [19] and Liao et al. [62].

Up to now, there has been some key research on the DAG-based blockchain with
IOTA Tangle. To help readers quickly understand the recent literature and
associated advances, here we provide an overview of DAG-based blockchain as
follows:

(1) The survey papers: Wang et al. [95], Bai [4], Siim [84], Brunner [13] and
Keidar et al. [49].

(2) The IOTA Tangle application in the Internet of Things: Hellani et al.
[44], Gerrits [37], Silvano and Marcelino [85], Lee and Sim [56], Wang et al.
[96], Zhang et al. [102] and Igiri et al. [47].

(3) New consensus protocols developed in the DAG-based blockchain: Danezis et
al. [22], Wang et al. [94], Cui et al. [19], Zhang et al. [103], Tian et al.
[88], Reddy and Sharma [80], Schett and Danezis [82], Xiang et al. [99],
Nguyen et al. [68], Zhou et al. [105], Spiegelman et al. [86], Deng et al.
[24] and Müller et al. [65].

(4) Performance analysis of the DAG-based blockchain: Dong et al. [26], Fan
[27], Fan et al. [28] and Penzkofer et al. [71].

(5) Security of the DAG-based blockchain: Conti et al. [18], Bramas [10, 11],
Shabandri et al. [83], Bhandary et al. [7], Li et al. [61], Wang et al. [91,
95], Madenouei [64], Brighente et al. [12] and Fan et al. [28]. In addition,
the parasite chain attacks are discussed by Staupe [87], Cullen et al. [20]
and Penzkofer et al. [71].

(6) Privacy of the DAG-based blockchain: Shabandri et al. [83].

(7) Scalability of the DAG-based blockchain: Chen et al. [17], Wang [93],
Madenouei [64] and Fan et al. [28].

(8) Throughput of the DAG-based blockchain: Zhang et al. [103], Madenouei
[64], Brighente et al. [12] and Fan et al. [28].

(9) Stability of the DAG-based blockchain: Bramas [10] and Ferraro et al.
[32].

(10) Control of the DAG-based blockchain: Ferraro [33], Vigneri et al. [89],
Nakanishi [67] and Gupta and Krishnamurthy [42].

(11) Physical structure of the DAG-based blockchain: A serialized bolckDAG by
Gupta and Janakiram [41] and A mixed Tangle-Blockchain architecture by Hassine
et al. [43].

(12) Data analysis of the DAG-based Blockchain: Guo et al. [40], Gangwani et
al. [34], Penzkofer et al. [72] and Silvano and Marcelino [85].

(13) Comparison among DAG, PoW, PoS and BFT: Pervez et al. [74], Anwar [2],
Cao et al. [14], Gerrits [37], Khrais [50] and Danezis et al. [23].

(14) Useful features of the DAG-based blockchain: Ferraro et al. [31], Zou et
al. [107], Cao et al. [15], Watanabe et al. [98], Wang et al. [94], Fan et al.
[29], Zhao and Yu [104], Zhou et al. [105], Birmpas et al. [8], Yin et al.
[100], Ding and Sato [25], Gao et al. [35], Tian et al. [88], Zhang et al.
[102, 103], Hellani et al. [45], Wang et al. [96], Jay et al. [48], Nguyen et
al. [68], Liao et al. [62], Müller et al. [65].

To further improve the performance of the IOTA Tangle (including the above 14
aspects), it is a key to provide a performance analysis of DAG-based
blockchain systems. However, it is interesting but difficult and challenging
to set up a mathematical model for analyzing the performance of the DAG-based
blockchain systems. To this end, so far, there have been two different
research classes as follows: (a) Analytical models by Dong et al. [26], Fan
[27], Park and Kim [69], Park et al. [70], Li et al. [61], Cao et al. [14],
Birmpaset al. [8] and Fan et al. [28]; and (b) simulation models by Zander et
al. [101], Bottone et al. [9], Lathif et al. [55], Madenouei [64] and Wang et
al. [95].

Different from those above works in the literature, this paper provides a
Markov process theory in the study of DAG-based blockchain. By using our
Markov process, for a DAG-based blockchain system, we can provide its
stability analysis, performance evaluation, and optimal control. Therefore,
our Markov process theory can be regarded as a key advance in the study of
DAG-based blockchain.

To show how to set up a Markov process, it is necessary and useful to
introduce the IOTA Tangle. The transactions are stored in a DAG, referred to
as Tangle. IOTA uses the PoW protocol and transaction validation to set up the
DAG-based blockchain. Note that the IOTA transactions are atomic in the
Tangle, thus one block corresponds to a transaction. The IOTA transactions are
connected via directed edges to other transactions, where a directed edge
means that a transaction (head) is approved by another (tail). To issue a
transaction and store it in a DAG permanently, the issuer must approve two
other transactions. Any transaction that has not yet been approved is called a
tip. The issuer uses a tip selection algorithm to choose which tips to approve
and uses the proof of work to ensure the validity of such an approval. Based
on this, the main purposes of this paper are to discuss the random behavior of
these tips in the DAG and to set up a Markov process of the tip number.

A few studies close to our work is to apply the simulation models by Kuśmierz
[51], Kuśmierz and Gal [52], Kuśmierz et al. [53, 54], Zanderet at al. [101],
Bottone et al. [9], Lathif et al. [55], Chafjiri and Esfahani [16], Zhao and
Yu [104], Gardner et al. [36], Cullen et al. [20], Wang et al. [91, 92] and
Perešíni et al. [73]. By comparing our Markov process with those simulation
models, we find that our Markov process can provide more accurate and detailed
analysis in the study of DAG-based blockchain. When using our Markov process,
the (tip) random behavior of the IOTA Tangle can clearly be understood from
the network structure of Tip connections in the time order. In the DAG-based
blockchain, each transaction will have a copy of the stored information; while
the network latency causes inconsistency in the content of the transactions’
copies. Thus, this inconsistency can cause a phenomenon in a deterministic
sense that a tip will be selected multiple times. However, our Markov process
will not cause such a phenomenon that a tip can be selected multiple times.
Therefore, this leads to a great simplification of our Markov analysis for the
DAG-based blockchain with IOTA Tangle.

Based on the above analysis, the main contributions of this paper are listed
as follows:

(a) We first describe a simple Markov model for the DAG-based blockchain with
IOTA Tangle by means of two layers of tips and internal tips’ impatient
connection behavior. Then we set up a continuous-time Markov process to
analyze the DAG blockchain system, and show that the Markov process is a
level-dependent QBD process. Based on this, we prove that this QBD process
must be irreducible and positive recurrent, and can provide performance
analysis of the DAG blockchain system by using the stationary probability
vector of the QBD process.

(b) We propose a new effective method for analyzing the sojourn time of any
arriving internal tip at this system by means of the first passage times and
the PH distributions. Further, we compute the average sojourn time of any
arriving internal tip by means of the RG-factorizations.

(c) We use numerical examples to check the validity of our theoretical
results, and to discuss how the performance measures of the DAG-based
blockchain with IOTA Tangle depend on some key parameters of this system.

Therefore, we believe that the methodology and results developed in this paper
shed light on the DAG blockchain systems such that a series of promising
research can be developed potentially.

The remainder of this paper is organized as follows. Section 2 provides a
detailed model description for the DAG-based blockchain system. Section 3
shows that the DAG-based blockchain system is related to a level-dependent QBD
process, and proves that the DAG-based blockchain system must be irreducible
and positive recurrent. Section 4 provides a performance analysis of the DAG
blockchain system. Section 5 proposes a new effective method for analyzing the
sojourn time of any arriving internal tip and computes the average sojourn
time by means of the RG-factorizations. Section 6 uses numerical examples to
discuss how performance measures of the DAG-based blockchain system depend on
some key parameters of this system. Section 7 gives some concluding remarks.

##  2 Model Descriptions

In this section, we provide a model description for a DAG-based blockchain
system and its associated network growth process. Also, we give mathematical
notations, random factors, and necessary parameters.

In a DAG-based blockchain system, its network growth process depends on the
arrivals of new transactions and the increase of confirmed transactions
through using a connection algorithm in the IOTA Tangle. Here, the confirmed
transactions are called network nodes (or blocks). To understand the IOTA
Tangle easily, the network growth process of the DAG-based blockchain is
depicted in Figure 1 with some physical interpretations.

Figure 1: Network growth process of DAG blockchain system

By using Figure 1, we first introduce a key concept: Tips, which are necessary
and useful in our next study. If any transaction is not approved by another
yet, then the transaction is called a tip. In this case, it is seen from
Figure 1 that all the tips are divided into two different categories: The
boundary tips and the internal tips. Note that there is a key evolutive
characteristic between a boundary tip and an internal tip. If an internal tip
synchronously approves two boundary tips, then the two boundary tips become
two confirmed transactions, so that the two boundary tips immediately become
the network nodes (or the confirmed blocks) and leave the set of tips. At the
same time, the internal tip immediately becomes a boundary tip and enters the
set of boundary tips.

In this paper, we introduce a key impatient behavior of internal tips. To
prevent the set of internal tips from becoming bigger and bigger such that the
system keeps a highly dynamic nature, we assume that every one of the internal
tips has an impatient behavior. Let $X$ be a nonnegative random variable. If
the waiting time of an internal tip is not less than $X$, then the internal
tip immediately becomes a boundary tip. It is worthwhile to note that the
impatient behavior of internal tips makes that each tip can leave the set of
tips as soon as possible.

By using Figure 1, we can provide a detailed description of the DAG-based
blockchain system and its associated network growth process as follows:

(1) For the convenience of discussion, we assume that the capacity of internal
tips is finite such that $S(t)\leq M$, where $M$ is a finite positive integer.
Note that there exists at least one genesis block (i.e., an initial
transaction) in the set of boundary tips. Thus, we have $S(t)\geq 1$ at any
time. At the same time, we assume that the capacity of boundary tips is
infinite.

(2) Arrivals of new transactions: Some accounts submit new transactions into
the DAG-based blockchain system according to a Poisson process with arrival
rate $\lambda>0$.

(3) Connection of each internal tip with two boundary tips: With the same
probability, each internal tip in the set of internal tips can synchronously
connect with any two different boundary tips in the set of tips and their
connection time is exponential with connection rate $\mu>0$.

In fact, such a connection is an approval, that is, the two boundary tips are
approved by the internal tip. This means that the two boundary tips become two
confirmed transactions so that the two boundary tips immediately become the
network nodes (or the confirmed blocks) and leave the set of tips. At the same
time, the internal tip immediately becomes a boundary tip and enters the set
of boundary tips.

(4) Impatient behavior of each internal tip: To enable the tips to enter the
network nodes (i.e., the confirmed transactions), we assume that each internal
tip has an impatient behavior. If the waiting time of the internal tip exceeds
a random impatient time, then this internal tip directly becomes a boundary
tip and enters the set of boundary tips. We assume that the impatient time of
each internal tip is exponential with inpatient rate $\alpha>0$.

(5) Independence: We assume that all the random variables defined above are
independent of each other.

###### Remark 1

In the DAG-based blockchain system, we introduce the impatient time of each
internal tip such that the internal tips can be accelerated to become network
nodes. In this case, the throughput of the DAG-based blockchain system is
improved greatly. At the same time, the impatient behavior can also prevent
some tips from staying for too much time in the set of tips.

###### Remark 2

In the DAG-based blockchain system, the purpose of this paper is to
concentrate on the dynamic characteristics of tips changing from the internal
tips, to the boundary tips, and finally, to the network nodes. While
introducing some random factors, this paper may be the first to apply the
Markov process theory to the study of DAG-based blockchain.

##  3 A Level-Dependent QBD Process

In this section, we consider the network growth process of the DAG-based
blockchain system by means of a continuous-time level-dependent QBD process,
and obtain a stability condition of the DAG-based blockchain system.

Let $Q(t)$ and $S(t)$ be the numbers of the internal tips and the boundary
tips in the DAG-based blockchain system at the time $t\geq 0$, respectively.
Note that once an internal tip completes the connection (or approval) with two
boundary tips, the two boundary tips become two network nodes so that both of
them leave the set of boundary tips immediately; while the internal tip
becomes a new boundary tip in the set of boundary tips. In this case, the tip
number in the set of boundary tips will be reduced by one. If a new
transaction arrives at the set of internal tips, the tip number in the set of
internal tips will be increased by one. If the internal tip becomes a new
boundary due to the impatient behavior of internal tips, then the tip number
in the set of internal tips will be decreased by one, while the tip number in
the set of boundary tips will be increased by one.

###### Lemma 1

For any time $t\geq 0$, $1\leq S(t)\leq M$.

Proof: $S(t)\leq M$ comes from Assumption (1) in Section 2: The capacity of
internal tips is finite. Thus, in what follows we only prove that $S(t)\geq 1$
by induction.

Firstly, for $n=0$ and $t_{0}=0$, $S(0)\geq 1$ follows the fact that there
exists at least one genesis block in the set of boundary tips.

Let $t_{1}$ be the epoch that the Markov process $\left\\{S(t):t\geq
0\right\\}$ has the first state jumping when it begins at time $0$. Then
$S(t)=S(0)\geq 1$ for $0\leq t<t_{1}$; while $S(t_{1})>S(0)\geq 1$ is due to
the fact that a new boundary tip comes from an impatient internal tip, and
$S(t_{1})\geq 1$ is due to the fact that once an internal tip completes the
connection (or approval) with two boundary tips, the two boundary tips become
two network nodes so that both of them leave the set of boundary tips
immediately, and the internal tip becomes a new boundary tip in the set of
boundary tips.

Secondly, in the cases: $n=1$ to $k-1$, this result holds. Now, we show that
for $n=k$, this result also holds. To this end, we write

$t_{k}>t_{k-1}>t_{k-2}>\cdots>t_{1}>t_{0}=0$

and

$S(t_{k-1})>1,S(t_{k-2})>1,\ldots,S(t_{1})>1,S(t_{0})\geq 1,$

where $t_{k}$ be the epoch that the Markov process $\left\\{S(t):t\geq
0\right\\}$ has the first state jumping when it begins at time $t_{k-1}$.

Now, we observe this result at time $t_{k}$. Note that $S(t)=S(0)\geq 1$ for
$t_{k-1}\leq t<t_{k}$; while $S(t_{k})>S(t_{k-1})\geq 1$ is due to the fact
that a new boundary tip comes from an impatient internal tip, and
$S(t_{k})\geq 1$ is due to the fact that once an internal tip completes the
connection (or approval) with two boundary tips, the two boundary tips become
two network nodes so that both of them leave the set of boundary tips
immediately, and the internal tip becomes a new boundary tip in the set of
boundary tips. Therefore, this result can hold at time $t_{k}$. By induction,
we show that this result can hold at time $t\geq 0$, i.e., $S(t)\geq 1$ for
time $t\geq 0$. This completes the proof. $\square$

It is easy to see that $\left\\{\left(Q(t),S(t):t\geq 0\right)\right\\}$ is a
two-dimensional continuous-time Markov process on a state space, given by

$\Omega=\left\\{\left(n,m\right):n\geq 0,1\leq m\leq M\right\\}.$

Based on this, the state transition relations of this two-dimensional Markov
process $\left\\{\left(Q(t),S(t):t\geq 0\right)\right\\}$ are depicted in
Figure 2.

Figure 2: The state transition relations of the two-dimensional Markov process

It is easy to see from Figure 2 that the Markov process
$\left\\{\left(Q(t),S(t):t\geq 0\right)\right\\}$ is a continuous-time level-
dependent QBD process whose state space is rewritten as

$\Omega=\bigcup\limits_{k=0}^{\infty}\text{Level }k{,}$

where

$\text{Level }k=\left\\{\left(k,m\right):1\leq m\leq M\right\\}.$

Therefore, the Markov process $\left\\{\left(Q(t),S(t):t\geq
0\right)\right\\}$ is a level-dependent QBD process whose infinitesimal
generator is given by

$Q=\left({\begin{array}[]{ccccccc}{{A_{0,0}}}&{{A_{0,1}}}&&&&&\\\
{{A_{1,0}}}&{{A_{1,1}}}&{{A_{1,2}}}&&&&\\\
&{{A_{2,1}}}&{{A_{2,2}}}&{{A_{2,3}}}&&&\\\ &&\ddots&\ddots&\ddots&&\\\
&&&{{A_{k,k-1}}}&{{A_{k,k}}}&{{A_{k,k+1}}}&\\\
&&&&\ddots&\ddots&\ddots\end{array}}\right),$

where

${A_{0,0}}=\left(\begin{array}[]{cccc}{-\lambda}&&&\\\ &{-\lambda}&&\\\
&&\ddots&\\\ &&&{-\lambda}\end{array}\right),\
{A_{0,1}}=\left(\begin{array}[]{cccc}\lambda&&&\\\ &\lambda&&\\\ &&\ddots&\\\
&&&\lambda\end{array}\right);$

for $k\geq 1$,

${A_{k,k-1}}=\left(\begin{array}[]{ccccc}0&k{\alpha}&&&\\\
k{C_{2}^{2}\mu}&0&k{\alpha}&&\\\ &\ddots&\ddots&\ddots&\\\
&&k{C_{M-1}^{2}\mu}&0&k{\alpha}\\\ &&&k{C_{M}^{2}\mu}&0\end{array}\right),$
${A_{k,k}}=\left({\begin{array}[]{ccccc}-{(k\alpha+\lambda)}&&&&\\\
&{-\left({kC_{2}^{2}\mu+k\alpha+\lambda}\right)}&&&\\\ &&\ddots&&\\\
&&&{-\left({kC_{M-1}^{2}\mu+k\alpha+\lambda}\right)}&\\\
&&&&{-\left({kC_{M}^{2}\mu+\lambda}\right)}\end{array}}\right),$
${A_{k,k+1}}=\left(\begin{array}[]{cccc}\lambda&&&\\\ &\lambda&&\\\
&&\ddots&\\\ &&&\lambda\end{array}\right).$

In what follows we apply the mean drift method (e.g., see Chapter 3 in Li
[57]) to study the stability of the level-dependent QBD process $Q$
corresponding to the DAG-based blockchain system.

The following theorem provides a necessary and sufficient condition under
which the level-dependent QBD $Q$ must be irreducible and positive recurrent.

###### Theorem 1

The level-dependent QBD $Q$ must be irreducible and positive recurrent. Thus,
the DAG-based blockchain system is positive recurrent.

Proof: The irreducibility of this QBD process $Q$ can be directly checked from
Figure 2. Therefore, in what follows we only need to prove that it is positive
recurrent.

Note that the QBD process $Q$ is irreducible, level-dependent and each of its
levels has finite states. Thus, we apply the mean drift method to compare the
upward mean drift rate with the downward mean drift rate on Level $k$ for a
larger positive integer $k\geq 1$.

For a larger positive integer $k\geq 1$, we have

$\displaystyle{\mathbf{A}_{k}}$
$\displaystyle={A_{k,k-1}}+{A_{k,k}}+{A_{k,k+1}}$
$\displaystyle=\left(\begin{array}[]{ccccc}{-k\alpha}&{k\alpha}&&&\\\
{kC_{2}^{2}\mu}&{-\left({kC_{2}^{2}\mu+k\alpha}\right)}&{k\alpha}&&\\\
&\ddots&\ddots&\ddots&\\\
&&{kC_{M-1}^{2}\mu}&{-\left({kC_{M-1}^{2}\mu+k\alpha}\right)}&{k\alpha}\\\
&&&{kC_{M}^{2}\mu}&-{kC_{M}^{2}\mu}\end{array}\right).$

It is easy to see that the Markov process $\mathbf{A}_{k}$ is irreducible,
aperiodic and finite states. Thus, the Markov process $\mathbf{A}_{k}$ must be
positive recurrent.

Let $\beta^{(k)}=(\beta_{1}^{(k)},\beta_{2}^{(k)},...,\beta_{M}^{(k)})$ be the
stationary probability vector of the Markov process $\mathbf{A}_{k}$. Then
$\beta^{(k)}\mathbf{A}_{k}=0$ and $\beta^{(k)}e=1$, where $e$ is a column
vector of size $M$ whose components are all ones. Now, we solve the system of
linear equations: $\beta^{(k)}\mathbf{A}_{k}=0$ and $\beta^{(k)}e=1$, that is,

$\left\\{\begin{array}[]{l}-\alpha\beta_{1}^{\left(k\right)}+\mu\beta_{2}^{\left(k\right)}=0,\\\
\alpha\beta_{i-1}^{\left(k\right)}-\left({C_{i}^{2}\mu+\alpha}\right)\beta_{i}^{\left(k\right)}+C_{i+1}^{2}\mu\beta_{i+1}^{\left(k\right)}=0{,}\text{
}2\leq i\leq M-1,\\\ \alpha\beta_{M-1}^{\left(k\right)}-\mu
C_{M}^{2}\beta_{M}^{\left(k\right)}=0.\end{array}\right.\ $ (1)

We obtain

$\beta_{2}^{\left(k\right)}=\frac{\alpha}{\mu}\beta_{1}^{\left(k\right)}=\frac{1}{{C_{2}^{2}}}\left({\frac{\alpha}{\mu}}\right){\beta_{1}}^{\left(k\right)},\
$
$\beta_{3}^{\left(k\right)}=\frac{1}{3}{\left({\frac{\alpha}{\mu}}\right)^{2}}\beta_{1}^{\left(k\right)}=\frac{1}{{C_{2}^{2}C_{3}^{2}}}{\left({\frac{\alpha}{\mu}}\right)^{2}}{\beta_{1}}^{\left(k\right)},\
$
$\beta_{4}^{\left(k\right)}=\frac{1}{{18}}{\left({\frac{\alpha}{\mu}}\right)^{3}}\beta_{1}^{\left(k\right)}=\frac{1}{{C_{2}^{2}C_{3}^{2}C_{4}^{2}}}{\left({\frac{\alpha}{\mu}}\right)^{3}}{\beta_{1}}^{\left(k\right)},$

for ${5}\leq s\leq M$

$\beta_{s}^{\left(k\right)}=\frac{1}{{\prod\limits_{i=2}^{s}{C_{i}^{2}}}}{\left({\frac{\alpha}{\mu}}\right)^{s-1}}{\beta_{1}}^{\left(k\right)}{.}\
$

By using $\beta^{(k)}e=1$, we obtain

$\beta_{1}^{\left(k\right)}+\frac{1}{{C_{2}^{2}}}\left({\frac{\alpha}{\mu}}\right)\beta_{1}^{\left(k\right)}+\cdots+\frac{1}{{\prod\limits_{i=2}^{M}{C_{i}^{2}}}}{\left({\frac{\alpha}{\mu}}\right)^{M-1}}\beta_{1}^{\left(k\right)}=1,$

this gives

$\beta_{1}^{\left(k\right)}=\frac{1}{1{+\sum\limits_{j=2}^{M}{\frac{1}{{\prod\limits_{i=2}^{j}{C_{i}^{2}}}}}{{\left({\frac{\alpha}{\mu}}\right)}^{j-1}}}}\
.$

Thus the stationary probability vector of the Markov process $\mathbf{A}_{k}$
is given by

$\displaystyle\beta_{1}^{\left(k\right)}$
$\displaystyle=\frac{1}{1{+\sum\limits_{j=2}^{M}{\frac{1}{{\prod\limits_{i=2}^{j}{C_{i}^{2}}}}}{{\left({\frac{\alpha}{\mu}}\right)}^{j-1}}}},$
$\displaystyle\beta_{s}^{\left(k\right)}$
$\displaystyle=\frac{\frac{1}{{\prod\limits_{i=2}^{s}{C_{i}^{2}}}}{\left({\frac{\alpha}{\mu}}\right)^{s-1}}}{1{+\sum\limits_{j=2}^{M}{\frac{1}{{\prod\limits_{i=2}^{j}{C_{i}^{2}}}}}{{\left({\frac{\alpha}{\mu}}\right)}^{j-1}}}},\text{
\ }{2}\leq s\leq M.$

Clearly, the stationary probability vector $\beta^{(k)}$ is independent of the
number $k$.

Now, we calculate the upward and downward mean drift rates on Level $k$. It is
easy to check that the upward mean drift rate, from Level $k$ to Level $k+1$,
is given by

${\beta^{\left(k\right)}}{A_{k,k+1}}e={\beta^{\left(k\right)}}{\left({\lambda,\lambda,\ldots,\lambda}\right)^{T}}=\lambda{\beta^{\left(k\right)}}e=\lambda.$

Similarly, the downward mean drift rate, from Level $k$ to Level $k-1$, is
given by

$\displaystyle{\beta^{\left(k\right)}}{A_{k,k-1}}e$
$\displaystyle={\beta^{\left(k\right)}}{\left({k\alpha,k\left({\mu
C_{2}^{2}+\alpha}\right),k\left({\mu
C_{3}^{2}+\alpha}\right),\ldots,k\left({C_{M-1}^{2}\mu+\alpha}\right),C_{M}^{2}k\mu}\right)^{T}}$
$\displaystyle=k\alpha\left({{\beta_{1}}^{\left(k\right)}+{\beta_{2}}^{\left(k\right)}+{\beta_{3}}^{\left(k\right)}+\cdots+\beta_{M-1}^{\left(k\right)}}\right)$
$\displaystyle+k\mu\left({C_{2}^{2}{\beta_{2}}^{\left(k\right)}+C_{3}^{2}{\beta_{3}}^{\left(k\right)}+\cdots+C_{M}^{2}\beta_{M}^{\left(k\right)}}\right)$
$\displaystyle=k\alpha\left(1-{\beta_{M}^{\left(k\right)}}\right)+k\mu{\sum\limits_{j=2}^{M}C_{j}^{2}{\beta_{j}}^{\left(k\right)}}.$

Thus, we get

${\beta^{\left(k\right)}}{A_{k,k-1}}e-{\beta^{\left(k\right)}}{A_{k,k+1}}e=k\alpha\left({1-\beta_{M}^{\left(k\right)}}\right)+k\mu{\sum\limits_{j=2}^{M}C_{j}^{2}{\beta_{j}}^{\left(k\right)}}-\lambda.$

Note that $\lambda$, $\alpha(1-\beta_{M}^{(k)})$ and
$\mu{\sum\limits_{j=2}^{M}C_{j}^{2}{\beta_{j}}^{\left(k\right)}}$ are positive
numbers and they are independent of the number $k$. Thus, it is easy to see
that as $k\rightarrow+\infty$,

$\beta^{(k)}A_{k,k-1}e-\beta^{(k)}A_{k,k+1}e\rightarrow+\infty.$

In this case, there always exists a larger positive integer $K$ such that for
$l\geq K$,

$\beta^{(l)}A_{l,l-1}e-\beta^{(l)}A_{l,l+1}e>0.$

Thus, the downward mean drift rate is bigger than the upward mean drift rate,
that is,

$\beta^{(l)}A_{l,l-1}e>\beta^{(l)}A_{l,l+1}e.$

Therefore, we show that the continuous-time level-dependent QBD process $Q$ is
positive recurrent. This completes the proof. $\square$

##  4 Performance Analysis

In this section, we first compute the stationary probability vector of the
level-dependent QBD process by means of the RG-factorizations given in Li
[57]. Then we provide performance analysis of the DAG-based blockchain system.

Let

$p_{k,i}\left(t\right)=P\left\\{Q\left(t\right)=k{,}S\left(t\right)=i\right\\},\text{
}k\geq 0,1\leq i\leq M.$

Then since the level-dependent QBD process $Q$ is irreducible and positive
recurrent, we have

$\pi_{k,i}=\lim_{t\rightarrow\infty}p_{k,i}\left(t\right).$

We write

$\pi_{k}=\left(\pi_{k,1},\pi_{k,2}{,\ldots,}\pi_{k,M}\right),\text{ \ }k\geq
0,$

and

$\pi=\left(\pi_{0},\pi_{1},\pi_{2}{,\ldots}\right)$

Note that the QBD process is level-dependent, we need to use the RG-
factorizations to compute the stationary probability vector. To this end, we
introduce $R$-, $U$\- and $G$\- measures as follows:

${U_{k}}={A_{k,k}}+{A_{k,k+1}}\left({-U_{k+1}^{-1}}\right){A_{k+1,k}},\text{{\
}}k\geq 0,$ ${R_{k}}={A_{k,k+1}}\left({-U_{k+1}^{-1}}\right),\text{{\ }}k\geq
0,$ ${G_{k}}=\left({-U_{k+1}^{-1}}\right){A_{k+1,k}},\text{{\ }}k\geq 1.$

On the other hand, by using Ramaswami and Taylor [81], the matrix sequence
$\\{{{R_{k}},k}\geq 0\\}$ is the minimum nonnegative solution of the system of
nonlinear matrix equations

${A_{k,k+1}}+{R_{k}}{A_{k+1,k+1}}+{R_{k}}{R_{k+1}}{A_{k+2,k+1}}=0,{k}\geq 0,\
$

and the matrix sequence $\\{{{G_{k}},k}\geq 1\\}$ is the minimum nonnegative
solution of the system of nonlinear matrix equations

${A_{k,k+1}}{G_{k+1}}{G_{k}+{A_{k,k}}{G_{k}+}A_{k,k-1}}=0,\text{{\ }}{k}\geq
1.\ $

Once $\\{{{R_{k}},k\geq 0}\\}$ or $\\{{{G_{k}},k}\geq 1\\}$ is determined, we
can get

${U_{k}}={A_{k,k}}+{R_{k}}{A_{k+1,k}=A_{k,k}}+{A_{k,k+1}}{G_{k+1}},\text{{\
}}{k}\geq 0.$

By using the $R$-, $U$\- and $G$\- measures and Li [57] or Li and Cao [58],
the UL-type RG-decomposition of the QBD process is given by

$Q=\left({I-{R_{U}}}\right){U_{D}}\left({I-{G_{L}}}\right),$

where

${U_{D}}=\text{diag}\left({{U_{0}},{U_{1}},{U_{2}},\ldots}\right),$

${R_{U}}=\left({\begin{array}[]{ccccc}0&{{R_{0}}}&&&\\\ &0&{{R_{1}}}&&\\\
&&0&{{R_{2}}}&\\\ &&&\ddots&\ddots\end{array}}\right),\text{{\
}}{G_{L}}=\left({\begin{array}[]{ccccc}0&&&&\\\ {{G_{1}}}&0&&&\\\
&{{G_{2}}}&0&&\\\ &&{{G_{3}}}&0&\\\ &&&\ddots&\ddots\end{array}}\right).$

###### Theorem 2

The stationary probability vector $\pi$ of the level-dependent QBD process $Q$
is given by

${\pi_{k}}=c{\tilde{\pi}_{k}},\text{{\ }}k\geq 0,\ $
${\tilde{\pi}_{k}}={\tilde{\pi}_{0}}{R_{0}}{R_{1}}\cdots{R_{k-1}},\text{{\
}}k\geq 1,$

where $\tilde{\pi}_{0}$ is uniquely determined by the system of linear
equations

${\tilde{\pi}_{0}}\left({{A_{0,0}}+{R_{0}A_{1,0}}}\right)=0,\ $
${\tilde{\pi}_{0}}e=1,\ $

and the constant $c$ is given by

$c=\frac{1}{{{{\tilde{\pi}}_{0}}e+\sum\limits_{k=1}^{\infty}{{{\tilde{\pi}}_{0}}{R_{0}}{R_{1}}\cdots{R_{k-1}}e}}}.$

Based on the stationary probability vector, we provide some steady-state
performance measures of the DAG-based blockchain system as follows:

(1) The steady-state average number of internal tips in the DAG-based
blockchain system is given by

$\displaystyle E\left[{{N_{A}}}\right]=$
$\displaystyle\left[{\left({{\pi_{1,1}+\pi_{1,2}+\pi_{1,3}+}\cdots+{\pi_{1,M}}}\right)+2\left({{\pi_{2,1}+\pi_{2,2}+\pi_{2,3}+}\cdots+{\pi_{2,M}}}\right)}\right.$
$\displaystyle\left.{+3\left({{\pi_{3,1}+\pi_{3,2}+\pi_{3,3}+}\cdots+{\pi_{3,M}}}\right)+\cdots}\right]$
$\displaystyle=$
$\displaystyle\sum\limits_{{k}=1}^{\infty}{k\cdot{\pi_{k}}e}=c\sum\limits_{k=1}^{\infty}{k\cdot{{\tilde{\pi}}_{k}}e}$
$\displaystyle=$ $\displaystyle
c\sum\limits_{{k}=1}^{\infty}{k{{\tilde{\pi}}_{1}}{R_{1}}}{R_{2}}\cdots{R_{k-1}}e.$

(2) The steady-state average number of boundary tips in the DAG-based
blockchain system is given by

$\displaystyle E\left[{{N_{B}}}\right]=$
$\displaystyle\left[{\left({{\pi_{0,1}}+{\pi_{1,1}+\pi_{2,1}+\pi_{3,1}+}\cdots}\right)+2\left({{\pi_{0,2}}+{\pi_{1,2}+\pi_{2,2}+\pi_{3,2}+}\cdots}\right)}\right.$
$\displaystyle\left.{+M\left({{\pi_{0,M}}+{\pi_{1,M}+\pi_{2,M}+\pi_{3,M}+}\cdots}\right)}\right]$
$\displaystyle=$
$\displaystyle\sum\limits_{k=0}^{\infty}{{\pi_{k}}{f_{A}=}}c{{\tilde{\pi}}_{0}}{f_{A}}+c\sum\limits_{k=1}^{\infty}{{{\tilde{\pi}}_{0}}{R_{0}}}{R_{1}}\cdots{R_{k-1}}{f_{A},}$

where $f_{A}=(1,2,...,M)^{T}$.

(3) The throughput of the DAG-based blockchain system

Note that the throughput of the DAG-based blockchain system is defined as the
number of new network nodes generated per unit of time, which is an important
indicator to measure the DAG-based blockchain system.

The following theorem provides expression for throughput of the DAG-based
blockchain system.

###### Theorem 3

If the DAG-based blockchain system is stable, then

$\displaystyle\text{TH}=$ $\displaystyle
2\mu\left[{\left({{\pi_{1,2}+C}_{3}^{2}{\pi_{1,3}+C}_{4}^{2}{\pi_{1,4}+}\cdots{+C}_{M}^{2}{\pi_{1,M}}}\right)}\right.$
$\displaystyle+2\left({{\pi_{2,2}+C}_{3}^{2}{\pi_{2,3}+C}_{4}^{2}{\pi_{2,4}+}\cdots{+C}_{M}^{2}{\pi_{2,M}}}\right)$
$\displaystyle+\left.{3\left({{\pi_{3,2}+C}_{3}^{2}{\pi_{3,3}+C}_{4}^{2}{\pi_{3,4}+}\cdots{+C}_{M}^{2}{\pi_{3,M}}}\right)+\cdots}\right]$
$\displaystyle=$ $\displaystyle
2\mu\sum\limits_{k=1}^{\infty}k{{\pi_{k}}}{f,}$

where $f=(0,1,C_{3}^{2},...,C_{M-1}^{2},C_{M}^{2})^{T}$.

Proof: From Figure 2, we observe that all the states $\left(m,n\right)$ for
$m\geq 1$ and $n\geq 2$ can generate the network nodes (i.e., the confirmed
blocks), seeing those bottom states of the brown arrows. Note that TH is the
product of $2\mu$ and the state probability sum that can generate the network
nodes. Let $P_{\text{TH}}$ denote the state probability sum that can generate
the network nodes. Accordingly, we need to compute the state probability sum
that can generate the network nodes.

For state $\left(1,2\right)$, the state probability that can generate the
network nodes is equal to $C_{2}^{2}\pi_{1,2}$. For state $\left(1,3\right)$,
the state probability that can generate the network nodes is equal to
$C_{3}^{2}\pi_{1,3}$. For state $\left(1,M\right)$, the state probability that
can generate the network nodes is equal to $C_{M}^{2}\pi_{1,M}$.

For state $\left(2,2\right)$, the state probability that can generate the
network nodes is equal to $2C_{2}^{2}\pi_{2,2}$. For state $\left(2,3\right)$,
the state probability that can generate the network nodes is equal to
$2C_{3}^{2}\pi_{2,3}$. For state $\left(2,M\right)$, the state probability
that can generate the network nodes is equal to $2C_{M}^{2}\pi_{2,M}$.

For state $\left(m,2\right)$, the state probability that can generate the
network nodes is equal to $mC_{2}^{2}\pi_{m,2}$. For state $\left(m,3\right)$,
the state probability that can generate the network nodes is equal to
$mC_{3}^{2}\pi_{m,3}$. For state $\left(m,M\right)$, the state probability
that can generate the network nodes is equal to $mC_{M}^{2}\pi_{m,M}$.

Based on analysis of the above special cases, we obtain

$\displaystyle P_{\text{TH}}=$
$\displaystyle{\left({{\pi_{1,2}+C}_{3}^{2}{\pi_{1,3}+C}_{4}^{2}{\pi_{1,4}+}\cdots{+C}_{M}^{2}{\pi_{1,M}}}\right)}$
$\displaystyle+2\left({{\pi_{2,2}+C}_{3}^{2}{\pi_{2,3}+C}_{4}^{2}{\pi_{2,4}+}\cdots{+C}_{M}^{2}{\pi_{2,M}}}\right)$
$\displaystyle+{3\left({{\pi_{3,2}+C}_{3}^{2}{\pi_{3,3}+C}_{4}^{2}{\pi_{3,4}+}\cdots{+C}_{M}^{2}{\pi_{3,M}}}\right)+\cdots}$
$\displaystyle=$ $\displaystyle\sum\limits_{k=1}^{\infty}k{{\pi_{k}}}{f,}$

Thus, we obtain

$\text{TH}=2\mu\times
P_{\text{TH}}=2\mu\sum\limits_{k=1}^{\infty}k{{\pi_{k}}}{f.}$

This completes the proof. $\square$

###### Remark 3

Under the complicated structure of the DAG-based blockchain systems, this
paper may be the first one to provide an exact computational formula for the
throughput of the DAG-based blockchain systems.

##  5 The Sojourn Time of Any Arriving Internal tip

In this section, we provide a new efficient method to compute the average
sojourn time of any arriving internal tip (or arriving transaction) at the
DAG-based blockchain system.

The sojourn time of any arriving internal tip at the DAG-based blockchain
system is the time interval from the arrival epoch of the new transaction to
the time that it finally becomes a network node. Obviously, such a sojourn
time includes two different processes: the internal tip is changed to a
boundary tip, and the boundary tip is changed to a network node.

Let $W_{A}$ be the sojourn time of the arriving internal tip A in the DAG-
based blockchain system. For the convenience of computation, we assume that
the arriving internal tip A arrives at the DAG-based blockchain system at time
$0$.

Let $I(t)$ and $J(t)$ denote the number of internal tips excluding the
arriving internal tip A and the number of boundary tips excluding the one
generated from the arriving internal tip A in the DAG-based blockchain system
at time $t$, respectively. Let $\Delta$ be an absorbing state that the
arriving internal tip A is finally changed to a network node.

It is easy to see that $\\{(1,I(t);J(t)),(I(t);1,J(t)){:}$ $t\geq{0}\\}$ is a
Markov process with the absorbing state $\Delta$. In state $(1,I(t);J(t))$,
$1$ means the arriving internal tip A; in state $(I(t);1,J(t))$, $1$ means a
boundary tip who is generated from the arriving internal tip A. Based on this,
the state space of Markov process $\\{(1,I(t);J(t)),(I(t);1,J(t)){:}$
$t\geq{0}\\}$ is given by

$\Theta=\left\\{\Delta\right\\}\cup\left\\{\bigcup\limits_{k=0}^{\infty}\text{Level
}k\right\\},$

where,

$\text{Level
}k=\left\\{\left(1,k;1\right),(k;1,0);\left(1,k;2\right),(k;1,1);\ldots;\left(1,k;M\right),(k;1,M-1)\right\\}.$

By using the level structure of the state space $\Theta$, Figure 3a, 3b and 3c
depict the state transition relations of the Markov process
$\\{(1,I(t);J(t)),(I(t);1,J(t)){:}$ $t\geq{0}\\}$.

(a)

(b)

(c)

Figure 3: State transition relations of the Markov process.

###### Remark 4

(i) Figure 3a contains three events: (1) Arrivals of internal tips (i.e., new
transactions), (2) the internal tip A is changed to the boundary tip A due to
its impatient behavior, and (3) the internal tip A, connecting (or approving)
two boundary tips, is changed to the boundary tip A.

(ii) Figure 3b contains two events: (1) The internal tips excluding the
internal tip A are changed to the boundary tips due to their impatient
behavior, and (2) the internal tips, excluding the internal tip A, connecting
(or approving) two boundary tips, are changed to the boundary tips.

(iii) Figure 3c contains one event: The boundary tip A is changed to a network
node.

From Figure 3a, 3b and 3c, it is easy to check that the infinitesimal
generator of the Markov process $\\{(1,I(t);J(t)),(I(t);1,J(t)){:}$
$t\geq{0}\\}$ with the absorbing state $\Delta$ is given by

$\mathbf{T}=\left(\begin{array}[]{cc}0&\mathbf{0}\\\
T{{}^{\Delta}}&T\end{array}\right)$

where

$T{{}^{\Delta}}+Te=0,$
$T=\left(\begin{array}[]{ccccc}{{T_{0,0}}}&{{T_{0,1}}}&&&\\\
{{T_{1,0}}}&{{T_{1,1}}}&{{T_{1,2}}}&&\\\
&{{T_{2,1}}}&{{T_{2,2}}}&{{T_{2,3}}}&\\\
&&\ddots&\ddots&\ddots\end{array}\right),\text{ \
}T{{}^{\Delta}}=\left(\begin{array}[]{c}T{{}_{0}^{\Delta}}\\\
T{{}_{1}^{\Delta}}\\\ T{{}_{2}^{\Delta}}\\\ \vdots\end{array}\right),$
$\text{\
}T_{i}^{\Delta}=\left(0,0;0,{iC_{1}^{1}\mu;}0,{iC_{2}^{1}\mu;}0,{iC_{3}^{1}\mu;\ldots;}0,{iC_{M-1}^{1}\mu}\right)^{T};$

$T{{}_{i,i+1}=}\left({\begin{array}[]{cccc}\lambda&&&\\\ &\lambda&&\\\
&&\ddots&\\\ &&&\lambda\end{array}}\right),\text{ }i\geq 0,$

$T{{}_{0,0}=}\left(\begin{array}[]{ccccc}{{A_{1,1}}}&{{A_{1,2}}}&&&\\\
{{A_{2,1}}}&{{A_{2,2}}}&{{A_{2,3}}}&&\\\ &\ddots&\ddots&\ddots&\\\
&&{{A_{M-1,M-2}}}&{{A_{M-1,M-1}}}&{{A_{M-1,M}}}\\\
&&&{{A_{M,M-1}}}&{{A_{M,M}}}\end{array}\right).$

${A_{1,1}}=\left({\begin{array}[]{cc}{-\left({\alpha+\lambda}\right)}&\\\
&{-\lambda}\end{array}}\right),{\ \
A_{1,2}}=\left({\begin{array}[]{cc}&\alpha\\\ &\end{array}}\right),$

for $2\leq l\leq M-1,$

${A_{l,l-1}}=\left({\begin{array}[]{cc}&{C_{l}^{2}\mu}\\\
&\end{array}}\right),{A_{l,l}}=\left({\begin{array}[]{cc}{-\left({C_{l}^{2}\mu+\alpha+\lambda}\right)}&\\\
&{-\lambda}\end{array}}\right),{A_{l,l+1}}=\left({\begin{array}[]{cc}\alpha&\\\
&\end{array}}\right),$

${A_{M,M-1}}=\left({\begin{array}[]{cc}&{C_{M}^{2}\mu}\\\
&\end{array}}\right),\text{ \
}{A_{M,M}}=\left({\begin{array}[]{cc}{-\left({C_{M}^{2}\mu+\lambda}\right)}&\\\
&{-\lambda}\end{array}}\right),$

$T{{}_{i,i-1}}=\left(\begin{array}[]{ccccc}0&{{B_{1,2}}}&&&\\\
{{B_{2,1}}}&0&{{B_{2,3}}}&&\\\ &\ddots&\ddots&\ddots&\\\
&&{{B_{M-1,M-2}}}&0&{{B_{M-1,M}}}\\\ &&&{{B_{M,M-1}}}&0\end{array}\right),$

for $1\leq l\leq M-1,$

${B_{l,l+1}}=\left({\begin{array}[]{cc}{i\alpha}&\\\
&{i\alpha}\end{array}}\right),$

${B_{2,1}}=\left({\begin{array}[]{cc}{i\mu}&\\\ &0\end{array}}\right),$

for $3\leq l\leq M,$

${B_{l,l-1}}=\left({\begin{array}[]{cc}{iC_{l}^{2}\mu}&\\\
&{iC_{l-1}^{2}\mu}\end{array}}\right),$

$T{{}_{i,i}}=\left(\begin{array}[]{cccccc}{{C_{1,1}}}&{{C_{1,2}}}&&&&\\\
{{C_{2,1}}}&{{C_{2,2}}}&{{C_{2,3}}}&&&\\\ &\ddots&\ddots&\ddots&&\\\
&&{{C_{M-2,M-3}}}&{{C_{M-2,M-2}}}&{{C_{M-2,M-1}}}&\\\
&&&{{C_{M-1,M-2}}}&{{C_{M-1,M-1}}}&\\\
&&&&{{C_{M,M-1}}}&{{C_{M,M}}}\end{array}\right),i\geq 1,$

${C_{1,1}}=\left({\begin{array}[]{cc}{-\left({\alpha+i\alpha+\lambda}\right)}&\\\
&{-\left({i\alpha+\lambda}\right)}\end{array}}\right),{C_{1,2}}=\left({\begin{array}[]{cc}&\alpha\\\
&\end{array}}\right),$

${C_{2,1}}=\left({\begin{array}[]{cc}&\mu\\\
&\end{array}}\right),{C_{2,3}}=\left({\begin{array}[]{cc}&\alpha\\\
&\end{array}}\right),$
${C_{2,2}}=\left({\begin{array}[]{cc}{-\left({\mu+\alpha+i\mu+i\alpha+\lambda}\right)}&\\\
&{-\left({i\alpha+\lambda+i\mu}\right)}\end{array}}\right),$

${C_{M-1,M-2}}=\left({\begin{array}[]{cc}&{C_{M-1}^{2}\mu}\\\
&\end{array}}\right),\text{ \
}{C_{M-1,M}}=\left({\begin{array}[]{cc}&\alpha\\\ &\end{array}}\right),$

${C_{M-1,M-1}}=\left({\begin{array}[]{cc}{-\left({C_{M-1}^{2}\mu+iC_{M-1}^{2}\mu+i\alpha+\lambda}\right)}&\\\
&{-\left({iC_{M-2}^{2}\mu+i\alpha+\lambda+iC_{M-2}^{1}\mu}\right)}\end{array}}\right),$

${C_{M,M-1}}=\left({\begin{array}[]{cc}&{C_{M}^{2}\mu}\\\
&\end{array}}\right),$

${C_{M,M}}=\left({\begin{array}[]{cc}{-\left({C_{M}^{2}\mu+iC_{M}^{2}\mu+\lambda}\right)}&\\\
&{-\left({iC_{M-1}^{2}\mu+\lambda+iC_{M-1}^{1}\mu}\right)}\end{array}}\right),$

for $3\leq l\leq M-2,$

${C_{l,l-1}}=\left({\begin{array}[]{cc}&{C_{l}^{2}\mu}\\\
&\end{array}}\right),{C_{l,l+1}}=\left({\begin{array}[]{cc}&\alpha\\\
&\end{array}}\right),$

${C_{l,l}}=\left({\begin{array}[]{cc}{-\left({C_{l}^{2}\mu+\alpha+iC_{l}^{2}\mu+i\alpha+\lambda}\right)}&\\\
&{-\left({iC_{l-1}^{2}\mu+i\alpha+\lambda+iC_{l-1}^{1}\mu}\right)}\end{array}}\right).$

Let $(\theta_{\Delta},\theta\mathbf{)}$ be the initial probability vector of
the Markov process $T$ with an absorbing state $\Delta$ for
$\theta_{\Delta}=0$, the vector ${\theta}=(0,0,...,0,1,0,...)$ shows that the
Markov process $T$ is at the state $(1,i_{0};j_{0})$ at time $0$. Therefore,
the $\left(2Mi_{0}+2j_{0}-1\right)$-st element of the vector $\theta$ is $1$,
and all the other elements are $0$.

The following theorem provides expression for the probability distribution of
the sojourn time $W_{A}$ by means of the first passage times and the phase-
type distributions of infinite sizes.

###### Theorem 4

The probability distribution of the sojourn time $W_{A}$ is of phase-type with
an irreducible representation $(\theta\mathbf{,}T\mathbf{)}$, and

${F_{{W_{A}}}}\left(t\right)=P\left\\{W_{A}\leq
t\right\\}=1-\theta\exp\left\\{Tt\right\\}e,\text{ }t\geq 0.$

Also, the average sojourn time $W_{A}$ is given by

$E\left[{{W_{A}}}\right]=-\theta T_{\max}^{-1}e,$

where $T_{\max}^{-1}$ is the maximal non-positive inverse of the matrix $T$ of
infinite sizes.

Proof: For $i\geq 0,$ $1\leq j\leq M$ and $0\leq n\leq M-1$, we write

$q_{1,i;j}\left(t\right)=P\left\\{I\left(t\right)=i{,}J\left(t\right)=j\right\\},$
$q_{i;1,n}\left(t\right)=P\left\\{I\left(t\right)=i,J\left(t\right)=n\right\\},$
$q_{i}\left(t\right)=\left(q_{1,i;1}\left(t\right),q_{i;1,0}\left(t\right);q_{1,i;2}\left(t\right),q_{i;1,1}\left(t\right);\ldots;q_{1,i;M}\left(t\right),q_{i;1,M-1}\left(t\right)\right),$
$q\left(t\right)=\left(q_{0}\left(t\right),q_{1}\left(t\right),q_{2}\left(t\right),\ldots\right).$

By using the Chapman-Kolmogorov forward differential equation, we obtain

$\frac{\mathrm{d}}{{\mathrm{d}t}}q\left(t\right)=q\left(t\right)T,\ $ (2)

with the initial conditions

$q\left(0\right)=\theta.\ $ (3)

It follows from (2) and (3) that

$q\left(t\right)=\theta\exp\left\\{Tt\right\\}{.}\ $ (4)

Note that $q(0)e=1$, it follows from (4) that

${F_{W_{A}}}\left(t\right)=P\left\\{W_{A}\leq
t\right\\}=1-\theta\exp\left\\{Tt\right\\}e,\text{{\ }}t\geq 0.$

In what follows we compute the average sojourn time $E\left[W_{A}\right]$ by
the Laplace-Stieltjes transform. Let $f(s)$ be the Laplace-Stieltjes transform
of the distribution function ${F_{{W_{A}}}}\left(t\right)$ or the random
variable $W_{A}$. Then

$f\left(s\right)=\int_{0}^{\infty}{{e^{-st}}}\text{{d}}{F_{{W_{A}}}}\left(t\right)=1+\theta\left(sI-T\right)_{\min}^{-1}T^{0},\
$

where $\left(sI-T\right)_{\min}^{-1}$ is the minimal non-negative inverse of
the matrix $sI-T$ of infinite sizes for $s\geq 0$. Therefore, we obtain

$E\left[W_{A}\right]=-\frac{\mathrm{d}}{{\mathrm{d}s}}f{\left(s\right)_{\mathrm{|}s=0}}=\theta{\left[\left(sI-T\right)_{\min}^{-2}\right]_{|s=0}}T^{0}=-\theta
T_{\max}^{-1}e.$

This completes the proof. $\square$

To compute the inverse matrix $T_{\max}^{-1}$, we need to use the RG-
decomposition of the Markov process $T$. To this end, we introduce $R$-, $U$\-
and $G$\- measures as follows:

$U_{i}=T_{i,i}+T_{i,i+1}\left({-}U_{i+1}^{-1}\right)T_{i+1,i},\text{ \ }i\geq
0,$ $R_{i}=T_{i,i+1}\left(-U_{i+1}^{-1}\right),\text{ \ }i\geq 0,$
$G_{i}=\left(-U_{i+1}^{-1}\right)T_{i+1,i},\text{ \ }i\geq 1.$

By using the $R$-, $U$\- and $G$\- measures, the UL-type RG-decomposition of
the QBD process $T$ is given by

$T=\left(I-R_{U}\right)U_{D}\left(I-G_{L}\right),$

where

$U_{D}=\text{diag}\left({{U_{0}},{U_{1}},{U_{2}},\ldots}\right),$
$R_{U}=\left({\begin{array}[]{ccccc}0&R_{0}&&&\\\ &0&R_{1}&&\\\ &&0&R_{2}&\\\
&&&\ddots&\ddots\end{array}}\right),\text{
}G_{L}=\left({\begin{array}[]{ccccc}0&&&&\\\ G_{1}&0&&&\\\ &G_{2}&0&&\\\
&&G_{3}&0&\\\ &&&\ddots&\ddots\end{array}}\right){.}$

We write

${X}_{k}^{\left(l\right)}=R_{l}R_{l+1}\cdots R_{l+k-1},\text{ \ }k\geq 1,l\geq
0,$ $Y_{k}^{\left(l\right)}=G_{l}G_{l-1}\cdots G_{l-k+1},\text{ \ }1\leq k\leq
l,$

and

$U_{D}^{-1}=\text{diag}\left(U_{0}^{-1},U_{1}^{-1},U_{2}^{-1},\ldots\right).$

By using the UL-type RG-factorization, we obtain

$T_{\max}^{-1}=\left(I-G_{L}\right)^{-1}U_{D}^{-1}\left(I-R_{U}\right)^{-1},$

where

$\left(I-R_{U}\right)^{-1}=\left({\begin{array}[]{ccccc}I&{X_{1}^{\left(0\right)}}&{X_{2}^{\left(0\right)}}&{X_{3}^{\left(0\right)}}&\cdots\\\
&I&{X_{1}^{\left(1\right)}}&{X_{2}^{\left(1\right)}}&\cdots\\\
&&I&{X_{1}^{\left(2\right)}}&\cdots\\\ &&&I&\cdots\\\
&&&&\ddots\end{array}}\right).$
$\left(I-G_{L}\right)^{-1}=\left({\begin{array}[]{ccccc}I&&&&\\\
Y_{1}^{\left(1\right)}&I&&&\\\
Y{{}_{2}^{\left(2\right)}}&{Y_{1}^{\left(2\right)}}&I&&\\\
{Y_{3}^{\left(3\right)}}&{Y_{2}^{\left(3\right)}}&{Y_{1}^{\left(3\right)}}&I&\\\
\vdots&\vdots&\vdots&\vdots&\ddots\end{array}}\right),$

Let

$T_{\max}^{-1}=\left(\begin{array}[]{cccc}V_{0,0}&V_{0,1}&V_{0,2}&\cdots\\\
V_{1,0}&V_{1,1}&V_{1,2}&\cdots\\\ V_{2,0}&V_{2,1}&V_{2,2}&\cdots\\\
\vdots&\vdots&\vdots&\ddots\end{array}\right).$

Then by using $T_{\max}^{-1}=(I-G_{L})^{-1}(U_{D})^{-1}(I-R_{U})^{-1}$, we
obtain

$V_{m,n}=\left\\{\begin{array}[]{ll}U_{m}^{-1}Y_{m-n}^{\left(m\right)}+\sum\limits_{i=1}^{\infty}X_{i}^{\left(m\right)}U_{i+m}^{-1}Y_{i+m-n}^{\left(i+m\right)}{,}&0\leq
n\leq m-1,\\\
U{{}_{m}^{-1}+\sum\limits_{i=1}^{\infty}}X{{{}_{i}^{\left(m\right)}}}U{{{}_{i+m}^{-1}}}Y{{{}_{i}^{\left(i{+m}\right)},}}&n=m,\\\
X{{}_{n-m}^{\left(m\right)}}U{{}_{n}^{-1}+\sum\limits_{i=n-m+1}^{\infty}}X{{{}_{i}^{\left(m\right)}}}U{{{}_{i+m}^{-1}}}Y{{{}_{i-n+m}^{\left({i+m}\right)},}}&n\geq
m+1.\end{array}\right.$

The average sojourn time of the arriving internal tip A in the DAG-based
blockchain system is given by

$\displaystyle E\left[W_{A}\right]$ $\displaystyle=-\theta
T_{\max}^{-1}e=-\theta\left(I-G_{L}\right)^{-1}U_{D}^{-1}\left(I-R_{U}\right)^{-1}e$
$\displaystyle=-\sum\limits_{i=1}^{\infty}\sum\limits_{j=0}^{\infty}\theta_{i}V_{i-1,j}e.$

##  6 Numerical Examples

In this section, we use numerical examples to check the validity of our
theoretical results, and indicate how some key system parameters influence the
performance measures of the DAG-based blockchain system. To do this, our
analysis is to focus on two issues: (1) Steady-state performance indicators of
the DAG-based blockchain system. (2) The average sojourn time
$E\left[W_{A}\right]$ of the arriving internal tip A.

###  6.1 Steady-state performance measures

Firstly, we discuss how the steady-state performance measures of the DAG-based
blockchain system are affected by the three key system parameters: $\alpha$,
$\mu$ and $\lambda$.

In Figures 4 and 5, we take that $M=100$, $\alpha=0.45$, $\lambda\in[20,40]$,
and $\mu=3.5,$ $4,$ $5$. From Figure 4, it is easy to see that $E[N_{A}]$
increases as $\lambda$ increases, while $E[N_{A}]$ decreases as $\mu$
increases. From Figure 5, we observe how $E[N_{B}]$ changes as $\lambda$
increases. It can be seen that $E[N_{B}]$ increases as $\lambda$ increases,
while $E[N_{B}]$ decreases as $\mu$ increases.

Figure 4: $E[N_{A}]$ vs $\lambda$ and $\mu$ Figure 5: $E[N_{B}]$ vs $\lambda$
and $\mu$

A coupling analysis: Note that the two numerical results can be intuitively
understood by means of a coupling method. As $\lambda$ increases, more and
more internal tips (or new transactions) are quickly entering the DAG-based
blockchain system. Thus, this makes $E[N_{A}]$ and $E[N_{B}]$ increase. On the
other hand, when $\alpha$ is constant and as $\mu$ increases, more and more
internal tips are quickly leaving the set of internal tips. Because the tip
number in the set of boundary tips decreases due to the connection of each
internal tip with two boundary tips, this leads to the decrease of $E[N_{A}]$
and $E[N_{B}]$ accordingly.

In Figure 6, we explore how TH is influenced by parameters $\lambda$ and
$\mu$. To this end, we take that $M=100$, $\alpha=0.45$, $\lambda\in[20,40]$,
and $\mu=2,$ $2.5,$ $3$. From Figure 6, it is observed that TH increases as
$\lambda$ or $\mu$ increases. This indicates that as $\lambda$ and $\mu$
increase, more and more network nodes (or confirmed transactions) are quickly
entering the DAG-based blockchain system, which leads to the increase of TH.
For this result, we can give an intuitive explanation based on the results in
Figures 4 and 5. From Figures 4 and 5, we can know that as $\lambda$
increases, more and more internal tips (or new transactions) can become
boundary tips, so more and more boundary tips will have the opportunity to
become network nodes (or confirmed transactions), which makes TH increases. In
addition, as $\mu$ increases, it causes that more and more boundary tips to
become network nodes (or confirmed transactions), and this leads to increase
of TH, which is consistent with our intuitive understanding.

Figure 6: TH vs $\lambda$ and $\mu$

###  6.2 The average sojourn time of the arriving internal tip A

In this subsection, we analyze how the average sojourn time of the arriving
internal tip A is affected by the three key system parameters: $\alpha$,
$\mu$, and $\lambda$. In this part, we let $M=50$ for all the numerical
examples.

In Figure 7, we observe how $E[W_{A}]$ is influenced by parameters: $\alpha$
and $\mu$. To this end, we take that $\alpha=0.3,0.4,0.5$, $\lambda=30$, and
$\mu\in\left[2,9\right]$. It is easy to see from Figure 7 that $E[W_{A}]$
decreases as $\mu$ or $\alpha$ increases. This indicates that as $\mu$ or
$\alpha$ increases, that is, the rate that tips become network nodes (or
confirmed transactions) increases, then the probability of the arriving
internal tip A being approved or connected increases, which makes the average
sojourn time of the arriving internal tip A decreases, which is consistent
with our intuitive understanding. Furthermore, this result also indicates that
the impatient behavior introduced by us can prevent some tips from staying for
too much time in the system.

Figure 7: $E[W_{A}]$ vs $\mu$ and $\alpha$

In Figure 8, we explore how $E[W_{A}]$ is influenced by parameters $\alpha$
and $\lambda$. To this end, we take that $\mu=5$, $\alpha=0.3,0.35,0.4$,
$\lambda\in\left[20,40\right]$. It is easy to see from Figure 8 that
$E[W_{A}]$ increases as $\lambda$ increases, while it decreases as $\alpha$
increases. This result indicates that as $\lambda$ increases, $E[N_{A}]$ and
$E[N_{B}]$ increase based on the results in Figures 4 and 5. This causes the
probability of the arriving internal tip A being approved or connected to
decrease, and then the average sojourn time of the arriving internal tip A
increases. On the other hand, as $\alpha$ increases, the rate that tips become
network nodes (or confirmed transactions) increases, then the probability of
the arriving internal tip A being approved or connected increases. This leads
to the average sojourn time of the arriving internal tip A decreases, which is
also consistent with our intuitive sense.

Figure 8: $E[W_{A}]$ vs $\lambda$ and $\alpha$

In Figure 9, we indicate how $E[W_{A}]$ is affected by the two parameters
$\mu$ and $\lambda$. To this end, we take that $\alpha=0.3$, $\mu=3.5,4,5$ and
$\lambda\in[20,40]$. From Figure 9, we can see that $E[W_{A}]$ increases as
$\lambda$ increases, which is consistent with the results in Figure 8. At the
same time, we can see from Figure 9 that as $\mu$ increases, $E[W_{A}]$
decreases as $\mu$ increases. This result indicates that as $\mu$ increases,
the rate at which internal tips become boundary tips and network nodes (or
confirmed transactions) increases, then the probability of the arriving
internal tip A being approved or connected increases. These lead to the
decrease of the average sojourn time of the arriving internal tip A. This
numerical result is also consistent with our intuition.

Figure 9: $E[W_{A}]$ vs $\lambda$ and $\mu$

##  7 Concluding Remarks

Since Bitcoin was proposed by Nakamoto [66] in 2008, the serial structure of
blockchain has achieved rapid development. Important examples include Bitcoin,
Litecoin, Ethereum and so on, and the consensus mechanisms such as PoW, PoS,
DPoS and PBFT are widely used. However, such a serial structure has a number
of essential pitfalls, for example, poor performance and scalability, limited
transaction throughput, high transaction cost, long confirmation delay, huge
energy expenditure, and so forth.

To overcome these pitfalls and drawbacks of blockchain, a data network
structure was found in the DAG-based blockchain with IOTA Tangle. From such a
network perspective, it is well-known that the analysis of the DAG-based
blockchain systems becomes interesting but difficult and challenging. To
investigate the DAG-based blockchain, so far, the simulation models have been
adopted widely while the mathematical modeling and analysis is still scarce in
the recent literature. To our best knowledge, this paper may be the first to
set up theory of Markov processes in the study of DAG-based blockchain
systems.

In this paper, we describe a simple Markov model for the DAG-based blockchain
with IOTA Tangle. Then we set up a continuous-time level-dependent QBD process
to analyze the DAG blockchain system. We show that the QBD process must be
irreducible and positive recurrent. By using the stationary probability vector
of the QBD process, we provide a performance analysis of the DAG blockchain
system. We propose a new effective method for computing the average sojourn
time of any arriving internal tip at this system. Finally, we use numerical
examples to check the validity of our theoretical results and indicate how
some key system parameters influence the performance measures of this system.

Note that the Markov process theory opens up a new venue to the study of DAG
blockchain systems. Thus, we believe that the methodology and results
developed in this paper can shed light on the DAG blockchain systems and open
a series of potentially promising research. Along these lines, we will
continue our future research in the following directions:

– Considering the DAG blockchain systems with IOTA Tangle. From $2$
connections to $m$ connections of the boundary tips, we observe how the
multiple connections will affect the performance of the DAG blockchain system.

– Setting up a block-structure Markov process for the DAG blockchain systems
and develop an effective algorithm for computing the matrix-analytic solution.
Using the stationary probability vector, we can analyze the performance of the
DAG blockchain systems.

– Developing the fluid and diffusion approximation for analyzing the DAG
blockchain systems, when there are general random factors.

– Further developing stochastic optimization and dynamic control of the DAG
blockchain systems, for example, Markov decision processes, stochastic game,
evolutionary game and so forth.

##  8 Acknowledgements

Quan-Lin Li was supported by the National Natural Science Foundation of China
under grants No. 71671158 and 71932002.

## References

  * [1] Alshaikhli, M., Elfouly, T., Elharrouss, O., Mohamed, A., & Ottakath, N. (2021). Evolution of Internet of Things from Blockchain to IOTA: A survey. IEEE Access, 10, 844-866.
  * [2] Anwar, H. (2019). The ultimate comparison of different types of distributed ledgers: Blockchain vs hashgraph vs DAG vs holochain. 101 Blockchains.
  * [3] Attias, V., & Bramas, Q. (2019). How to choose its parents in the Tangle. In: International Conference on Networked Systems, Springer, Pages 275-280.
  * [4] Bai, C. (2018). State-of-the-art and future trends of Blockchain based on DAG structure. In: International Workshop on Structured Object-oriented Formal Language and Method, Springer, Pages 183-196.
  * [5] Belchior, R., Vasconcelos, A., Guerreiro, S., & Correia, M. (2021). A survey on blockchain interoperability: Past, present, and future trends. ACM Computing Surveys, 54(8), 1-41.
  * [6] Benčić, F. M., & Žarko, I. P. (2018). Distributed ledger technology: Blockchain compared to directed acyclic graph. In: The IEEE 38th International Conference on Distributed Computing Systems, Pages 1569-1570.
  * [7] Bhandary, M., Parmar, M., & Ambawade, D. (2020). A Blockchain solution based on directed acyclic graph for IoT data security using IOTA Tangle. In: The 5th International Conference on Communication and Electronics Systems, Pages 827-832.
  * [8] Birmpas, G., Koutsoupias, E., Lazos, P., & Marmolejo-Cossío, F. J. (2020). Fairness and efficiency in DAG-based cryptocurrencies. In: International Conference on Financial Cryptography and Data Security, Springer, Pages 79-96.
  * [9] Bottone, M., Raimondi, F., & Primiero, G. (2018). Multi-agent based simulations of block-free distributed ledgers. In: The 32nd International Conference on Advanced Information Networking and Applications Workshops, Pages 585-590.
  * [10] Bramas, Q. (2018). The stability and the security of the Tangle. HAL Id: hal-01716111.
  * [11] Bramas, Q. (2021). Efficient and secure TSA for the Tangle. In: International Conference on Networked Systems, Springer, Pages, 161-166.
  * [12] Brighente, A., Conti, M., Kumar, G., Ghanbari, R., & Saha, R. (2021). Knocking on Tangle’s doors: Security analysis of IOTA ports. In: The IEEE International Conference on Blockchain, Pages 433-439.
  * [13] Brunner, M., Cachin, C., & Sesar, I. A. (2021). Analysis of the Tangle: The Impact of Conflicting Blocks to the Tangle network. Bachelor Thesis, Institute of Computer Science, University of Bern, Switzerland.
  * [14] Cao, B., Zhang, Z., Feng, D., Zhang, S., Zhang, L., Peng, M., & Li, Y. (2020). Performance analysis and comparison of PoW, PoS and DAG based Blockchains. Digital Communications and Networks, 6(4), 480-485.
  * [15] Cao, K., Lin, F., Qian, C., & Li, K. (2019). A high efficiency network using DAG and consensus in Blockchain. In: The IEEE International Conference on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking, Pages 279-285.
  * [16] Chafjiri, F. S., & Esfahani, M. M. E. (2019). An adaptive random walk algorithm for selecting tips in the Tangle. In: The 5th International Conference on Web Research, Pages 161-166.
  * [17] Chen, T. Y., Huang, W. N., Kuo, P. C., Chung, H., & Chao, T. W. (2018). DEXON: A highly scalable, decentralized DAG-based consensus algorithm. arXiv preprint arXiv:1811.07525.
  * [18] Conti, M., Kumar, G., Nerurkar, P., Saha, R., & Vigneri, L. (2022). A survey on security challenges and solutions in the IOTA. Journal of Network and Computer Applications, 103383.
  * [19] Cui, L., Yang, S., Chen, Z., Pan, Y., Xu, M., & Xu, K. (2019). An efficient and compacted DAG-based Blockchain protocol for industrial Internet of Things. IEEE Transactions on Industrial Informatics, 16(6), 4134-4145.
  * [20] Cullen, A., Ferraro, P., King, C., & Shorten, R. (2019). Distributed ledger technology for IoT: Parasite chain attacks. arXiv preprint arXiv:1904.00996.
  * [21] Cullen, A., Ferraro, P., King, C., & Shorten, R. (2020). On the resilience of DAG-based distributed ledgers in IoT applications. IEEE Internet of Things Journal, 7(8), 7112-7122.
  * [22] Danezis, G., & Hrycyszyn, D. (2018). Blockmania: From block DAGs to consensus. arXiv preprint arXiv:1809.01620.
  * [23] Danezis, G., Kokoris-Kogias, L., Sonnino, A., & Spiegelman, A. (2022). Narwhal and tusk: a DAG-based mempool and efficient BFT consensus. In: Proceedings of the Seventeenth European Conference on Computer Systems, Pages 34-50.
  * [24] Deng, X., Li, K., Wang, Z., & Liu, H. (2022). A novel consensus algorithm based on segmented DAG and BP neural network for consortium Blockchain. Security and Communication Networks, Vol. 2022, Article ID 1060765.
  * [25] Ding, Y., & Sato, H. (2020). Dagbase: A decentralized database platform using DAG-based consensus. In: The IEEE 44th Annual Computers, Software, and Applications Conference, Pages 798-807.
  * [26] Dong, Z., Zheng, E., Choon, Y., & Zomaya, A. Y. (2019). Dagbench: A performance evaluation framework for DAG distributed ledgers. In: The IEEE 12th International Conference on Cloud Computing, Pages 264-271.
  * [27] Fan, C. (2019). Performance analysis and design of an IoT-friendly DAG-based distributed ledger system. Master of Science, Department of Electrical and Computer Engineering, University of Alberta.
  * [28] Fan, C., Ghaemi, S., Khazaei, H., Chen, Y., & Musilek, P. (2021). Performance analysis of the IOTA DAG-based distributed ledger. ACM Transactions on Modeling and Performance Evaluation of Computing Systems, 6(3), 1-20.
  * [29] Fan, C., Khazaei, H., Chen, Y., & Musilek, P. (2019). Towards a scalable DAG-based distributed ledger for smart communities. In: The IEEE 5th World Forum on Internet of Things, Pages 177-182.
  * [30] Ferrag, M. A., Derdour, M., Mukherjee, M., Derhab, A., Maglaras, L., & Janicke, H. (2018). Blockchain technologies for the internet of things: Research issues and challenges. IEEE Internet of Things Journal, 6(2), 2188-2204.
  * [31] Ferraro, P., King, C., & Shorten, R. (2018). IOTA-based directed acyclic graphs without orphans. arXiv preprint arXiv:1901.07302.
  * [32] Ferraro, P., King, C., & Shorten, R. (2019). On the stability of unverified transactions in a DAG-based distributed ledger. IEEE Transactions on Automatic Control, 65(9), 3772-3783.
  * [33] Ferraro, P., Penzkofer, A., King, C., & Shorten, R. (2022). Feedback control for distributed ledgers: An attack mitigation policy for DAG-based DLTs. arXiv preprint arXiv:2204.11691.
  * [34] Gangwani, P., Perez-Pons, A., Bhardwaj, T., Upadhyay, H., Joshi, S., & Lagos, L. (2021). Securing environmental IoT data using masked authentication messaging protocol in a DAG-based Blockchain: IOTA Tangle. Future Internet, 13(12), 312.
  * [35] Gao, Y., Liu, Y., Wen, Q., Lin, H., & Chen, Y. (2020). Secure drone network edge service architecture guaranteed by DAG-based Blockchain for flying automation under 5G. Sensors, 20(21), 6209.
  * [36] Gardner, R., Reinecke, P., & Wolter, K. (2020). Performance of tip selection schemes in DAG Blockchains. In: Mathematical Research for Blockchain Economy, Springer, Pages 101-116.
  * [37] Gerrits, L. (2020). Comparative study of EOS and IOTA Blockchains in the context of smart IoT for mobility. Doctoral dissertation, stage Master 2 Estel Université Nice-Sophia Antipolis.
  * [38] Gorbunova, M., Masek, P., Komarov, M., & Ometov, A. (2022). Distributed ledger technology: State-of-the-art and current challenges. Computer Science and Information Systems, 19(1), 65-85.
  * [39] Gorkhali, A., Li, L., & Shrestha, A. (2020). Blockchain: A literature review. Journal of Management Analytics, 7(3), 321-343.
  * [40] Guo, F., Xiao, X., Hecker, A., & Dustdar, S. (2020). Characterizing IOTA Tangle with empirical data. In: The 2020 IEEE Global Communications Conference, Pages 1-6.
  * [41] Gupta, H., & Janakiram, D. (2019). CDAG: A serialized blockdag for permissioned Blockchain. arXiv preprint arXiv:1910.08547.
  * [42] Gupta, A., & Krishnamurthy, V. (2022). Controlling transaction rate in Tangle Ledger: A principal agent problem approach. arXiv preprint arXiv:2203.05643.
  * [43] Hassine, M. B., Kmimech, M., Hellani, H., & Sliman, L. (2020). Toward a mixed Tangle-Blockchain architecture. In: Knowledge Innovation Through Intelligent Software Methodologies, Tools and Techniques, Pages 221-233.
  * [44] Hellani, H., Sliman, L., Hassine, M. B., Samhat, A. E., Exposito, E., & Kmimech, M. (2019). Tangle the Blockchain: Toward IOTA and Blockchain integration for IoT environment. In: International Conference on Hybrid Intelligent Systems, Springer, Pages 429-440.
  * [45] Hellani, H., Sliman, L., Samhat, A. E., & Exposito, E. (2021). Computing resource allocation scheme for DAG-based IOTA nodes. Sensors, 21(14), 4703.
  * [46] Huang, H., Kong, W., Zhou, S., Zheng, Z., & Guo, S. (2021). A survey of state-of-the-art on blockchains: Theories, modelings, and tools. ACM Computing Surveys, 54(2), 1-42.
  * [47] Igiri, C. P., Bhargava, D., Udanor, C., & Sowah, A. R. (2022). Blockchain versus IOTA Tangle for Internet of Things: The best architecture. In: Blockchain Technology, CRC Press, Pages 259-278.
  * [48] Jay, M., Mollard, A., Sun, Y., Zheng, R., Amigo, I., Reiffers-Masson, A., & Ruano Rincón, S. (2021). Utility maximisation in the Coordinator-less IOTA Tangle. In: International Symposium on Ubiquitous Networking, Springer, Pages 93-104.
  * [49] Keidar, I., Kokoris-Kogias, E., Naor, O., & Spiegelman, A. (2021). All you need is DAG. In: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, Pages 165-175.
  * [50] Khrais, L. T. (2020). Comparison study of Blockchain technology and IOTA technology. In: The Fourth International Conference on IoT in Social, Mobile, Analytics and Cloud, Pages 42-47.
  * [51] Kuśmierz, B. (2017). The first glance at the simulation of the Tangle: Discrete model. Vol. 1. IOTA Foundation Technical Report, Pages 1-10.
  * [52] Kuśmierz, B., & Gal, A. (2018). Probability of being left behind and probability of becoming permanent tip in the Tangle V0. 2. Vol. 1. No. 1. IOTA Foundation Technical Report, Pages 1–9.
  * [53] Kuśmierz, B., Sanders, W., Penzkofer, A., Capossele, A., & Gal, A. (2019). Properties of the Tangle for uniform random and random walk tip selection. In: 2019 IEEE International Conference on Blockchain, Pages 228-236.
  * [54] Kuśmierz, B., Staupe, P., & Gal, A. (2018). Extracting Tangle properties in continuous time via large-scale simulations. IOTA Found. White Paper, 2018-08.
  * [55] Lathif, M. R. A., Nasirifard, P., & Jacobsen, H. A. (2018). CIDDS: A configurable and distributed DAG-based distributed ledger simulation framework. In: Proceedings of the 19th International Middleware Conference, Pages 7-8.
  * [56] Lee, S. W., & Sim, K. B. (2021). Design and hardware implementation of a simplified DAG-based Blockchain and new AES-CBC algorithm for IoT security. Electronics, 10(9), 1127.
  * [57] Li, Q.L., 2010. Constructive Computation in Stochastic Models with Applications: The RG-Factorizations. Springer.
  * [58] Li, Q.L., Cao, J. (2004). Two types of RG-factorizations of quasi-birth-and-death processes and their applications to stochastic integral functionals. Stochastic Models, 20 (3), 299–340.
  * [59] Li, Q. L., Chang, Y., Wu, X., & Zhang, G. (2021). A new theoretical framework of pyramid markov processes for Blockchain selfish mining. Journal of Systems Science and Systems Engineering, 30(6), 667-711.
  * [60] Li, Q. L., Chang, Y. X., & Zhang, C. (2022). Tree representation, growth rate of Blockchain and reward allocation in Ethereum with multiple mining pools. arXiv preprint arXiv:2201.10087.
  * [61] Li, Y., Cao, B., Peng, M., Zhang, L., Zhang, L., Feng, D., & Yu, J. (2020). Direct acyclic graph-based ledger for Internet of Things: Performance and security analysis. IEEE/ACM Transactions on Networking, 28(4), 1643-1656.
  * [62] Liao, Z., Cheng, S., Zhang, J., Wu, W., Wang, J., & Sharma, P. K. (2022). GpDB: A graph-partition based storage strategy for DAG-Blockchain in edge-cloud IIoT. IEEE Transactions on Industrial Informatics. https://ieeexplore.ieee.org/document/9741329
  * [63] Lo, S. K., Liu, Y., Chia, S. Y., Xu, X., Lu, Q., Zhu, L., & Ning, H. (2019). Analysis of Blockchain solutions for IoT: A systematic literature review. IEEE Access, 7, 58822-58835.
  * [64] Madenouei, N. A. (2020). Exploring the scalability, throughput and security characteristics of the Tangle distributed ledger technology through simulation analysis. Master of Science, York University, Canada.
  * [65] Müller, S., Penzkofer, A., Polyanskii, N., Theis, J., Sanders, W., & Moog, H. (2022). Tangle 2.0: Leaderless Nakamoto consensus on the heaviest DAG. arXiv preprint arXiv:2205.02177.
  * [66] Nakamoto, S. (2008). Bitcoin: A peer-to-peer electronic cash system. Decentralized Business Review, 21260.
  * [67] Nakanishi, R., Zhang, Y., Sasabe, M., & Kasahara, S. (2020). IOTA-based access control framework for the Internet of Things. In: The 2nd Conference on Blockchain Research & Applications for Innovative Networks and Services, Pages 87-95.
  * [68] Nguyen, Q., Cronje, A., Kong, M., Lysenko, E., & Guzev, A. (2021). Lachesis: Scalable asynchronous BFT on DAG streams. arXiv preprint arXiv:2108.01900.
  * [69] Park, S., & Kim, H. (2019). DAG-based distributed ledger for low-latency smart grid network. Energies, 12(18), 3570.
  * [70] Park, S., Oh, S., & Kim, H. (2019). Performance analysis of DAG-based cryptocurrency. In: The IEEE International Conference on Communications workshops, Pages 1-6.
  * [71] Penzkofer, A., Kusmierz, B., Capossele, A., Sanders, W., & Saa, O. (2020). Parasite chain detection in the IOTA protocol. arXiv preprint arXiv:2004.13409.
  * [72] Penzkofer, A., Saa, O., & Dziubałtowska, D. (2021). Impact of delay classes on the data structure in IOTA. In: Data Privacy Management, Cryptocurrencies and Blockchain Technology, Springer, Pages 289-300.
  * [73] Perešíni, M., Benčić, F. M., Malinka, K., & Homoliak, I. (2021). DAG-oriented protocols PHANTOM and GHOSTDAG under incentive attack via transaction selection strategy. arXiv preprint arXiv:2109.01102.
  * [74] Pervez, H., Muneeb, M., Irfan, M. U., & Haq, I. U. (2018). A comparative analysis of DAG-based Blockchain architectures. In: The 12th International Conference on Open Source Systems and Technologies, Pages 27-34.
  * [75] Popov, S. (2016). The Tangle. Vol. 1. IOTA Foundation Technical Report, Pages 131–156.
  * [76] Popov, S. (2018). The Tangle. A white paper, Version 1.4.3, Pages 1-28.
  * [77] Popov, S., & Buchanan, W. (2019). Fast probabilistic consensus within Byzantine infrastructures. arXiv preprint arXiv: 1905.10895, Pages 1–30.
  * [78] Popov, S., Moog, H., Camargo, D., et al. (2020). The Coordicide. Vol. 1. No. 1. IOTA Foundation Technical Report, pp. 1–42.
  * [79] Popov, S., Saa, O., Finardi, P. (2019). Equilibria in the Tangle. Computers & Industrial Engineering, 136, 160–172.
  * [80] Reddy, B. S., & Sharma, G. V. V. (2020). Scalable consensus protocols for PoW based Blockchain and blockDAG. arXiv preprint arXiv:2010.05447.
  * [81] Ramaswami, V., & Taylor, P.G. (1996). Some properties of the rate perators in level dependent quasi-birth-and-death processes with countable number of phases. Stochastic Models, 12(1), 143-164.
  * [82] Schett, M. A., & Danezis, G. (2021). Embedding a deterministic BFT protocol in a block DAG. In: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, Pages 177-186.
  * [83] Shabandri, B., & Maheshwari, P. (2019). Enhancing IoT security and privacy using distributed ledgers with IOTA and the Tangle. In: The 6th International Conference on Signal Processing and Integrated Networks, Pages 1069-1075.
  * [84] Siim, J. (2018). DAG-based distributed ledgers. In: Research Seminar in Cryptology.
  * [85] Silvano, W. F., & Marcelino, R. (2020). Iota Tangle: A cryptocurrency to communicate Internet-of-Things data. Future Generation Computer Systems, 112, 307-319.
  * [86] Spiegelman, A., Giridharan, N., Sonnino, A., Kokoris-Kogias, L. (2022). Bullshark: DAG BFT protocols made practical. arXiv preprint arXiv:2201.05677.
  * [87] Staupe, P. (2017). Quasi-analytic parasite chain absorption probabilities in the Tangle. Vol. 20. IOTA Foundation Technical Report, Pages 15–18.
  * [88] Tian, H., Lin, H., & Zhang, F. (2020). Design a proof of stake based directed acyclic graph chain. In: International Conference on Frontiers in Cyber Security, Springer, Pages 150-165.
  * [89] Vigneri, L., Welz, W., Gal, A., & Dimitrov, V. (2019). Achieving fairness in the Tangle through an adaptive rate control algorithm. In: The IEEE International Conference on Blockchain and Cryptocurrency, Pages 146-148.
  * [90] Viriyasitavat, W., Anuphaptrirong, T., & Hoonsopon, D. (2019). When blockchain meets Internet of Things: Characteristics, challenges, and business opportunities. Journal of industrial information integration, 15, 21-28.
  * [91] Wang, B., Wang, Q., Chen, S., & Xiang, Y. (2020). Security analysis on Tangle-based Blockchain through simulation. In: Australasian Conference on Information Security and Privacy, Springer, Pages 653-663.
  * [92] Wang, J., Yang, J., & Wang, B. (2021). Dynamic balance tip selection algorithm for IOTA. In: The IEEE 5th Information Technology, Networking, Electronic and Automation Control Conference, Vol. 5, Pages 360-365.
  * [93] Wang, Q. (2019). Improving the scalability of Blockchain through DAG. In: Proceedings of the 20th International Middleware Conference Doctoral Symposium, Pages 34-35.
  * [94] Wang, Q., Wang, T., Shen, Z., Jia, Z., Zhao, M., & Shao, Z. (2019). Re-Tangle: A reram-based processing-in-memory architecture for transaction-based Blockchain. In: The IEEE/ACM International Conference on Computer-Aided Design, Pages 1-8.
  * [95] Wang, Q., Yu, J., Chen, S., & Xiang, Y. (2020). SoK: Diving into DAG-based Blockchain systems. arXiv preprint arXiv:2012.06128.
  * [96] Wang, T., Wang, Q., Shen, Z., Jia, Z., & Shao, Z. (2021). Understanding characteristics and system implications of DAG-based Blockchain in IoT environments. IEEE Internet of Things Journal, https://ieeexplore.ieee.org/abstract/document/9524824.
  * [97] Wang, W., Hoang, D. T., Hu, P., et al. (2019). A survey on consensus mechanisms and mining strategy management in blockchain networks. IEEE Access, 7, 22328-22370.
  * [98] Watanabe, H., Ishida, T., Ohashi, S., Fujimura, S., Nakadaira, A., Hidaka, K., & Kishigami, J. (2019). Enhancing Blockchain traceability with DAG-based tokens. In: The IEEE International Conference on Blockchain, Pages 220-227.
  * [99] Xiang, F., Huaimin, W., Peichang, S., Xue, O., & Xunhui, Z. (2021). Jointgraph: A DAG-based efficient consensus algorithm for consortium Blockchains. Software: Practice and Experience, 51(10), 1987-1999.
  * [100] Yin, Z., Ruan, A., Wei, M., et al. (2020). Streamnet: A DAG system with streaming graph computing. In: Proceedings of the Future Technologies Conference, Springer, Pages 499-522.
  * [101] Zander, M., Waite, T., & Harz, D. (2019). DAGsim: Simulation of DAG-based distributed ledger protocols. ACM SIGMETRICS Performance Evaluation Review, 46(3), 118-121.
  * [102] Zhang, H., Leng, S., Wu, F., & Chai, H. (2021). A DAG Blockchain enhanced user-autonomy spectrum sharing framework for 6G-enabled IoT. IEEE Internet of Things Journal, 9(11), 8012-8023.
  * [103] Zhang, Z., Zhu, D., & Mi, B. (2020). C-DAG: Community-assisted DAG mechanism with high throughput and eventual consistency. In: International Conference on Wireless Algorithms, Systems, and Applications, Springer, Pages 113-121.
  * [104] Zhao, L., & Yu, J. (2019). Evaluating DAG-based Blockchains for IoT. In: The 18th IEEE International Conference on Trust, Security and Privacy in Computing and Communications/The 13th IEEE International Conference on Big Data Science and Engineering, Pages 507-513.
  * [105] Zhou, T., Li, X., & Zhao, H. (2019). DLattice: A permission-less Blockchain based on DPoS-BA-DAG consensus for data tokenization. IEEE Access, 7, 39273-39287.
  * [106] Zhu, Q., Loke, S. W., Trujillo-Rasua, R., Jiang, F., & Xiang, Y. (2019). Applications of distributed ledger technologies to the internet of things: A survey. ACM computing surveys, 52(6), 1-34.
  * [107] Zou, J., Dong, Z., Shao, A., Zhuang, P., Li, W., & Zomaya, A. Y. (2018). 3D-DAG: A high performance DAG network with eventual consistency and finality. In: The 1st IEEE International Conference on Hot Information-Centric Networking, Pages 262-263.