The fluid limit of a random graph model for a shared ledger. (March 2021)

• Record Type: Journal Article
• Authors: King, Christopher
• Is Part Of: Advances in applied probability. Volume 53:Number 1(2021)
• Page Start: 81
• Page End: 106
• Publication Date: 2021-03
• Subjects: Directed acyclic graph, -- random growth model, -- fluid limit, -- delay differential equation; 60C05, -- 05C80; Probabilities -- Periodicals; Stochastic models -- Periodicals; Electronic journals; Periodicals; 519.2
• DOI: 10.1017/apr.2020.48
• Languages: English
• ISSNs: 0001-8678

Abstract

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.