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

DOI10.1017/APR.2020.48zbMATH Open1496.60007arXiv1902.05050OpenAlexW2911770795MaRDI QIDQ5022281FDOQ5022281

Authors: Christopher King 

Publication date: 18 January 2022

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

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.

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

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

zbMATH Keywords

directed acyclic graphdelay differential equationfluid limitrandom growth model

Mathematics Subject Classification ID

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

Cites Work

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

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)