[{"volume":36,"acknowledgement":"A preliminary version of this work appeared in DISC’19. Mirza Ahad Baig, Alessia Milani and Corentin Travers are supported by ANR projects Descartes and FREDDA. Mirza Ahad Baig is supported by UMI Relax. Danny Hendler is supported by the Israel Science Foundation (Grants 380/18 and 1425/22).","abstract":[{"text":"A shared-memory counter is a widely-used and well-studied concurrent object. It supports two operations: An Inc operation that increases its value by 1 and a Read operation that returns its current value. In Jayanti et al (SIAM J Comput, 30(2), 2000), Jayanti, Tan and Toueg proved a linear lower bound on the worst-case step complexity of obstruction-free implementations, from read-write registers, of a large class of shared objects that includes counters. The lower bound leaves open the question of finding counter implementations with sub-linear amortized step complexity. In this work, we address this gap. We show that n-process, wait-free and linearizable counters can be implemented from read-write registers with O(log2n) amortized step complexity. This is the first counter algorithm from read-write registers that provides sub-linear amortized step complexity in executions of arbitrary length. Since a logarithmic lower bound on the amortized step complexity of obstruction-free counter implementations exists, our upper bound is within a logarithmic factor of the optimal. The worst-case step complexity of the construction remains linear, which is optimal. This is obtained thanks to a new max register construction with O(logn) amortized step complexity in executions of arbitrary length in which the value stored in the register does not grow too quickly. We then leverage an existing counter algorithm by Aspnes, Attiya and Censor-Hillel [1] in which we “plug” our max register implementation to show that it remains linearizable while achieving O(log2n) amortized step complexity.","lang":"eng"}],"doi":"10.1007/s00446-022-00439-5","day":"01","isi":1,"external_id":{"isi":["000890138700001"]},"date_updated":"2023-08-16T08:39:36Z","year":"2023","citation":{"apa":"Baig, M. A., Hendler, D., Milani, A., &#38; Travers, C. (2023). Long-lived counters with polylogarithmic amortized step complexity. <i>Distributed Computing</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00446-022-00439-5\">https://doi.org/10.1007/s00446-022-00439-5</a>","ama":"Baig MA, Hendler D, Milani A, Travers C. Long-lived counters with polylogarithmic amortized step complexity. <i>Distributed Computing</i>. 2023;36:29-43. doi:<a href=\"https://doi.org/10.1007/s00446-022-00439-5\">10.1007/s00446-022-00439-5</a>","chicago":"Baig, Mirza Ahad, Danny Hendler, Alessia Milani, and Corentin Travers. “Long-Lived Counters with Polylogarithmic Amortized Step Complexity.” <i>Distributed Computing</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s00446-022-00439-5\">https://doi.org/10.1007/s00446-022-00439-5</a>.","ieee":"M. A. Baig, D. Hendler, A. Milani, and C. Travers, “Long-lived counters with polylogarithmic amortized step complexity,” <i>Distributed Computing</i>, vol. 36. Springer Nature, pp. 29–43, 2023.","short":"M.A. Baig, D. Hendler, A. Milani, C. Travers, Distributed Computing 36 (2023) 29–43.","mla":"Baig, Mirza Ahad, et al. “Long-Lived Counters with Polylogarithmic Amortized Step Complexity.” <i>Distributed Computing</i>, vol. 36, Springer Nature, 2023, pp. 29–43, doi:<a href=\"https://doi.org/10.1007/s00446-022-00439-5\">10.1007/s00446-022-00439-5</a>.","ista":"Baig MA, Hendler D, Milani A, Travers C. 2023. Long-lived counters with polylogarithmic amortized step complexity. Distributed Computing. 36, 29–43."},"article_type":"original","publisher":"Springer Nature","page":"29-43","quality_controlled":"1","title":"Long-lived counters with polylogarithmic amortized step complexity","intvolume":"        36","publication_status":"published","department":[{"_id":"KrPi"}],"article_processing_charge":"No","date_created":"2023-01-12T12:10:08Z","author":[{"full_name":"Baig, Mirza Ahad","last_name":"Baig","first_name":"Mirza Ahad","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425"},{"full_name":"Hendler, Danny","last_name":"Hendler","first_name":"Danny"},{"full_name":"Milani, Alessia","last_name":"Milani","first_name":"Alessia"},{"full_name":"Travers, Corentin","first_name":"Corentin","last_name":"Travers"}],"_id":"12164","scopus_import":"1","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"open_access":"1","url":"https://drops.dagstuhl.de/opus/volltexte/2019/11310/"}],"oa":1,"publication_identifier":{"eissn":["1432-0452"],"issn":["0178-2770"]},"date_published":"2023-03-01T00:00:00Z","type":"journal_article","language":[{"iso":"eng"}],"keyword":["Computational Theory and Mathematics","Computer Networks and Communications","Hardware and Architecture","Theoretical Computer Science"],"month":"03","oa_version":"Preprint","publication":"Distributed Computing"},{"keyword":["Computer Networks and Communications","Hardware and Architecture","Safety","Risk","Reliability and Quality","Computer Science (miscellaneous)"],"language":[{"iso":"eng"}],"month":"03","project":[{"name":"Coordination in constrained and natural distributed systems","grant_number":"840605","_id":"26A5D39A-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"},{"name":"Elastic Coordination for Scalable Machine Learning","grant_number":"805223","call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425"}],"oa_version":"Preprint","publication":"Proceedings of the ACM on Measurement and Analysis of Computing Systems","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","related_material":{"record":[{"status":"public","id":"10854","relation":"shorter_version"}]},"main_file_link":[{"url":"https://arxiv.org/abs/2005.07637","open_access":"1"}],"oa":1,"publication_identifier":{"issn":["2476-1249"]},"type":"journal_article","date_published":"2021-03-01T00:00:00Z","article_type":"original","publisher":"Association for Computing Machinery","ec_funded":1,"quality_controlled":"1","page":"1-33","intvolume":"         5","title":"Input-dynamic distributed algorithms for communication networks","date_created":"2022-03-18T09:10:27Z","department":[{"_id":"DaAl"}],"article_processing_charge":"No","publication_status":"published","issue":"1","author":[{"first_name":"Klaus-Tycho","last_name":"Foerster","full_name":"Foerster, Klaus-Tycho"},{"full_name":"Korhonen, Janne","first_name":"Janne","last_name":"Korhonen","id":"C5402D42-15BC-11E9-A202-CA2BE6697425"},{"first_name":"Ami","last_name":"Paz","full_name":"Paz, Ami"},{"id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6432-6646","full_name":"Rybicki, Joel","first_name":"Joel","last_name":"Rybicki"},{"full_name":"Schmid, Stefan","first_name":"Stefan","last_name":"Schmid"}],"scopus_import":"1","_id":"10855","acknowledgement":"We thank Jukka Suomela for discussions. We also thank our shepherd Mohammad Hajiesmaili\r\nand the reviewers for their time and suggestions on how to improve the paper. This project\r\nhas received funding from the European Research Council (ERC) under the European Union’s\r\nHorizon 2020 research and innovation programme (grant agreement No 805223 ScaleML), from the European Union’s Horizon 2020 research and innovation programme under the Marie\r\nSk lodowska–Curie grant agreement No. 840605, from the Vienna Science and Technology Fund (WWTF) project WHATIF, ICT19-045, 2020-2024, and from the Austrian Science Fund (FWF) and netIDEE SCIENCE project P 33775-N.","volume":5,"abstract":[{"text":"Consider a distributed task where the communication network is fixed but the local inputs given to the nodes of the distributed system may change over time. In this work, we explore the following question: if some of the local inputs change, can an existing solution be updated efficiently, in a dynamic and distributed manner? To address this question, we define the batch dynamic \\congest model in which we are given a bandwidth-limited communication network and a dynamic edge labelling defines the problem input. The task is to maintain a solution to a graph problem on the labeled graph under batch changes. We investigate, when a batch of α edge label changes arrive, \\beginitemize \\item how much time as a function of α we need to update an existing solution, and \\item how much information the nodes have to keep in local memory between batches in order to update the solution quickly. \\enditemize Our work lays the foundations for the theory of input-dynamic distributed network algorithms. We give a general picture of the complexity landscape in this model, design both universal algorithms and algorithms for concrete problems, and present a general framework for lower bounds. In particular, we derive non-trivial upper bounds for two selected, contrasting problems: maintaining a minimum spanning tree and detecting cliques.","lang":"eng"}],"day":"01","arxiv":1,"doi":"10.1145/3447384","external_id":{"arxiv":["2005.07637"]},"year":"2021","citation":{"apa":"Foerster, K.-T., Korhonen, J., Paz, A., Rybicki, J., &#38; Schmid, S. (2021). Input-dynamic distributed algorithms for communication networks. <i>Proceedings of the ACM on Measurement and Analysis of Computing Systems</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3447384\">https://doi.org/10.1145/3447384</a>","ama":"Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. Input-dynamic distributed algorithms for communication networks. <i>Proceedings of the ACM on Measurement and Analysis of Computing Systems</i>. 2021;5(1):1-33. doi:<a href=\"https://doi.org/10.1145/3447384\">10.1145/3447384</a>","ieee":"K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, and S. Schmid, “Input-dynamic distributed algorithms for communication networks,” <i>Proceedings of the ACM on Measurement and Analysis of Computing Systems</i>, vol. 5, no. 1. Association for Computing Machinery, pp. 1–33, 2021.","chicago":"Foerster, Klaus-Tycho, Janne Korhonen, Ami Paz, Joel Rybicki, and Stefan Schmid. “Input-Dynamic Distributed Algorithms for Communication Networks.” <i>Proceedings of the ACM on Measurement and Analysis of Computing Systems</i>. Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3447384\">https://doi.org/10.1145/3447384</a>.","short":"K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, S. Schmid, Proceedings of the ACM on Measurement and Analysis of Computing Systems 5 (2021) 1–33.","mla":"Foerster, Klaus-Tycho, et al. “Input-Dynamic Distributed Algorithms for Communication Networks.” <i>Proceedings of the ACM on Measurement and Analysis of Computing Systems</i>, vol. 5, no. 1, Association for Computing Machinery, 2021, pp. 1–33, doi:<a href=\"https://doi.org/10.1145/3447384\">10.1145/3447384</a>.","ista":"Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. 2021. Input-dynamic distributed algorithms for communication networks. Proceedings of the ACM on Measurement and Analysis of Computing Systems. 5(1), 1–33."},"date_updated":"2023-09-26T10:40:55Z"}]