Figure 1.
Comparison of analysis and simulation for basic queueing model
-
Previous Article
Upper bounds for Z$ _1 $-eigenvalues of generalized Hilbert tensors
- JIMO Home
- This Issue
-
Next Article
Forecast horizon of dynamic lot size model for perishable inventory with minimum order quantities
doi: 10.3934/jimo.2018193
Priority queueing analysis of transaction-confirmation time for Bitcoin
Graduate School of Information Science, Nara Institute of Science and Technology, Takayama 8916-5, Ikoma, Nara 6300192, Japan |
In Bitcoin system, a transaction is given a priority value according to its attributes such as the remittance amount and fee, and transactions with high priorities are likely to be confirmed faster than those with low priorities. In this paper, we analyze the transaction-confirmation time for Bitcoin system. We model the transaction-confirmation process as a queueing system with batch service, M/$ \mbox{G}^B $/1. We consider the joint distribution of numbers of transactions in system and the elapsed service time, deriving the mean transaction-confirmation time. Using the result, we derive the recursive formulae of mean transaction-confirmation times of an M/$ \mbox{G}^B $/1 queue with priority service discipline. In numerical examples, we show the effect of the maximum block size on the mean transaction-confirmation time, investigating the accuracy region of our queueing model. We also discuss how the increase in micropayments, which are likely to be given low priorities, affects the transaction-confirmation time.
Mathematics Subject Classification:
Primary: 68M20, 90B22; Secondary: 60K25.
Citation:
Yoshiaki Kawase, Shoji Kasahara.
Priority queueing analysis of transaction-confirmation time for Bitcoin. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2018193
![]()
References:
| [1] |
A. M. Antonopoulos, Mastering Bitcoin, O'Reilly, 2014.Google Scholar |
| [2] |
M. L. Chaudhry and J. G. C. Templeton,
The queuing system M/GB/1 and its ramifications, European Journal of Operational Research, 6 (1981), 56-60.
doi: 10.1016/0377-2217(81)90328-3. |
| [3] |
M. L. Chaudhry and J. G. C. Templeton, A First Course in Bulk Queues, John Wiley & Sons, 1983. |
| [4] |
http://www.meti.go.jp/committee/kenkyukai/sansei/fintech\_kadai/pdf/003\_02\_00.pdfGoogle Scholar |
| [5] |
http://www.coindesk.com/1mb-block-size-today-bitcoin/Google Scholar |
| [6] | |
| [7] |
http://www.coindesk.com/segregated-witness-bitcoin-block-size-debate/Google Scholar |
| [8] |
S. Kasahara and J. Kawahara, Effect of Bitcoin fee on transaction-confirmation process, arXiv: 1604.00103[cs.CR].Google Scholar |
| [9] |
Y. Kawase and S. Kasahara, Transaction-Confirmation Time for Bitcoin: A Queueing Analytical Approach to Blockchain Mechanism, The 12th International Conference on Queueing Theory and Network Applications (QTNA2017), Qinhuangdao, China, August 21-23, 2017.Google Scholar |
| [10] |
M. Möser and R. Böhome,
Trends, tips, tolls: A longitudinal study of bitcoin transaction fees, Financial Cryptography and Data Security, Lecture Notes in Computer Science, Springer, 8976 (2015), 19-33.
doi: 10.1007/978-3-662-48051-9_2. |
| [11] |
S. Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System, 2008. Available from: https://bitcoin.org/bitcoin.pdf.Google Scholar |
| [12] |
J. Poon and T. Dryja, The bitcoin lightning network: Scalable off-chain instant payments, https://lightning.network/lightning-network-paper.pdf, 2016.Google Scholar |
| [13] |
H. Takagi, Queueing Analysis: A Foundation of Performance Evaluation, Vol. 2. Finite systems. North-Holland Publishing Co., Amsterdam, 1993. |
| [14] |
https://github.com/bitcoin/bips/blob/master/bip-0141.mediawikiGoogle Scholar |
| [15] |
F. Tschorsch and B. Scheuermann, Bitcoin and beyond: A technical survey on decentralized digital currencies, Tutorials, 18 (2016), 2084-2123. Google Scholar |
| [16] | |
| [17] |
https://www.coindesk.com/segwits-slow-rollout-bitcoins-capacity-hasnt-seen/Google Scholar |
show all references
References:
| [1] |
A. M. Antonopoulos, Mastering Bitcoin, O'Reilly, 2014.Google Scholar |
| [2] |
M. L. Chaudhry and J. G. C. Templeton,
The queuing system M/GB/1 and its ramifications, European Journal of Operational Research, 6 (1981), 56-60.
doi: 10.1016/0377-2217(81)90328-3. |
| [3] |
M. L. Chaudhry and J. G. C. Templeton, A First Course in Bulk Queues, John Wiley & Sons, 1983. |
| [4] |
http://www.meti.go.jp/committee/kenkyukai/sansei/fintech\_kadai/pdf/003\_02\_00.pdfGoogle Scholar |
| [5] |
http://www.coindesk.com/1mb-block-size-today-bitcoin/Google Scholar |
| [6] | |
| [7] |
http://www.coindesk.com/segregated-witness-bitcoin-block-size-debate/Google Scholar |
| [8] |
S. Kasahara and J. Kawahara, Effect of Bitcoin fee on transaction-confirmation process, arXiv: 1604.00103[cs.CR].Google Scholar |
| [9] |
Y. Kawase and S. Kasahara, Transaction-Confirmation Time for Bitcoin: A Queueing Analytical Approach to Blockchain Mechanism, The 12th International Conference on Queueing Theory and Network Applications (QTNA2017), Qinhuangdao, China, August 21-23, 2017.Google Scholar |
| [10] |
M. Möser and R. Böhome,
Trends, tips, tolls: A longitudinal study of bitcoin transaction fees, Financial Cryptography and Data Security, Lecture Notes in Computer Science, Springer, 8976 (2015), 19-33.
doi: 10.1007/978-3-662-48051-9_2. |
| [11] |
S. Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System, 2008. Available from: https://bitcoin.org/bitcoin.pdf.Google Scholar |
| [12] |
J. Poon and T. Dryja, The bitcoin lightning network: Scalable off-chain instant payments, https://lightning.network/lightning-network-paper.pdf, 2016.Google Scholar |
| [13] |
H. Takagi, Queueing Analysis: A Foundation of Performance Evaluation, Vol. 2. Finite systems. North-Holland Publishing Co., Amsterdam, 1993. |
| [14] |
https://github.com/bitcoin/bips/blob/master/bip-0141.mediawikiGoogle Scholar |
| [15] |
F. Tschorsch and B. Scheuermann, Bitcoin and beyond: A technical survey on decentralized digital currencies, Tutorials, 18 (2016), 2084-2123. Google Scholar |
| [16] | |
| [17] |
https://www.coindesk.com/segwits-slow-rollout-bitcoins-capacity-hasnt-seen/Google Scholar |
Figure 2.
Comparison of analysis and simulation for priority-queueing model
Figure 3.
Transaction-confirmation time vs. block size, 1st period (October 2013 to September 2014). $ \lambda = 0.7336929 $ , $ \mu = 0.0019748858 $ , and the coefficient of variation of transaction inter-arrival time: $ 3.72401599 $
Figure 4.
Transaction-confirmation time vs. block size, 2nd period (October 2014 to September 2015). $ \lambda = 1.2081311 $ , $ \mu = 0.0017009449 $ , and the coefficient of variation of transaction inter-arrival time: $ 15.3250509 $
Figure 5.
The mean transaction-arrival rate
Figure 6.
Transaction-confirmation time vs. block size, October 2013 to September 2014. $ \lambda_H = 0.7203544 $ , $ \mu = 0.0019748858 $
Figure 7.
Transaction-confirmation time vs. block size, October 2014 to September 2015. $ \lambda_H = 1.1494675 $ , $ \mu = 0.0017009449 $
Figure 8.
Transaction-confirmation time vs. block size, October 2013 to September 2014. $ \lambda_L = 0.0133385 $ , $ \mu = 0.0019748858 $
Figure 9.
Transaction-confirmation time vs. block size, October 2014 to September 2015. $ \lambda_L = 0.0586636 $ , $ \mu = 0.0017009449 $
Figure 10.
The effects of the block size on the transaction-confirmation time
Figure 11.
The effects of the micropayments on the transaction-confirmation time
Figure 12.
The effect of the block size on the transaction-confirmation time of high-priority transactions
Figure 13.
The effects of the block size on the transaction-confirmation time of low-priority transactions
Table 1.
Mean transaction confirmation time for each priority
| Period | Classless [s] | Low priority [s] | High priority [s] | |
| 1st | (2013/10/1-2014/9/30) | 1060.67797 | 1947.47115 | 1044.25043 |
| 2nd | (2014/10/1-2015/9/30) | 1171.98866 | 4887.56496 | 1070.32818 |
| overall | (2013/10/1-2015/9/30) | 1124.13286 | 3888.06977 | 1059.06133 |
| Period | Classless [s] | Low priority [s] | High priority [s] | |
| 1st | (2013/10/1-2014/9/30) | 1060.67797 | 1947.47115 | 1044.25043 |
| 2nd | (2014/10/1-2015/9/30) | 1171.98866 | 4887.56496 | 1070.32818 |
| overall | (2013/10/1-2015/9/30) | 1124.13286 | 3888.06977 | 1059.06133 |
Table 2.
Comparison of analysis and measurement
| Transaction Type | Arrival Rate | Measurement [s] | Analysis[s] |
| Classless | 0.9709120529 | 1124.13286 | 1112.025339 |
| High Priority | 0.9349109906 | 1059.06133 | 1108.773595 |
| Low Priority | 0.0360010622 | 3888.06977 | 1196.469817 |
| Transaction Type | Arrival Rate | Measurement [s] | Analysis[s] |
| Classless | 0.9709120529 | 1124.13286 | 1112.025339 |
| High Priority | 0.9349109906 | 1059.06133 | 1108.773595 |
| Low Priority | 0.0360010622 | 3888.06977 | 1196.469817 |
Table 3.
Coefficients of variation for transaction interarrival time
| Period | 1st 2013/10-2014/09 |
2nd 2014/10-2015/09 |
Overall 2013/10-2015/09 |
| Classless | 3.72401 | 15.32505 | 10.17893 |
| Period | 1st 2013/10-2014/09 |
2nd 2014/10-2015/09 |
Overall 2013/10-2015/09 |
| Classless | 3.72401 | 15.32505 | 10.17893 |
Table 4.
Coefficients of variation for transaction interarrival time, two-priority classes
| Period | 1st 2013/10-2014/09 |
2nd 2014/10-2015/09 |
Overall 2013/10-2015/09 |
| Low Priority | 1.66569 | 3.90654 | 3.01387 |
| High Priority | 3.70045 | 14.94895 | 9.99103 |
| Period | 1st 2013/10-2014/09 |
2nd 2014/10-2015/09 |
Overall 2013/10-2015/09 |
| Low Priority | 1.66569 | 3.90654 | 3.01387 |
| High Priority | 3.70045 | 14.94895 | 9.99103 |
| [1] |
Shoji Kasahara, Jun Kawahara. Effect of Bitcoin fee on transaction-confirmation process. Journal of Industrial & Management Optimization, 2019, 15 (1) : 365-386. doi: 10.3934/jimo.2018047 |
| [2] |
Yung Chung Wang, Jenn Shing Wang, Fu Hsiang Tsai. Analysis of discrete-time space priority queue with fuzzy threshold. Journal of Industrial & Management Optimization, 2009, 5 (3) : 467-479. doi: 10.3934/jimo.2009.5.467 |
| [3] |
Hideaki Takagi. Unified and refined analysis of the response time and waiting time in the M/M/m FCFS preemptive-resume priority queue. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1945-1973. doi: 10.3934/jimo.2017026 |
| [4] |
Arnaud Devos, Joris Walraevens, Tuan Phung-Duc, Herwig Bruneel. Analysis of the queue lengths in a priority retrial queue with constant retrial policy. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-30. doi: 10.3934/jimo.2019082 |
| [5] |
Shaojun Lan, Yinghui Tang. Performance analysis of a discrete-time $ Geo/G/1$ retrial queue with non-preemptive priority, working vacations and vacation interruption. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1421-1446. doi: 10.3934/jimo.2018102 |
| [6] |
Dhanya Shajin, A. N. Dudin, Olga Dudina, A. Krishnamoorthy. A two-priority single server retrial queue with additional items. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-22. doi: 10.3934/jimo.2019085 |
| [7] |
Biao Xu, Xiuli Xu, Zhong Yao. Equilibrium and optimal balking strategies for low-priority customers in the M/G/1 queue with two classes of customers and preemptive priority. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1599-1615. doi: 10.3934/jimo.2018113 |
| [8] |
Zhanyou Ma, Wenbo Wang, Linmin Hu. Performance evaluation and analysis of a discrete queue system with multiple working vacations and non-preemptive priority. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-14. doi: 10.3934/jimo.2018196 |
| [9] |
Sofian De Clercq, Koen De Turck, Bart Steyaert, Herwig Bruneel. Frame-bound priority scheduling in discrete-time queueing systems. Journal of Industrial & Management Optimization, 2011, 7 (3) : 767-788. doi: 10.3934/jimo.2011.7.767 |
| [10] |
Bara Kim, Jeongsim Kim. Explicit solution for the stationary distribution of a discrete-time finite buffer queue. Journal of Industrial & Management Optimization, 2016, 12 (3) : 1121-1133. doi: 10.3934/jimo.2016.12.1121 |
| [11] |
Zsolt Saffer, Wuyi Yue. A dual tandem queueing system with GI service time at the first queue. Journal of Industrial & Management Optimization, 2014, 10 (1) : 167-192. doi: 10.3934/jimo.2014.10.167 |
| [12] |
Tuan Phung-Duc, Ken'ichi Kawanishi. Multiserver retrial queue with setup time and its application to data centers. Journal of Industrial & Management Optimization, 2019, 15 (1) : 15-35. doi: 10.3934/jimo.2018030 |
| [13] |
Yongjiang Guo, Yuantao Song. The (functional) law of the iterated logarithm of the sojourn time for a multiclass queue. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-28. doi: 10.3934/jimo.2018192 |
| [14] |
Yutaka Sakuma, Atsushi Inoie, Ken’ichi Kawanishi, Masakiyo Miyazawa. Tail asymptotics for waiting time distribution of an M/M/s queue with general impatient time. Journal of Industrial & Management Optimization, 2011, 7 (3) : 593-606. doi: 10.3934/jimo.2011.7.593 |
| [15] |
Archana Prashanth Joshi, Meng Han, Yan Wang. A survey on security and privacy issues of blockchain technology. Mathematical Foundations of Computing, 2018, 1 (2) : 121-147. doi: 10.3934/mfc.2018007 |
| [16] |
Thomas Demoor, Joris Walraevens, Dieter Fiems, Stijn De Vuyst, Herwig Bruneel. Influence of real-time queue capacity on system contents in DiffServ's expedited forwarding per-hop-behavior. Journal of Industrial & Management Optimization, 2010, 6 (3) : 587-602. doi: 10.3934/jimo.2010.6.587 |
| [17] |
Michiel De Muynck, Herwig Bruneel, Sabine Wittevrongel. Analysis of a discrete-time queue with general service demands and phase-type service capacities. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1901-1926. doi: 10.3934/jimo.2017024 |
| [18] |
Bart Feyaerts, Stijn De Vuyst, Herwig Bruneel, Sabine Wittevrongel. The impact of the $NT$-policy on the behaviour of a discrete-time queue with general service times. Journal of Industrial & Management Optimization, 2014, 10 (1) : 131-149. doi: 10.3934/jimo.2014.10.131 |
| [19] |
Gopinath Panda, Veena Goswami. Effect of information on the strategic behavior of customers in a discrete-time bulk service queue. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-20. doi: 10.3934/jimo.2019007 |
| [20] |
Shan Gao, Jinting Wang. On a discrete-time GI$^X$/Geo/1/N-G queue with randomized working vacations and at most $J$ vacations. Journal of Industrial & Management Optimization, 2015, 11 (3) : 779-806. doi: 10.3934/jimo.2015.11.779 |
2018 Impact Factor: 1.025
Tools
Metrics
Other articles
by authors
[Back to Top]