Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-09T01:34:48.271Z Has data issue: false hasContentIssue false
  • English
  • Français

The fluid limit of a random graph model for a shared ledger

Part of: Graph theory Combinatorial probability

Published online by Cambridge University Press:  17 March 2021

Christopher King
Christopher King*
Affiliation:
Northeastern University
*
*Postal address: Department of Mathematics, Northeastern University, Boston, MA 02115. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

A shared ledger is a record of transactions that can be updated by any member of a group of users. The notion of independent and consistent record-keeping in a shared ledger is important for blockchain and more generally for distributed ledger technologies. In this paper we analyze a stochastic model for the shared ledger known as the tangle, which was devised as the basis for the IOTA cryptocurrency. The model is a random directed acyclic graph, and its growth is described by a non-Markovian stochastic process. We first prove ergodicity of the stochastic process, and then derive a delay differential equation for the fluid model which describes the tangle at high arrival rate. We prove convergence in probability of the tangle process to the fluid model, and also prove global stability of the fluid model. The convergence proof relies on martingale techniques.

Keywords

Directed acyclic graphrandom growth modelfluid limitdelay differential equation

MSC classification

Primary: 60C05: Combinatorial probability
Secondary: 05C80: Random graphs
Type
Original Article
Information
Advances in Applied Probability , Volume 53 , Issue 1 , March 2021 , pp. 81 - 106
Check for updates
Copyright
© The Author(s), 2021. Published by Cambridge University Press on behalf of Applied Probability Trust

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Agarwal, R. P. (2000). Difference equations and inequalities, 2nd edn. Dekker, New York.CrossRefGoogle Scholar
BarabÁsi, A. L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286, 509–512.CrossRefGoogle ScholarPubMed
Baxendale, P. (2011). T. E. Harris’s contributions to recurrent Markov processes and stochastic flows. Ann. Prob. 39, 417–428.CrossRefGoogle Scholar
Billingsley, P. (1995). Probability and Measure, 3rd edn. Wiley, New York.Google Scholar
Breiman, L. (1960). The strong law of large numbers for a class of Markov chains. Ann. Math. Statist. 31, 801–803.CrossRefGoogle Scholar
Callaway, D. S., Hopcroft, J. H., Kleinberg, J. M., Newman, M. E. J. and Strogatz, S. H. (2001). Are randomly grown graphs really random? Phys. Rev. E 64, 041902.CrossRefGoogle ScholarPubMed
Darling, R. W. R. and Norris, J. R. (2008). Differential equation approximations for Markov chains. Prob. Surveys 5, 37–79.CrossRefGoogle Scholar
Driver, R. (1977). Ordinary and Delay Differential Equations. Springer, New York.CrossRefGoogle Scholar
D’Souza, R. M., Borgs, C., Chayes, J. T., Berger, N. and Kleinberg, R. D. (2007). Emergence of tempered preferential attachment from optimization. Proc. Nat. Acad. Sci. USA 104, 6112–6117.CrossRefGoogle Scholar
Ferraro, P., King, C. and Shorten, R. (2018). Distributed ledger technology for smart cities, the sharing economy, and social compliance. IEEE Access 6, 62728–62746.CrossRefGoogle Scholar
Ferraro, P., King, C. and Shorten, R. (2019). IOTA-based directed acyclic graphs without orphans. Preprint. Available at https://arxiv.org/abs/1901.07302.Google Scholar
Frolkova, M. and Mandjes, M. (2019). A Bitcoin-Inspired infinite-server model with a random fluid limit. Stoch. Models 35, 1–32.CrossRefGoogle Scholar
Hairer, M., Mattingly, J. and Scheutzow, M. (2011). Asymptotic coupling and a general form of Harris’ theorem with applications to stochastic delay equations. Prob. Theory Relat. Fields 149, 223–259.CrossRefGoogle Scholar
Halsey, T. C. (2000). Diffusion-Limited aggregation: a model for pattern formation. Physics Today 53, 36–41.CrossRefGoogle Scholar
Koops, D. (2018) Predicting the confirmation time of Bitcoin transactions. Preprint. Available at https://arxiv.org/abs/1809.10596.Google Scholar
Nakamoto, S. (2008). Bitcoin: a peer-to-peer electronic cash system. Available at https://bitcoin.org/bitcoin.pdf.Google Scholar
Novitzky, S., Pender, J., Rand, R. and Wesson, E. (2019). Non-Linear dynamics in queueing theory: determining size of oscillations in queues with delayed information. SIAM J. Appl. Dynam. Systems 18, 279–311.CrossRefGoogle Scholar
Pender, J., Rand, R. and Wesson, E. (2020). A stochastic analysis of queues with customer choice and delayed information. Math. Operat. Res. 45, 1104–1126.CrossRefGoogle Scholar
Pender, J., Rand, R. and Wesson, E. (2017). Queues with choice via delay differential equations. Internat. J. Bifurcation Chaos 27, 1730016.CrossRefGoogle Scholar
Popov, S. (2017). The Tangle (v. 1.4.2). Available at https://www.iota.org/foundation/research-papers.Google Scholar
Reiss, M., Riedle, M. and van Gaans, O. (2006). Delay differential equations driven by Lévy processes: stationarity and Feller properties. Stoch. Process. Appl. 116, 1409–1432.CrossRefGoogle Scholar
Scheutzow, M. (1984). Qualitative behaviour of stochastic delay equations with a bounded memory. Stochastics 12, 41–80.CrossRefGoogle Scholar
Tweedie, R. L. (1976). Criteria for classifying general Markov chains. Adv. Appl. Prob. 8, 737–771.CrossRefGoogle Scholar
Zheng, Z., Xie, S., Dai, H., Chen, X. and Wang, H. (2017). An overview of blockchain technology: architecture, consensus, and future trends. In 2017 IEEE 6th International Congress on Big Data, IEEE, Piscataway, NJ, pp. 557–564.CrossRefGoogle Scholar