--- _id: '12330' abstract: - lang: eng text: 'The design and implementation of efficient concurrent data structures has seen significant attention. However, most of this work has focused on concurrent data structures providing good worst-case guarantees, although, in real workloads, objects are often accessed at different rates. Efficient distribution-adaptive data structures, such as splay-trees, are known in the sequential case; however, they often are hard to translate efficiently to the concurrent case. We investigate distribution-adaptive concurrent data structures, and propose a new design called the splay-list. At a high level, the splay-list is similar to a standard skip-list, with the key distinction that the height of each element adapts dynamically to its access rate: popular elements “move up,” whereas rarely-accessed elements decrease in height. We show that the splay-list provides order-optimal amortized complexity bounds for a subset of operations, while being amenable to efficient concurrent implementation. Experiments show that the splay-list can leverage distribution-adaptivity for performance, and can outperform the only previously-known distribution-adaptive concurrent design in certain workloads.' article_processing_charge: No article_type: original author: - first_name: Vitalii full_name: Aksenov, Vitalii id: 2980135A-F248-11E8-B48F-1D18A9856A87 last_name: Aksenov - first_name: Dan-Adrian full_name: Alistarh, Dan-Adrian id: 4A899BFC-F248-11E8-B48F-1D18A9856A87 last_name: Alistarh orcid: 0000-0003-3650-940X - first_name: Alexandra full_name: Drozdova, Alexandra last_name: Drozdova - first_name: Amirkeivan full_name: Mohtashami, Amirkeivan last_name: Mohtashami citation: ama: 'Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. The splay-list: A distribution-adaptive concurrent skip-list. Distributed Computing. 2023;36:395-418. doi:10.1007/s00446-022-00441-x' apa: 'Aksenov, V., Alistarh, D.-A., Drozdova, A., & Mohtashami, A. (2023). The splay-list: A distribution-adaptive concurrent skip-list. Distributed Computing. Springer Nature. https://doi.org/10.1007/s00446-022-00441-x' chicago: 'Aksenov, Vitalii, Dan-Adrian Alistarh, Alexandra Drozdova, and Amirkeivan Mohtashami. “The Splay-List: A Distribution-Adaptive Concurrent Skip-List.” Distributed Computing. Springer Nature, 2023. https://doi.org/10.1007/s00446-022-00441-x.' ieee: 'V. Aksenov, D.-A. Alistarh, A. Drozdova, and A. Mohtashami, “The splay-list: A distribution-adaptive concurrent skip-list,” Distributed Computing, vol. 36. Springer Nature, pp. 395–418, 2023.' ista: 'Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. 2023. The splay-list: A distribution-adaptive concurrent skip-list. Distributed Computing. 36, 395–418.' mla: 'Aksenov, Vitalii, et al. “The Splay-List: A Distribution-Adaptive Concurrent Skip-List.” Distributed Computing, vol. 36, Springer Nature, 2023, pp. 395–418, doi:10.1007/s00446-022-00441-x.' short: V. Aksenov, D.-A. Alistarh, A. Drozdova, A. Mohtashami, Distributed Computing 36 (2023) 395–418. date_created: 2023-01-22T23:00:55Z date_published: 2023-09-01T00:00:00Z date_updated: 2023-08-14T12:54:32Z day: '01' department: - _id: DaAl doi: 10.1007/s00446-022-00441-x external_id: arxiv: - '2008.01009' isi: - '000913424000001' intvolume: ' 36' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.2008.01009 month: '09' oa: 1 oa_version: Preprint page: 395-418 publication: Distributed Computing publication_identifier: eissn: - 1432-0452 issn: - 0178-2770 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: 'The splay-list: A distribution-adaptive concurrent skip-list' type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 36 year: '2023' ... --- _id: '12164' 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.' 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). article_processing_charge: No article_type: original author: - first_name: Mirza Ahad full_name: Baig, Mirza Ahad id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425 last_name: Baig - first_name: Danny full_name: Hendler, Danny last_name: Hendler - first_name: Alessia full_name: Milani, Alessia last_name: Milani - first_name: Corentin full_name: Travers, Corentin last_name: Travers citation: 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. 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. ista: Baig MA, Hendler D, Milani A, Travers C. 2023. Long-lived counters with polylogarithmic amortized step complexity. Distributed Computing. 36, 29–43. 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. date_created: 2023-01-12T12:10:08Z date_published: 2023-03-01T00:00:00Z date_updated: 2023-08-16T08:39:36Z day: '01' department: - _id: KrPi doi: 10.1007/s00446-022-00439-5 external_id: isi: - '000890138700001' intvolume: ' 36' isi: 1 keyword: - Computational Theory and Mathematics - Computer Networks and Communications - Hardware and Architecture - Theoretical Computer Science language: - iso: eng main_file_link: - open_access: '1' url: https://drops.dagstuhl.de/opus/volltexte/2019/11310/ month: '03' oa: 1 oa_version: Preprint page: 29-43 publication: Distributed Computing publication_identifier: eissn: - 1432-0452 issn: - 0178-2770 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Long-lived counters with polylogarithmic amortized step complexity type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 36 year: '2023' ... --- _id: '7939' abstract: - lang: eng text: "We design fast deterministic algorithms for distance computation in the Congested Clique model. Our key contributions include:\r\n A (2+ϵ)-approximation for all-pairs shortest paths in O(log2n/ϵ) rounds on unweighted undirected graphs. With a small additional additive factor, this also applies for weighted graphs. This is the first sub-polynomial constant-factor approximation for APSP in this model.\r\n A (1+ϵ)-approximation for multi-source shortest paths from O(n−−√) sources in O(log2n/ϵ) rounds on weighted undirected graphs. This is the first sub-polynomial algorithm obtaining this approximation for a set of sources of polynomial size.\r\n\r\nOur main techniques are new distance tools that are obtained via improved algorithms for sparse matrix multiplication, which we leverage to construct efficient hopsets and shortest paths. Furthermore, our techniques extend to additional distance problems for which we improve upon the state-of-the-art, including diameter approximation, and an exact single-source shortest paths algorithm for weighted undirected graphs in O~(n1/6) rounds. " acknowledgement: Open access funding provided by Institute of Science and Technology (IST Austria). We thank Mohsen Ghaffari, Michael Elkin and Merav Parter for fruitful discussions. This project has received funding from the European Union’s Horizon 2020 Research And Innovation Program under Grant Agreement No. 755839. article_processing_charge: Yes (via OA deal) article_type: original author: - first_name: Keren full_name: Censor-Hillel, Keren last_name: Censor-Hillel - first_name: Michal full_name: Dory, Michal last_name: Dory - first_name: Janne full_name: Korhonen, Janne id: C5402D42-15BC-11E9-A202-CA2BE6697425 last_name: Korhonen - first_name: Dean full_name: Leitersdorf, Dean last_name: Leitersdorf citation: ama: Censor-Hillel K, Dory M, Korhonen J, Leitersdorf D. Fast approximate shortest paths in the congested clique. Distributed Computing. 2021;34:463-487. doi:10.1007/s00446-020-00380-5 apa: Censor-Hillel, K., Dory, M., Korhonen, J., & Leitersdorf, D. (2021). Fast approximate shortest paths in the congested clique. Distributed Computing. Springer Nature. https://doi.org/10.1007/s00446-020-00380-5 chicago: Censor-Hillel, Keren, Michal Dory, Janne Korhonen, and Dean Leitersdorf. “Fast Approximate Shortest Paths in the Congested Clique.” Distributed Computing. Springer Nature, 2021. https://doi.org/10.1007/s00446-020-00380-5. ieee: K. Censor-Hillel, M. Dory, J. Korhonen, and D. Leitersdorf, “Fast approximate shortest paths in the congested clique,” Distributed Computing, vol. 34. Springer Nature, pp. 463–487, 2021. ista: Censor-Hillel K, Dory M, Korhonen J, Leitersdorf D. 2021. Fast approximate shortest paths in the congested clique. Distributed Computing. 34, 463–487. mla: Censor-Hillel, Keren, et al. “Fast Approximate Shortest Paths in the Congested Clique.” Distributed Computing, vol. 34, Springer Nature, 2021, pp. 463–87, doi:10.1007/s00446-020-00380-5. short: K. Censor-Hillel, M. Dory, J. Korhonen, D. Leitersdorf, Distributed Computing 34 (2021) 463–487. date_created: 2020-06-07T22:00:54Z date_published: 2021-12-01T00:00:00Z date_updated: 2024-03-07T14:43:39Z day: '01' department: - _id: DaAl doi: 10.1007/s00446-020-00380-5 external_id: arxiv: - '1903.05956' isi: - '000556444600001' intvolume: ' 34' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.1007/s00446-020-00380-5 month: '12' oa: 1 oa_version: Published Version page: 463-487 project: - _id: B67AFEDC-15C9-11EA-A837-991A96BB2854 name: IST Austria Open Access Fund publication: Distributed Computing publication_identifier: eissn: - 1432-0452 issn: - 0178-2770 publication_status: published publisher: Springer Nature quality_controlled: '1' related_material: record: - id: '6933' relation: earlier_version status: public scopus_import: '1' status: public title: Fast approximate shortest paths in the congested clique type: journal_article user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 34 year: '2021' ... --- _id: '7150' abstract: - lang: eng text: "In this work, we use algebraic methods for studying distance computation and subgraph detection tasks in the congested clique model. Specifically, we adapt parallel matrix multiplication implementations to the congested clique, obtaining an O(n1−2/ω) round matrix multiplication algorithm, where ω<2.3728639 is the exponent of matrix multiplication. In conjunction with known techniques from centralised algorithmics, this gives significant improvements over previous best upper bounds in the congested clique model. The highlight results include:\r\n\r\n1. triangle and 4-cycle counting in O(n0.158) rounds, improving upon the O(n1/3) algorithm of Dolev et al. [DISC 2012],\r\n2. a (1+o(1))-approximation of all-pairs shortest paths in O(n0.158) rounds, improving upon the O~(n1/2)-round (2+o(1))-approximation algorithm given by Nanongkai [STOC 2014], and\r\n 3. computing the girth in O(n0.158) rounds, which is the first non-trivial solution in this model.\r\n \r\nIn addition, we present a novel constant-round combinatorial algorithm for detecting 4-cycles." article_processing_charge: No article_type: original author: - first_name: Keren full_name: Censor-Hillel, Keren last_name: Censor-Hillel - first_name: Petteri full_name: Kaski, Petteri last_name: Kaski - first_name: Janne full_name: Korhonen, Janne id: C5402D42-15BC-11E9-A202-CA2BE6697425 last_name: Korhonen - first_name: Christoph full_name: Lenzen, Christoph last_name: Lenzen - first_name: Ami full_name: Paz, Ami last_name: Paz - first_name: Jukka full_name: Suomela, Jukka last_name: Suomela citation: ama: Censor-Hillel K, Kaski P, Korhonen J, Lenzen C, Paz A, Suomela J. Algebraic methods in the congested clique. Distributed Computing. 2019;32(6):461-478. doi:10.1007/s00446-016-0270-2 apa: Censor-Hillel, K., Kaski, P., Korhonen, J., Lenzen, C., Paz, A., & Suomela, J. (2019). Algebraic methods in the congested clique. Distributed Computing. Springer Nature. https://doi.org/10.1007/s00446-016-0270-2 chicago: Censor-Hillel, Keren, Petteri Kaski, Janne Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. “Algebraic Methods in the Congested Clique.” Distributed Computing. Springer Nature, 2019. https://doi.org/10.1007/s00446-016-0270-2. ieee: K. Censor-Hillel, P. Kaski, J. Korhonen, C. Lenzen, A. Paz, and J. Suomela, “Algebraic methods in the congested clique,” Distributed Computing, vol. 32, no. 6. Springer Nature, pp. 461–478, 2019. ista: Censor-Hillel K, Kaski P, Korhonen J, Lenzen C, Paz A, Suomela J. 2019. Algebraic methods in the congested clique. Distributed Computing. 32(6), 461–478. mla: Censor-Hillel, Keren, et al. “Algebraic Methods in the Congested Clique.” Distributed Computing, vol. 32, no. 6, Springer Nature, 2019, pp. 461–78, doi:10.1007/s00446-016-0270-2. short: K. Censor-Hillel, P. Kaski, J. Korhonen, C. Lenzen, A. Paz, J. Suomela, Distributed Computing 32 (2019) 461–478. date_created: 2019-12-05T09:49:49Z date_published: 2019-12-01T00:00:00Z date_updated: 2021-01-12T08:12:05Z day: '01' doi: 10.1007/s00446-016-0270-2 extern: '1' external_id: arxiv: - '1503.04963' intvolume: ' 32' issue: '6' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1503.04963 month: '12' oa: 1 oa_version: Preprint page: 461-478 publication: Distributed Computing publication_identifier: issn: - 0178-2770 - 1432-0452 publication_status: published publisher: Springer Nature quality_controlled: '1' status: public title: Algebraic methods in the congested clique type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 32 year: '2019' ...