[{"date_updated":"2025-12-02T14:02:38Z","language":[{"iso":"eng"}],"oa_version":"None","corr_author":"1","publisher":"Springer Nature","quality_controlled":"1","related_material":{"record":[{"status":"public","id":"14820","relation":"later_version"}]},"month":"05","citation":{"chicago":"Schmid, Stefan, Jakub Svoboda, and Michelle X Yeo. “Weighted Acket Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.” In <i>30th International Colloquium on Structural Information and Communication Complexity</i>, 13892:576–94. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/978-3-031-32733-9_26\">https://doi.org/10.1007/978-3-031-32733-9_26</a>.","ista":"Schmid S, Svoboda J, Yeo MX. 2023. Weighted acket selection for rechargeable links in cryptocurrency networks: Complexity and approximation. 30th International Colloquium on Structural Information and Communication Complexity. SIROCCO: International Colloquium on Structural Information and Communication Complexity, LNCS, vol. 13892, 576–594.","ama":"Schmid S, Svoboda J, Yeo MX. Weighted acket selection for rechargeable links in cryptocurrency networks: Complexity and approximation. In: <i>30th International Colloquium on Structural Information and Communication Complexity</i>. Vol 13892. Springer Nature; 2023:576-594. doi:<a href=\"https://doi.org/10.1007/978-3-031-32733-9_26\">10.1007/978-3-031-32733-9_26</a>","short":"S. Schmid, J. Svoboda, M.X. Yeo, in:, 30th International Colloquium on Structural Information and Communication Complexity, Springer Nature, 2023, pp. 576–594.","apa":"Schmid, S., Svoboda, J., &#38; Yeo, M. X. (2023). Weighted acket selection for rechargeable links in cryptocurrency networks: Complexity and approximation. In <i>30th International Colloquium on Structural Information and Communication Complexity</i> (Vol. 13892, pp. 576–594). Alcalá de Henares, Spain: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-32733-9_26\">https://doi.org/10.1007/978-3-031-32733-9_26</a>","ieee":"S. Schmid, J. Svoboda, and M. X. Yeo, “Weighted acket selection for rechargeable links in cryptocurrency networks: Complexity and approximation,” in <i>30th International Colloquium on Structural Information and Communication Complexity</i>, Alcalá de Henares, Spain, 2023, vol. 13892, pp. 576–594.","mla":"Schmid, Stefan, et al. “Weighted Acket Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.” <i>30th International Colloquium on Structural Information and Communication Complexity</i>, vol. 13892, Springer Nature, 2023, pp. 576–94, doi:<a href=\"https://doi.org/10.1007/978-3-031-32733-9_26\">10.1007/978-3-031-32733-9_26</a>."},"type":"conference","page":"576-594","conference":{"end_date":"2023-06-09","start_date":"2023-06-06","name":"SIROCCO: International Colloquium on Structural Information and Communication Complexity","location":"Alcalá de Henares, Spain"},"abstract":[{"lang":"eng","text":"We consider a natural problem dealing with weighted packet selection across a rechargeable link, which e.g., finds applications in cryptocurrency networks. The capacity of a link (u, v) is determined by how much nodes u and v allocate for this link. Specifically, the input is a finite ordered sequence of packets that arrive in both directions along a link. Given (u, v) and a packet of weight x going from u to v, node u can either accept or reject the packet. If u accepts the packet, the capacity on link (u, v) decreases by x. Correspondingly, v’s capacity on (u, v) increases by x. If a node rejects the packet, this will entail a cost affinely linear in the weight of the packet. A link is “rechargeable” in the sense that the total capacity of the link has to remain constant, but the allocation of capacity at the ends of the link can depend arbitrarily on the nodes’ decisions. The goal is to minimise the sum of the capacity injected into the link and the cost of rejecting packets. We show that the problem is NP-hard, but can be approximated efficiently with a ratio of (1 + E) . (1 + square3) for some arbitrary E>0."}],"_id":"19985","OA_type":"closed access","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"KrCh"},{"_id":"KrPi"}],"publication_status":"published","external_id":{"isi":["001292782600026"]},"alternative_title":["LNCS"],"status":"public","isi":1,"day":"25","publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"eisbn":["9783031327339"],"isbn":["9783031327322"]},"volume":13892,"scopus_import":"1","publication":"30th International Colloquium on Structural Information and Communication Complexity","year":"2023","intvolume":"     13892","acknowledgement":"We thank Mahsa Bastankhah and Mohammad Ali Maddah-Ali for fruitful discussions about different variants of the problem. This work is supported by the European Research Council (ERC) Consolidator Project 864228 (AdjustNet), 2020-2025, the ERC CoG 863818 (ForM-SMArt), and the German Research Foundation (DFG) grant 470029389 (FlexNets), 2021–2024.","doi":"10.1007/978-3-031-32733-9_26","title":"Weighted acket selection for rechargeable links in cryptocurrency networks: Complexity and approximation","author":[{"first_name":"Stefan","full_name":"Schmid, Stefan","last_name":"Schmid"},{"orcid":"0000-0002-1419-3267","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","last_name":"Svoboda","full_name":"Svoboda, Jakub","first_name":"Jakub"},{"full_name":"Yeo, Michelle X","first_name":"Michelle X","orcid":"0009-0001-3676-4809","last_name":"Yeo","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"}],"date_created":"2025-07-10T13:15:43Z","ec_funded":1,"project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"date_published":"2023-05-25T00:00:00Z"},{"abstract":[{"lang":"eng","text":"Sharding distributed ledgers is a promising on-chain solution for scaling blockchains but lacks formal grounds, nurturing skepticism on whether such complex systems can scale blockchains securely. We fill this gap by introducing the first formal framework as well as a roadmap to robust sharding. In particular, we first define the properties sharded distributed ledgers should fulfill. We build upon and extend the Bitcoin backbone protocol by defining consistency and scalability. Consistency encompasses the need for atomic execution of cross-shard transactions to preserve safety, whereas scalability encapsulates the speedup a sharded system can gain in comparison to a non-sharded system.\r\nUsing our model, we explore the limitations of sharding. We show that a sharded ledger with n participants cannot scale under a fully adaptive adversary, but it can scale up to m shards where n=c'm log m, under an epoch-adaptive adversary; the constant c' encompasses the trade-off between security and scalability. This is possible only if the sharded ledgers create succinct proofs of the valid state updates at every epoch. We leverage our results to identify the sufficient components for robust sharding, which we incorporate in a protocol abstraction termed Divide & Scale. To demonstrate the power of our framework, we analyze the most prominent sharded blockchains (Elastico, Monoxide, OmniLedger, RapidChain) and pinpoint where they fail to meet the desired properties."}],"_id":"14744","type":"conference","month":"06","citation":{"mla":"Avarikioti, Zeta, et al. “Divide &#38; Scale: Formalization and Roadmap to Robust Sharding.” <i>30th International Colloquium on Structural Information and Communication Complexity</i>, vol. 13892, Springer Nature, 2023, pp. 199–245, doi:<a href=\"https://doi.org/10.1007/978-3-031-32733-9_10\">10.1007/978-3-031-32733-9_10</a>.","ieee":"Z. Avarikioti, A. Desjardins, E. Kokoris Kogias, and R. Wattenhofer, “Divide &#38; Scale: Formalization and roadmap to robust sharding,” in <i>30th International Colloquium on Structural Information and Communication Complexity</i>, Alcalá de Henares, Spain, 2023, vol. 13892, pp. 199–245.","ama":"Avarikioti Z, Desjardins A, Kokoris Kogias E, Wattenhofer R. Divide &#38; Scale: Formalization and roadmap to robust sharding. In: <i>30th International Colloquium on Structural Information and Communication Complexity</i>. Vol 13892. Springer Nature; 2023:199-245. doi:<a href=\"https://doi.org/10.1007/978-3-031-32733-9_10\">10.1007/978-3-031-32733-9_10</a>","chicago":"Avarikioti, Zeta, Antoine Desjardins, Eleftherios Kokoris Kogias, and Roger Wattenhofer. “Divide &#38; Scale: Formalization and Roadmap to Robust Sharding.” In <i>30th International Colloquium on Structural Information and Communication Complexity</i>, 13892:199–245. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/978-3-031-32733-9_10\">https://doi.org/10.1007/978-3-031-32733-9_10</a>.","ista":"Avarikioti Z, Desjardins A, Kokoris Kogias E, Wattenhofer R. 2023. Divide &#38; Scale: Formalization and roadmap to robust sharding. 30th International Colloquium on Structural Information and Communication Complexity. SIROCCO: Structural Information and Communication Complexity, LNCS, vol. 13892, 199–245.","short":"Z. Avarikioti, A. Desjardins, E. Kokoris Kogias, R. Wattenhofer, in:, 30th International Colloquium on Structural Information and Communication Complexity, Springer Nature, 2023, pp. 199–245.","apa":"Avarikioti, Z., Desjardins, A., Kokoris Kogias, E., &#38; Wattenhofer, R. (2023). Divide &#38; Scale: Formalization and roadmap to robust sharding. In <i>30th International Colloquium on Structural Information and Communication Complexity</i> (Vol. 13892, pp. 199–245). Alcalá de Henares, Spain: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-32733-9_10\">https://doi.org/10.1007/978-3-031-32733-9_10</a>"},"page":"199-245","conference":{"location":"Alcalá de Henares, Spain","end_date":"2023-06-09","name":"SIROCCO: Structural Information and Communication Complexity","start_date":"2023-06-06"},"oa_version":"None","quality_controlled":"1","publisher":"Springer Nature","date_updated":"2025-09-09T14:10:46Z","language":[{"iso":"eng"}],"date_published":"2023-06-01T00:00:00Z","author":[{"last_name":"Avarikioti","full_name":"Avarikioti, Zeta","first_name":"Zeta"},{"id":"06d0c166-aec1-11ee-a7c0-b96e840a602b","last_name":"Desjardins","full_name":"Desjardins, Antoine","first_name":"Antoine"},{"last_name":"Kokoris Kogias","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30","first_name":"Eleftherios","full_name":"Kokoris Kogias, Eleftherios"},{"full_name":"Wattenhofer, Roger","first_name":"Roger","last_name":"Wattenhofer"}],"title":"Divide & Scale: Formalization and roadmap to robust sharding","date_created":"2024-01-08T12:56:46Z","intvolume":"     13892","acknowledgement":"The work was partially supported by the Austrian Science Fund (FWF) through the project CoRaF (grant agreement 2020388).","doi":"10.1007/978-3-031-32733-9_10","volume":13892,"year":"2023","publication":"30th International Colloquium on Structural Information and Communication Complexity","scopus_import":"1","status":"public","isi":1,"alternative_title":["LNCS"],"publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"eisbn":["9783031327339"],"isbn":["9783031327322"]},"day":"01","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","department":[{"_id":"ElKo"}],"article_processing_charge":"No","external_id":{"isi":["001292782600010"]},"publication_status":"published"}]