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

DOI10.1017/APR.2020.48MaRDI QIDQ5022281zbMATH OpenOpenAlexFDO

Authors Christopher King

Publication date 18 January 2022

Published in Advances in Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1902.05050

zbMATH Keywords

directed acyclic graphdelay differential equationfluid limitrandom growth model

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

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 the growth of a model for the tangle, which is the shared ledger protocol used 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 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.

Recommendations

• A bitcoin-inspired infinite-server model with a random fluid limit
• Algorand: a secure and efficient distributed ledger
• Analysis of the average confirmation time of transactions in a blockchain system
• A Stochastic Epidemiological Model and a Deterministic Limit for BitTorrent-Like Peer-to-Peer File-Sharing Networks
• Efficient state management in distributed ledgers

Cites work

• scientific article; zbMATH DE number 765034 (Why is no real title available?)
• scientific article; zbMATH DE number 1418991 (Why is no real title available?)
• A Stochastic Analysis of Queues with Customer Choice and Delayed Information
• A bitcoin-inspired infinite-server model with a random fluid limit
• Asymptotic coupling and a general form of Harris' theorem with applications to stochastic delay equations
• Criteria for classifying general Markov chains
• Delay differential equations driven by Lévy processes: stationarity and Feller properties
• Differential equation approximations for Markov chains
• Emergence of Scaling in Random Networks
• Nonlinear dynamics in queueing theory: determining the size of oscillations in queues with delay
• Ordinary and delay differential equations
• Qualitative behaviour of stochastic delay equations with a bounded memory
• Queues with choice via delay differential equations
• T. E. Harris's contributions to recurrent Markov processes and stochastic flows
• The Strong Law of Large Numbers for a Class of Markov Chains

This page was built for publication: The fluid limit of a random graph model for a shared ledger

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5022281)