[{"external_id":{"isi":["000890138700001"]},"article_processing_charge":"No","author":[{"id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","first_name":"Mirza Ahad","last_name":"Baig","full_name":"Baig, Mirza Ahad"},{"last_name":"Hendler","full_name":"Hendler, Danny","first_name":"Danny"},{"first_name":"Alessia","full_name":"Milani, Alessia","last_name":"Milani"},{"first_name":"Corentin","full_name":"Travers, Corentin","last_name":"Travers"}],"title":"Long-lived counters with polylogarithmic amortized step complexity","citation":{"mla":"Baig, Mirza Ahad, et al. “Long-Lived Counters with Polylogarithmic Amortized Step Complexity.” Distributed Computing, vol. 36, Springer Nature, 2023, pp. 29–43, doi:10.1007/s00446-022-00439-5.","short":"M.A. Baig, D. Hendler, A. Milani, C. Travers, Distributed Computing 36 (2023) 29–43.","ieee":"M. A. Baig, D. Hendler, A. Milani, and C. Travers, “Long-lived counters with polylogarithmic amortized step complexity,” Distributed Computing, vol. 36. Springer Nature, pp. 29–43, 2023.","ama":"Baig MA, Hendler D, Milani A, Travers C. Long-lived counters with polylogarithmic amortized step complexity. Distributed Computing. 2023;36:29-43. doi:10.1007/s00446-022-00439-5","apa":"Baig, M. A., Hendler, D., Milani, A., & Travers, C. (2023). Long-lived counters with polylogarithmic amortized step complexity. Distributed Computing. Springer Nature. https://doi.org/10.1007/s00446-022-00439-5","chicago":"Baig, Mirza Ahad, Danny Hendler, Alessia Milani, and Corentin Travers. “Long-Lived Counters with Polylogarithmic Amortized Step Complexity.” Distributed Computing. Springer Nature, 2023. https://doi.org/10.1007/s00446-022-00439-5.","ista":"Baig MA, Hendler D, Milani A, Travers C. 2023. Long-lived counters with polylogarithmic amortized step complexity. Distributed Computing. 36, 29–43."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"29-43","date_created":"2023-01-12T12:10:08Z","doi":"10.1007/s00446-022-00439-5","date_published":"2023-03-01T00:00:00Z","year":"2023","isi":1,"publication":"Distributed Computing","day":"01","oa":1,"quality_controlled":"1","publisher":"Springer Nature","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).","department":[{"_id":"KrPi"}],"date_updated":"2023-08-16T08:39:36Z","type":"journal_article","article_type":"original","keyword":["Computational Theory and Mathematics","Computer Networks and Communications","Hardware and Architecture","Theoretical Computer Science"],"status":"public","_id":"12164","volume":36,"publication_status":"published","publication_identifier":{"eissn":["1432-0452"],"issn":["0178-2770"]},"language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://drops.dagstuhl.de/opus/volltexte/2019/11310/"}],"scopus_import":"1","intvolume":" 36","month":"03","abstract":[{"lang":"eng","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."}],"oa_version":"Preprint"},{"acknowledgement":"B. Auerbach, M.A. Baig and K. Pietrzak—received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT); Karen Klein was supported in part by ERC CoG grant 724307 and conducted part of this work at IST Austria, funded by the ERC under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT); Guillermo Pascual-Perez was funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 665385; Michael Walter conducted part of this work at IST Austria, funded by the ERC under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT).","oa":1,"publisher":"Springer Nature","quality_controlled":"1","year":"2021","isi":1,"publication":"19th International Conference","day":"04","page":"222-253","date_created":"2021-12-05T23:01:42Z","date_published":"2021-11-04T00:00:00Z","doi":"10.1007/978-3-030-90456-2_8","project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"},{"grant_number":"665385","name":"International IST Doctoral Program","call_identifier":"H2020","_id":"2564DBCA-B435-11E9-9278-68D0E5697425"}],"citation":{"chicago":"Alwen, Joel F, Benedikt Auerbach, Mirza Ahad Baig, Miguel Cueto Noval, Karen Klein, Guillermo Pascual Perez, Krzysztof Z Pietrzak, and Michael Walter. “Grafting Key Trees: Efficient Key Management for Overlapping Groups.” In 19th International Conference, 13044:222–53. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-90456-2_8.","ista":"Alwen JF, Auerbach B, Baig MA, Cueto Noval M, Klein K, Pascual Perez G, Pietrzak KZ, Walter M. 2021. Grafting key trees: Efficient key management for overlapping groups. 19th International Conference. TCC: Theory of Cryptography, LNCS, vol. 13044, 222–253.","mla":"Alwen, Joel F., et al. “Grafting Key Trees: Efficient Key Management for Overlapping Groups.” 19th International Conference, vol. 13044, Springer Nature, 2021, pp. 222–53, doi:10.1007/978-3-030-90456-2_8.","short":"J.F. Alwen, B. Auerbach, M.A. Baig, M. Cueto Noval, K. Klein, G. Pascual Perez, K.Z. Pietrzak, M. Walter, in:, 19th International Conference, Springer Nature, 2021, pp. 222–253.","ieee":"J. F. Alwen et al., “Grafting key trees: Efficient key management for overlapping groups,” in 19th International Conference, Raleigh, NC, United States, 2021, vol. 13044, pp. 222–253.","ama":"Alwen JF, Auerbach B, Baig MA, et al. Grafting key trees: Efficient key management for overlapping groups. In: 19th International Conference. Vol 13044. Springer Nature; 2021:222-253. doi:10.1007/978-3-030-90456-2_8","apa":"Alwen, J. F., Auerbach, B., Baig, M. A., Cueto Noval, M., Klein, K., Pascual Perez, G., … Walter, M. (2021). Grafting key trees: Efficient key management for overlapping groups. In 19th International Conference (Vol. 13044, pp. 222–253). Raleigh, NC, United States: Springer Nature. https://doi.org/10.1007/978-3-030-90456-2_8"},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","article_processing_charge":"No","external_id":{"isi":["000728363700008"]},"author":[{"full_name":"Alwen, Joel F","last_name":"Alwen","first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0002-7553-6606","full_name":"Auerbach, Benedikt","last_name":"Auerbach","first_name":"Benedikt","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425"},{"full_name":"Baig, Mirza Ahad","last_name":"Baig","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","first_name":"Mirza Ahad"},{"last_name":"Cueto Noval","full_name":"Cueto Noval, Miguel","first_name":"Miguel","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc"},{"full_name":"Klein, Karen","last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen"},{"orcid":"0000-0001-8630-415X","full_name":"Pascual Perez, Guillermo","last_name":"Pascual Perez","first_name":"Guillermo","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Walter","full_name":"Walter, Michael","orcid":"0000-0003-3186-2482","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","first_name":"Michael"}],"title":"Grafting key trees: Efficient key management for overlapping groups","abstract":[{"text":"Key trees are often the best solution in terms of transmission cost and storage requirements for managing keys in a setting where a group needs to share a secret key, while being able to efficiently rotate the key material of users (in order to recover from a potential compromise, or to add or remove users). Applications include multicast encryption protocols like LKH (Logical Key Hierarchies) or group messaging like the current IETF proposal TreeKEM. A key tree is a (typically balanced) binary tree, where each node is identified with a key: leaf nodes hold users’ secret keys while the root is the shared group key. For a group of size N, each user just holds log(N) keys (the keys on the path from its leaf to the root) and its entire key material can be rotated by broadcasting 2log(N) ciphertexts (encrypting each fresh key on the path under the keys of its parents). In this work we consider the natural setting where we have many groups with partially overlapping sets of users, and ask if we can find solutions where the cost of rotating a key is better than in the trivial one where we have a separate key tree for each group. We show that in an asymptotic setting (where the number m of groups is fixed while the number N of users grows) there exist more general key graphs whose cost converges to the cost of a single group, thus saving a factor linear in the number of groups over the trivial solution. As our asymptotic “solution” converges very slowly and performs poorly on concrete examples, we propose an algorithm that uses a natural heuristic to compute a key graph for any given group structure. Our algorithm combines two greedy algorithms, and is thus very efficient: it first converts the group structure into a “lattice graph”, which is then turned into a key graph by repeatedly applying the algorithm for constructing a Huffman code. To better understand how far our proposal is from an optimal solution, we prove lower bounds on the update cost of continuous group-key agreement and multicast encryption in a symbolic model admitting (asymmetric) encryption, pseudorandom generators, and secret sharing as building blocks.","lang":"eng"}],"oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/1158"}],"alternative_title":["LNCS"],"scopus_import":"1","intvolume":" 13044","month":"11","publication_status":"published","publication_identifier":{"isbn":["9-783-0309-0455-5"],"eissn":["1611-3349"],"issn":["0302-9743"],"eisbn":["978-3-030-90456-2"]},"language":[{"iso":"eng"}],"ec_funded":1,"volume":13044,"_id":"10408","conference":{"name":"TCC: Theory of Cryptography","start_date":"2021-11-08","end_date":"2021-11-11","location":"Raleigh, NC, United States"},"type":"conference","status":"public","date_updated":"2023-08-14T13:19:39Z","department":[{"_id":"KrPi"}]},{"page":"31-40","date_created":"2020-09-13T22:01:17Z","date_published":"2020-07-31T00:00:00Z","doi":"10.1145/3382734.3406005","year":"2020","publication_status":"published","publication_identifier":{"isbn":["9781450375825"]},"publication":"Proceedings of the 39th Symposium on Principles of Distributed Computing","language":[{"iso":"eng"}],"day":"31","main_file_link":[{"url":"https://hal.archives-ouvertes.fr/hal-02860087/document","open_access":"1"}],"oa":1,"scopus_import":"1","publisher":"Association for Computing Machinery","quality_controlled":"1","month":"07","abstract":[{"text":"We present the first deterministic wait-free long-lived snapshot algorithm, using only read and write operations, that guarantees polylogarithmic amortized step complexity in all executions. This is the first non-blocking snapshot algorithm, using reads and writes only, that has sub-linear amortized step complexity in executions of arbitrary length. The key to our construction is a novel implementation of a 2-component max array object which may be of independent interest.","lang":"eng"}],"oa_version":"Preprint","article_processing_charge":"No","author":[{"last_name":"Baig","full_name":"Baig, Mirza Ahad","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","first_name":"Mirza Ahad"},{"last_name":"Hendler","full_name":"Hendler, Danny","first_name":"Danny"},{"last_name":"Milani","full_name":"Milani, Alessia","first_name":"Alessia"},{"full_name":"Travers, Corentin","last_name":"Travers","first_name":"Corentin"}],"title":"Long-lived snapshots with polylogarithmic amortized step complexity","citation":{"ista":"Baig MA, Hendler D, Milani A, Travers C. 2020. Long-lived snapshots with polylogarithmic amortized step complexity. Proceedings of the 39th Symposium on Principles of Distributed Computing. PODC: Principles of Distributed Computing, 31–40.","chicago":"Baig, Mirza Ahad, Danny Hendler, Alessia Milani, and Corentin Travers. “Long-Lived Snapshots with Polylogarithmic Amortized Step Complexity.” In Proceedings of the 39th Symposium on Principles of Distributed Computing, 31–40. Association for Computing Machinery, 2020. https://doi.org/10.1145/3382734.3406005.","ieee":"M. A. Baig, D. Hendler, A. Milani, and C. Travers, “Long-lived snapshots with polylogarithmic amortized step complexity,” in Proceedings of the 39th Symposium on Principles of Distributed Computing, Virtual, Italy, 2020, pp. 31–40.","short":"M.A. Baig, D. Hendler, A. Milani, C. Travers, in:, Proceedings of the 39th Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2020, pp. 31–40.","ama":"Baig MA, Hendler D, Milani A, Travers C. Long-lived snapshots with polylogarithmic amortized step complexity. In: Proceedings of the 39th Symposium on Principles of Distributed Computing. Association for Computing Machinery; 2020:31-40. doi:10.1145/3382734.3406005","apa":"Baig, M. A., Hendler, D., Milani, A., & Travers, C. (2020). Long-lived snapshots with polylogarithmic amortized step complexity. In Proceedings of the 39th Symposium on Principles of Distributed Computing (pp. 31–40). Virtual, Italy: Association for Computing Machinery. https://doi.org/10.1145/3382734.3406005","mla":"Baig, Mirza Ahad, et al. “Long-Lived Snapshots with Polylogarithmic Amortized Step Complexity.” Proceedings of the 39th Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2020, pp. 31–40, doi:10.1145/3382734.3406005."},"date_updated":"2024-02-28T12:54:30Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"location":"Virtual, Italy","end_date":"2020-08-07","start_date":"2020-08-03","name":"PODC: Principles of Distributed Computing"},"type":"conference","status":"public","_id":"8382"}]