[{"main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.2105.13172"}],"arxiv":1,"publisher":"Institute of Electrical and Electronics Engineers","quality_controlled":"1","type":"conference","language":[{"iso":"eng"}],"article_processing_charge":"No","month":"06","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"21","citation":{"mla":"Henzinger, Monika H., et al. “On the Complexity of Weight-Dynamic Network Algorithms.” <i>IFIP Networking Conference</i>, Institute of Electrical and Electronics Engineers, 2021, doi:<a href=\"https://doi.org/10.23919/ifipnetworking52078.2021.9472803\">10.23919/ifipnetworking52078.2021.9472803</a>.","chicago":"Henzinger, Monika H, Ami Paz, and Stefan Schmid. “On the Complexity of Weight-Dynamic Network Algorithms.” In <i>IFIP Networking Conference</i>. Institute of Electrical and Electronics Engineers, 2021. <a href=\"https://doi.org/10.23919/ifipnetworking52078.2021.9472803\">https://doi.org/10.23919/ifipnetworking52078.2021.9472803</a>.","ieee":"M. H. Henzinger, A. Paz, and S. Schmid, “On the complexity of weight-dynamic network algorithms,” in <i>IFIP Networking Conference</i>,  Espoo and Helsinki, Finland, 2021.","apa":"Henzinger, M. H., Paz, A., &#38; Schmid, S. (2021). On the complexity of weight-dynamic network algorithms. In <i>IFIP Networking Conference</i>.  Espoo and Helsinki, Finland: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.23919/ifipnetworking52078.2021.9472803\">https://doi.org/10.23919/ifipnetworking52078.2021.9472803</a>","ama":"Henzinger MH, Paz A, Schmid S. On the complexity of weight-dynamic network algorithms. In: <i>IFIP Networking Conference</i>. Institute of Electrical and Electronics Engineers; 2021. doi:<a href=\"https://doi.org/10.23919/ifipnetworking52078.2021.9472803\">10.23919/ifipnetworking52078.2021.9472803</a>","ista":"Henzinger MH, Paz A, Schmid S. 2021. On the complexity of weight-dynamic network algorithms. IFIP Networking Conference. IFIP: Networking.","short":"M.H. Henzinger, A. Paz, S. Schmid, in:, IFIP Networking Conference, Institute of Electrical and Electronics Engineers, 2021."},"scopus_import":"1","conference":{"name":"IFIP: Networking","location":" Espoo and Helsinki, Finland","start_date":"2021-06-21","end_date":"2021-06-24"},"date_created":"2022-07-25T11:13:06Z","oa_version":"Preprint","extern":"1","external_id":{"arxiv":["2105.13172"]},"date_published":"2021-06-21T00:00:00Z","date_updated":"2023-02-09T09:11:51Z","publication":"IFIP Networking Conference","publication_identifier":{"eissn":["1861-2288"]},"publication_status":"published","status":"public","_id":"11649","author":[{"full_name":"Henzinger, Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","orcid":"0000-0002-5008-6530"},{"full_name":"Paz, Ami","last_name":"Paz","first_name":"Ami"},{"first_name":"Stefan","full_name":"Schmid, Stefan","last_name":"Schmid"}],"oa":1,"title":"On the complexity of weight-dynamic network algorithms","doi":"10.23919/ifipnetworking52078.2021.9472803","year":"2021","abstract":[{"lang":"eng","text":"While operating communication networks adaptively may improve utilization and performance, frequent adjustments also introduce an algorithmic challenge: the re-optimization of traffic engineering solutions is time-consuming and may limit the granularity at which a network can be adjusted. This paper is motivated by question whether the reactivity of a network can be improved by re-optimizing solutions dynamically rather than from scratch, especially if inputs such as link weights do not change significantly. This paper explores to what extent dynamic algorithms can be used to speed up fundamental tasks in network operations. We specifically investigate optimizations related to traffic engineering (namely shortest paths and maximum flow computations), but also consider spanning tree and matching applications. While prior work on dynamic graph algorithms focusses on link insertions and deletions, we are interested in the practical problem of link weight changes. We revisit existing upper bounds in the weight-dynamic model, and present several novel lower bounds on the amortized runtime for recomputing solutions. In general, we find that the potential performance gains depend on the application, and there are also strict limitations on what can be achieved, even if link weights change only slightly."}]},{"publication_status":"published","status":"public","ec_funded":1,"publication_identifier":{"eissn":["1861-2288"],"isbn":["978-1-6654-4501-6"],"eisbn":["978-3-9031-7639-3"]},"project":[{"grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks"}],"abstract":[{"lang":"eng","text":"Payment channel networks are a promising approach to improve the scalability of cryptocurrencies: they allow to perform transactions in a peer-to-peer fashion, along multihop routes in the network, without requiring consensus on the blockchain. However, during the discovery of cost-efficient routes for the transaction, critical information may be revealed about the transacting entities. This paper initiates the study of privacy-preserving route discovery mechanisms for payment channel networks. In particular, we present LightPIR, an approach which allows a client to learn the shortest (or cheapest in terms of fees) path between two nodes without revealing any information about the endpoints of the transaction to the servers. The two main observations which allow for an efficient solution in LightPIR are that: (1) surprisingly, hub labelling algorithms – which were developed to preprocess “street network like” graphs so one can later efficiently compute shortest paths – also perform well for the graphs underlying payment channel networks, and that (2) hub labelling algorithms can be conveniently combined with private information retrieval. LightPIR relies on a simple hub labeling heuristic on top of existing hub labeling algorithms which leverages the specific topological features of cryptocurrency networks to further minimize storage and bandwidth overheads. In a case study considering the Lightning network, we show that our approach is an order of magnitude more efficient compared to a privacy-preserving baseline based on using private information retrieval on a database that stores all pairs shortest paths."}],"doi":"10.23919/IFIPNetworking52078.2021.9472205","author":[{"first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654"},{"first_name":"Iosif","last_name":"Salem","full_name":"Salem, Iosif"},{"full_name":"Schmid, Stefan","last_name":"Schmid","first_name":"Stefan"},{"last_name":"Yeo","full_name":"Yeo, Michelle X","first_name":"Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"}],"title":"LightPIR: Privacy-preserving route discovery for payment channel networks","_id":"9969","article_processing_charge":"No","arxiv":1,"conference":{"location":"Espoo and Helsinki, Finland","start_date":"2021-06-21","end_date":"2021-06-24","name":"2021 IFIP Networking Conference (IFIP Networking)"},"oa_version":"Submitted Version","day":"21","citation":{"mla":"Pietrzak, Krzysztof Z., et al. <i>LightPIR: Privacy-Preserving Route Discovery for Payment Channel Networks</i>. IEEE, 2021, doi:<a href=\"https://doi.org/10.23919/IFIPNetworking52078.2021.9472205\">10.23919/IFIPNetworking52078.2021.9472205</a>.","chicago":"Pietrzak, Krzysztof Z, Iosif Salem, Stefan Schmid, and Michelle X Yeo. “LightPIR: Privacy-Preserving Route Discovery for Payment Channel Networks.” IEEE, 2021. <a href=\"https://doi.org/10.23919/IFIPNetworking52078.2021.9472205\">https://doi.org/10.23919/IFIPNetworking52078.2021.9472205</a>.","ama":"Pietrzak KZ, Salem I, Schmid S, Yeo MX. LightPIR: Privacy-preserving route discovery for payment channel networks. In: IEEE; 2021. doi:<a href=\"https://doi.org/10.23919/IFIPNetworking52078.2021.9472205\">10.23919/IFIPNetworking52078.2021.9472205</a>","ista":"Pietrzak KZ, Salem I, Schmid S, Yeo MX. 2021. LightPIR: Privacy-preserving route discovery for payment channel networks. 2021 IFIP Networking Conference (IFIP Networking).","short":"K.Z. Pietrzak, I. Salem, S. Schmid, M.X. Yeo, in:, IEEE, 2021.","ieee":"K. Z. Pietrzak, I. Salem, S. Schmid, and M. X. Yeo, “LightPIR: Privacy-preserving route discovery for payment channel networks,” presented at the 2021 IFIP Networking Conference (IFIP Networking), Espoo and Helsinki, Finland, 2021.","apa":"Pietrzak, K. Z., Salem, I., Schmid, S., &#38; Yeo, M. X. (2021). LightPIR: Privacy-preserving route discovery for payment channel networks. Presented at the 2021 IFIP Networking Conference (IFIP Networking), Espoo and Helsinki, Finland: IEEE. <a href=\"https://doi.org/10.23919/IFIPNetworking52078.2021.9472205\">https://doi.org/10.23919/IFIPNetworking52078.2021.9472205</a>"},"month":"06","related_material":{"record":[{"id":"14506","relation":"dissertation_contains","status":"public"}]},"date_updated":"2023-11-30T10:54:50Z","year":"2021","oa":1,"isi":1,"type":"conference","language":[{"iso":"eng"}],"quality_controlled":"1","main_file_link":[{"url":"https://arxiv.org/abs/2104.04293","open_access":"1"}],"publisher":"IEEE","external_id":{"isi":["000853016800008"],"arxiv":["2104.04293"]},"date_published":"2021-06-21T00:00:00Z","scopus_import":"1","date_created":"2021-08-29T22:01:16Z","department":[{"_id":"KrPi"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8"}]