Almost sure one-endedness of a random graph model of distributed ledgers
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914007161503744 |
|---|---|
| author | Feng, Jiewei King, Christopher Duffy, Ken R. |
| author_facet | Feng, Jiewei King, Christopher Duffy, Ken R. |
| contents | Blockchain and other decentralized databases, known as distributed ledgers, are designed to store information online where all trusted network members can update the data with transparency. The dynamics of ledger's development can be mathematically represented by a directed acyclic graph (DAG). One essential property of a properly functioning shared ledger is that all network members holding a copy of the ledger agree on a sequence of information added to the ledger, which is referred to as consensus and is known to be related to a structural property of DAG called one-endedness. In this paper, we consider a model of distributed ledger with sequential stochastic arrivals that mimic attachment rules from the IOTA cryptocurrency. We first prove that the number of leaves in the random DAG is bounded by a constant infinitely often through the identification of a suitable martingale, and then prove that a sequence of specific events happens infinitely often. Combining those results we establish that, as time goes to infinity, the IOTA DAG is almost surely one-ended. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_07774 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Almost sure one-endedness of a random graph model of distributed ledgers Feng, Jiewei King, Christopher Duffy, Ken R. Probability Dynamical Systems Blockchain and other decentralized databases, known as distributed ledgers, are designed to store information online where all trusted network members can update the data with transparency. The dynamics of ledger's development can be mathematically represented by a directed acyclic graph (DAG). One essential property of a properly functioning shared ledger is that all network members holding a copy of the ledger agree on a sequence of information added to the ledger, which is referred to as consensus and is known to be related to a structural property of DAG called one-endedness. In this paper, we consider a model of distributed ledger with sequential stochastic arrivals that mimic attachment rules from the IOTA cryptocurrency. We first prove that the number of leaves in the random DAG is bounded by a constant infinitely often through the identification of a suitable martingale, and then prove that a sequence of specific events happens infinitely often. Combining those results we establish that, as time goes to infinity, the IOTA DAG is almost surely one-ended. |
| title | Almost sure one-endedness of a random graph model of distributed ledgers |
| topic | Probability Dynamical Systems |
| url | https://arxiv.org/abs/2309.07774 |