Directed Acyclic Graph-Type Distributed Ledgers via Young-Age Preferential Attachment

References

• Barabási AL, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509–512.Google Scholar
• Blockchain Luxembourg S.A. (2021a) Average block size—Blockchain. Accessed May 19, 2023, https://blockchain.info/de/charts/avg-block-size.Google Scholar
• Blockchain Luxembourg S.A. (2021b) Median confirmation time—Blockchain. Accessed May 19, 2023, https://www.blockchain.com/charts/median-confirmation-time.Google Scholar
• Blockchain Luxembourg S.A. (2021c) Transaction rate—Blockchain. Accessed May 19, 2023, https://blockchain.info/de/charts/transactions-per-second.Google Scholar
• Bloznelis M, Götze F, Jaworski J (2012) Birth of a strongly connected giant in an inhomogeneous random digraph. J. Appl. Probab. 49(3):601–611.Google Scholar
• Bollobás B, Riordan O (2004) The phase transition and connectedness in uniformly grown random graphs. Leonardi S, ed. Algorithms and Models for the Web-Graph (WAW 2004), Lecture Notes in Computer Science, vol. 3243 (Springer, Berlin), 1–18. https://doi.org/10.1007/978-3-540-30216-2_1.Google Scholar
• Bollobás B, Janson S, Riordan O (2005) The phase transition in the uniformly grown random graph has infinite order. Random Structures Algorithms 26(1–2):1–36.Google Scholar
• Bollobás B, Janson S, Riordan O (2007) The phase transition in inhomogeneous random graphs. Random Structures Algorithms 31(1):3–122.Google Scholar
• Bollobás B, Riordan O, Spencer J, Tusnády G (2001) The degree sequence of a scale-free random graph process. Random Structures Algorithms 18(3):279–290.Google Scholar
• Brightwell G, Luczak M (2012) Vertices of high degree in the preferential attachment tree. Electronic J. Probab. 17(14):1–43.Google Scholar
• Cao J, Olvera-Cravioto M (2020) Connectivity of a general class of inhomogeneous random digraphs. Random Structures Algorithms 56(3):722–774.Google Scholar
• Chung F, Lu L (2006) Concentration inequalities and martingale inequalities: A survey. Internet Math. 3(1):79–127.Google Scholar
• Croman K, Decker C, Eyal I, Gencer AE, Juels A, Kosba A, Miller A, et al. (2016) On scaling decentralized blockchains. Clark J, Meiklejohn S, Ryan P, Wallach D, Brenner M, Rohloff K, eds. Financial Cryptography and Data Security. FC 2016, Lecture Notes in Computer Science, vol. 9604 (Springer, Berlin, Heidelberg), 106–125. https://doi.org/10.1007/978-3-662-53357-4_8.Google Scholar
• Decker C, Wattenhofer R (2013) Information propagation in the Bitcoin network. IEEE 13th Internat. Conf. Peer-to-Peer Comput. (P2P) (IEEE, Piscataway, NJ), 1–10. https://doi.org/10.1109/P2P.2013.6688704.Google Scholar
• Dereich S, Mörters P (2009) Random networks with sublinear preferential attachment: Degree evolutions. Electronic J. Probab. 14(43):1222–1267.Google Scholar
• Dereich S, Mörters P (2013) Random networks with sublinear preferential attachment: The giant component. Ann. Probab. 41(1):329–384.Google Scholar
• Donet JAD, Perez-Sola C, Herrera-Joancomarti J (2014) The Bitcoin P2P network. Böhme R, Brenner M, Moore T, Smith M, eds. Financial Cryptography and Data Security. FC 2014, Lecture Notes in Computer Science, vol. 8438 (Springer, Berlin, Heidelberg), 87–102. https://doi.org/10.1007/978-3-662-44774-1_7.Google Scholar
• Dunford N, Schwartz JT (1988) Linear Operators. Part II (John Wiley & Sons, Inc., New York).Google Scholar
• Durrett R, Kesten H (1990) The Critical Parameter for Connectedness of Some Random Graphs. A Tribute to Paul Erdős (Cambridge University Press, Cambridge, UK), 161–176.Google Scholar
• Fadhil M, Owenson G, Adda M (2016) A Bitcoin model for evaluation of clustering to improve propagation delay in Bitcoin network. 2016 IEEE Internat. Conf. Comput. Sci. Engrg. (CSE) and IEEE Internat. Conf. Embedded Ubiquitous Comput. (EUC) and 15th Internat. Sympos. Distributed Comput. Appl. Bus. Engrg. (DCABES) (IEEE, Piscataway, NJ), 468–475. https://doi.org/10.1109/CSE-EUC-DCABES.2016.226.Google Scholar
• Fadhil M, Owenson G, Adda M (2017) Locality based approach to improve propagation delay on the Bitcoin peer-to-peer network. IFIP/IEEE Sympos. Integrated Network Service Management (IM) (IEEE, Piscataway, NJ), 556–559. https://doi.org/10.23919/INM.2017.7987328.Google Scholar
• Feller W (1950) An Introduction to Probability Theory and Its Applications, vol. I (John Wiley & Sons, Inc., New York).Google Scholar
• Ferraro P, King C, Shorten R (2020) On the stability of unverified transactions in a DAG-based distributed ledger. IEEE Trans. Automatic Control 65(9):3772–3783.Google Scholar
• Gobel J, Krzesinski AE (2017) Increased block size and Bitcoin blockchain dynamics. 27th IEEE Internat. Telecomm. Networks Appl. Conf. (ITNAC) (IEEE, Piscataway, NJ), 1–6. https://doi.org/10.1109/ATNAC.2017.8215367.Google Scholar
• Kalikow S, Weiss B (1988) When are random graphs connected. Israel J. Math. 62(3):257–268.Google Scholar
• Kusmierz B, Gal A (2018) Probability of being left behind and probability of becoming permanent tip in the Tangle v0.2. Working paper, IOTA Foundation.Google Scholar
• Lewenberg Y, Sompolinsky Y, Zohar A (2015) Inclusive block chain protocols. Böhme R, Okamoto T, eds. Financial Cryptography and Data Security. FC 2015, Lecture Notes in Computer Science, vol. 8975 (Springer, Berlin, Heidelberg), 528–547. https://doi.org/10.1007/978-3-662-47854-7_33.Google Scholar
• Lyon MR, Mahmoud HM (2020) Trees grown under young-age preferential attachment. J. Appl. Probab. 57(3):9111–927.Google Scholar
• Müller S, Penzkofer A, Polyanskii N, Theis J, Sanders W, Moog H (2022) Tangle 2.0 leaderless Nakamoto consensus on the heaviest DAG. IEEE Access 10:105807–105842. https://doi.org/10.1109/ACCESS.2022.3211422.Google Scholar
• Nakamoto S (2006) Bitcoin: A peer-to-peer electronic cash system. White paper.Google Scholar
• Pappalardo G, Di Matteo T, Caldarelli G, Aste T (2017) Blockchain inefficiency in the Bitcoin peers network. EPJ Data Sci. 7:30. https://doi.org/10.1140/epjds/s13688-018-0159-3.Google Scholar
• Pemantle R (2007) A survey of random processes with reinforcement. Probab. Surveys 4:1–79.Google Scholar
• Popov S (2016) The Tangle. Working paper, IOTA Foundation.Google Scholar
• Popov S, Moog H, Camargo D, Capossele A, Dimitrov V, Gal A, Greve A, et al. (2020) The Coordicide. Working paper, IOTA Foundation.Google Scholar
• Shepp LA (1989) Connectedness of certain random graphs. Israel J. Math. 67(1):23–33.Google Scholar
• Sompolinsky Y, Wyborski S, Zohar A (2021) Phantom Ghostdag: A scalable generalization of Nakamoto consensus. Proc. 3rd ACM Conf. Adv. Financial Tech. (AFT ’21) (Association for Computing Machinery, New York), 57–70. https://doi.org/10.1145/3479722.3480990.Google Scholar
• Sompolinsky Y, Lewenberg Y, Zohar A (2016) Spectre: A fast and scalable cryptocurrency protocol. IACR Cryptology ePrint Archive 1159. Working paper. https://eprint.iacr.org/2016/1159.Google Scholar
• van der Hofstad R (2017) Random Graphs and Complex Networks, vol. 1, Cambridge Series in Statistical and Probabilistic Mathematics (Cambridge University Press, Cambridge, UK).Google Scholar
• van der Hofstad R (2021) Random Graphs and Complex Networks, vol. 2, Cambridge Series in Statistical and Probabilistic Mathematics (Cambridge University Press, Cambridge, UK).Google Scholar
• Wang Q, Yu J, Chen S, Xiang Y (2022) SoK: Diving into DAG-based blockchain systems. Preprint, submitted October 29, https://doi.org/10.48550/arXiv.2012.06128.Google Scholar
• Yeow K, Gani A, Ahmad RW, Rodrigues JJ, Ko K (2017) Decentralized consensus for edge-centric Internet of things: A review, taxonomy, and research issues. IEEE Access 6:1513–1524. https://doi.org/10.1109/ACCESS.2017.2779263.Google Scholar
• Yin H, Guo D, Wang K, Jiang Z, Lyu Y, Xing J (2018) Hyperconnected network: A decentralized trusted computing and networking paradigm. IEEE Network 32(1):112–117.Google Scholar
• Zyskind G, Nathan O, Pentland A (2015) Decentralizing privacy: Using blockchain to protect personal data. 2015 IEEE Security Privacy Workshops (IEEE, Piscataway, NJ), 180–184.Google Scholar