Markov processes in blockchain systems

Autor: Hai-Bo Yu, Jing-Yu Ma, Yan-Xia Chang, Quan-Lin Li, Fan-Qi Ma
Jazyk: angličtina
Rok vydání: 2019
Předmět:
FOS: Computer and information sciences
Computer Science - Cryptography and Security
Theoretical computer science
Blockchain
E.2
Computer science
Matrix-geometric solution
E.3
Markovian arrival process (MAP)
Markov process
02 engineering and technology
lcsh:QA75.5-76.95
H.3.5
symbols.namesake
H.2.4
Block-structured Markov process
020204 information systems
0202 electrical engineering
electronic engineering
information engineering
90B22
60J28
94A15
Queue
Block (data storage)
Structure (mathematical logic)
Queueing theory
Series (mathematics)
lcsh:T58.5-58.64
lcsh:Information technology
D.4.8
D.4.6
Computer Science Applications
Human-Computer Interaction
Modeling and Simulation
Phase type (PH) distribution
symbols
020201 artificial intelligence & image processing
lcsh:Electronic computers. Computer science
Cryptography and Security (cs.CR)
Database transaction
Bitcoin
Information Systems
Zdroj: Computational Social Networks, Vol 6, Iss 1, Pp 1-28 (2019)
ISSN: 2197-4314
DOI: 10.1186/s40649-019-0066-1
Popis: In this paper, we develop a more general framework of block-structured Markov processes in the queueing study of blockchain systems, which can provide analysis both for the stationary performance measures and for the sojourn times of any transaction and block. Note that an original aim of this paper is to generalize the two-stage batch-service queueing model studied in Li et al. \cite{Li:2018} both ``from exponential to phase-type" service times and ``from Poisson to MAP" transaction arrivals. In general, the MAP transaction arrivals and the two stages of PH service times make our blockchain queue more suitable to various practical conditions of blockchain systems with crucial random factors, for example, the mining processes, the block-generations, the blockchain-building and so forth. For such a more general blockchain queueing model, we focus on two basic research aspects: (1) By using the matrix-geometric solution, we first obtain a sufficient stable condition of the blockchain system. Then we provide simple expressions for the average number of transactions in the queueing waiting room, and the average number of transactions in the block. (2) However, comparing with Li et al. \cite{Li:2018}, analysis of the transaction-confirmation time becomes very difficult and challenging due to the complicated blockchain structure. To overcome the difficulties, we develop a computational technique of the first passage times by means of both the PH distributions of infinite sizes and the $RG$-factorizations. Finally, we hope that the methodology and results given in this paper will open a new avenue to queueing analysis of more general blockchain systems in practice, and can motivate a series of promising future research on development of lockchain technologies.
38 pages, 4 figures
Databáze: OpenAIRE
Externí odkaz: