{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T01:58:05Z","timestamp":1771034285917,"version":"3.50.1"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,6,9]],"date-time":"2020-06-09T00:00:00Z","timestamp":1591660800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100014155","name":"Simons Foundation","doi-asserted-by":"publisher","award":["197892"],"award-info":[{"award-number":["197892"]}],"id":[{"id":"10.13039\/100014155","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2020,6,9]]},"abstract":"<jats:p>The blockchain paradigm provides a mechanism for content dissemination and distributed consensus on Peer-to-Peer (P2P) networks. While this paradigm has been widely adopted in industry, it has not been carefully analyzed in terms of its network scaling with respect to the number of peers. Applications for blockchain systems, such as cryptocurrencies and IoT, require this form of network scaling. In this paper, we propose a new stochastic network model for a blockchain system. We identify a structural property called one-endedness, which we show to be desirable in any blockchain system as it is directly related to distributed consensus among the peers. We show that the stochastic stability of the network is sufficient for the one-endedness of a blockchain. We further establish that our model belongs to a class of network models, called monotone separable models. This allows us to establish upper and lower bounds on the stability region. The bounds on stability depend on the connectivity of the P2P network through its conductance and allow us to analyze the scalability of blockchain systems on large P2P networks. We verify our theoretical insights using both synthetic data and real data from the Bitcoin network.<\/jats:p>","DOI":"10.1145\/3392153","type":"journal-article","created":{"date-parts":[[2020,6,9]],"date-time":"2020-06-09T22:10:12Z","timestamp":1591740612000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":24,"title":["Stability and Scalability of Blockchain Systems"],"prefix":"10.1145","volume":"4","author":[{"given":"Aditya","family":"Gopalan","sequence":"first","affiliation":[{"name":"The University of Texas at Austin, Austin, TX, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abishek","family":"Sankararaman","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anwar","family":"Walid","sequence":"additional","affiliation":[{"name":"Nokia Bell Labs, Murray Hill, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sriram","family":"Vishwanath","sequence":"additional","affiliation":[{"name":"The University of Texas at Austin, Austin, TX, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,12]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"https:\/\/en.Bitcoin.it\/wiki\/Confirmation. Online","year":"2019"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v12-463"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.2307\/3215303"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/719\/14471"},{"key":"e_1_2_1_5_1","first-page":"24","article-title":"Doeblin trees","author":"Baccelli Fran\u00e7ois","year":"2019","journal-title":"Electronic Journal of Probability"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2013.6566973"},{"key":"e_1_2_1_7_1","volume-title":"Renewal population dynamics and their eternal family trees. arXiv preprint arXiv:1803.08081","author":"Baccelli Fran\u00e7ois","year":"2018"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3319535.3363213"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-9675-6_15"},{"key":"e_1_2_1_10_1","volume-title":"Bitcoin database dump. https:\/\/gz.blockchair.com\/Bitcoin\/blocks\/. Online","year":"2020"},{"issue":"1","key":"e_1_2_1_11_1","first-page":"22","article-title":"Redesigning the bitcoin network for anonymity","volume":"1","author":"Venkatakrishnan Shaileshh Bojja","year":"2017","journal-title":"Proceedings of the ACM on Measurement and Analysis of Computing Systems"},{"key":"e_1_2_1_12_1","first-page":"22","volume-title":"Ethereum white paper. GitHub repository","author":"Vitalik Buterin","year":"2013"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873736"},{"key":"e_1_2_1_14_1","first-page":"1","article-title":"Information propagation in the bitcoin network","volume":"2013","author":"Decker Christian","year":"2013","journal-title":"IEEE P2P"},{"key":"e_1_2_1_15_1","first-page":"69","volume-title":"Proceedings of the 5th international conference on Information processing in sensor networks","author":"Dimakis Alexandros G","year":"2006"},{"key":"e_1_2_1_16_1","first-page":"45","volume-title":"Emin G\u00fcn Sirer, and Robbert Van Renesse. Bitcoin-ng: A scalable blockchain protocol. In 13th {USENIX} symposium on networked systems design and implementation ({NSDI} 16)","author":"Eyal Ittay","year":"2016"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212998"},{"key":"e_1_2_1_18_1","first-page":"251","volume-title":"ACM SIGCOMM computer communication review","author":"Faloutsos Michalis","year":"1999"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3224424"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.15807\/jorsj.47.275"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1007\/978-3-642-15369-3_42","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Fountoulakis Nikolaos","year":"2010"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095246"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1080\/15326349.2018.1559739"},{"key":"e_1_2_1_24_1","volume-title":"Rumor spreading on graphs","author":"Ganesh Ayalvadi","year":"2015"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46803-6_10"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-58387-6_24"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978341"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2016.07.001"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01362670"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2009.5062058"},{"key":"e_1_2_1_31_1","volume-title":"Random graphs","author":"Janson Svante","year":"2011"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2012.6195689"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-68520-5_5"},{"key":"e_1_2_1_34_1","volume-title":"Reversibility and stochastic networks","author":"Kelly Frank P","year":"2011"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.1013"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47854-7_33"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-04648-4_3"},{"key":"e_1_2_1_38_1","volume-title":"Markov processes in blockchain systems. arXiv preprint arXiv:1904.03598","author":"Li Quan-Lin","year":"2019"},{"key":"e_1_2_1_39_1","volume-title":"Probability on trees and networks","author":"Lyons Russell","year":"2017"},{"key":"e_1_2_1_40_1","first-page":"2","volume-title":"ACM SIGMETRICS Performance Evaluation Review","author":"Massouli\u00e9 Laurent","year":"2005"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238178"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2019.2928716"},{"key":"e_1_2_1_43_1","volume-title":"Bitcoin: A peer-to-peer electronic cash system","author":"Nakamoto Satoshi","year":"2008"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198805090.001.0001","volume-title":"Networks","author":"Newman Mark","year":"2018"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0188-x"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2018.8485982"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-56614-6_22"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087809"},{"key":"e_1_2_1_49_1","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001","volume-title":"Random geometric graphs","author":"Mathew Penrose","year":"2003"},{"key":"e_1_2_1_50_1","volume-title":"Iota whitepaper. Technical White Paper, year=","author":"Popov Sergei","year":"2017"},{"key":"e_1_2_1_51_1","first-page":"367","volume-title":"ACM SIGCOMM computer communication review","author":"Qiu Dongyu","year":"2004"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011494323443"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308897.3308952"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/tit.2007.909171"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1561\/1300000014"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47854-7_32"},{"key":"e_1_2_1_57_1","volume-title":"Fundamentals of wireless communication","author":"Tse David","year":"2005"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2013.2256675"},{"key":"e_1_2_1_59_1","volume-title":"Random graphs and complex networks. Available on http:\/\/www. win. tue. nl\/rhofstad\/NotesRGCN. pdf, 11","author":"Der Hofstad Remco Van","year":"2009"},{"key":"e_1_2_1_60_1","volume-title":"Prism: Scaling bitcoin by 10,000 x. arXiv preprint arXiv:1909.11261","author":"Yang Lei","year":"2019"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2004.1354647"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2012.2195712"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3392153","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3392153","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:38:49Z","timestamp":1750199929000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3392153"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,9]]},"references-count":62,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,6,9]]}},"alternative-id":["10.1145\/3392153"],"URL":"https:\/\/doi.org\/10.1145\/3392153","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,9]]},"assertion":[{"value":"2020-06-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}