[{"related_material":{"record":[{"status":"public","id":"10429","relation":"dissertation_contains"}]},"main_file_link":[{"url":"https://arxiv.org/abs/1804.01018","open_access":"1"}],"isi":1,"title":"Distributionally linearizable data structures","external_id":{"isi":["000545269600016"],"arxiv":["1804.01018"]},"year":"2018","doi":"10.1145/3210377.3210411","oa_version":"Preprint","quality_controlled":"1","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publication_identifier":{"isbn":["9781450357999"]},"_id":"5965","article_processing_charge":"No","date_updated":"2023-09-19T10:44:13Z","oa":1,"arxiv":1,"author":[{"first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"id":"3569F0A0-F248-11E8-B48F-1D18A9856A87","first_name":"Trevor A","last_name":"Brown","full_name":"Brown, Trevor A"},{"last_name":"Kopinsky","full_name":"Kopinsky, Justin","first_name":"Justin"},{"full_name":"Li, Jerry Z.","last_name":"Li","first_name":"Jerry Z."},{"full_name":"Nadiradze, Giorgi","last_name":"Nadiradze","first_name":"Giorgi"}],"abstract":[{"text":"Relaxed concurrent data structures have become increasingly popular, due to their scalability in graph processing and machine learning applications (\\citeNguyen13, gonzalez2012powergraph ). Despite considerable interest, there exist families of natural, high performing randomized relaxed concurrent data structures, such as the popular MultiQueue~\\citeMQ pattern for implementing relaxed priority queue data structures, for which no guarantees are known in the concurrent setting~\\citeAKLN17. Our main contribution is in showing for the first time that, under a set of analytic assumptions, a family of relaxed concurrent data structures, including variants of MultiQueues, but also a new approximate counting algorithm we call the MultiCounter, provides strong probabilistic guarantees on the degree of relaxation with respect to the sequential specification, in arbitrary concurrent executions. We formalize these guarantees via a new correctness condition called distributional linearizability, tailored to concurrent implementations with randomized relaxations. Our result is based on a new analysis of an asynchronous variant of the classic power-of-two-choices load balancing algorithm, in which placement choices can be based on inconsistent, outdated information (this result may be of independent interest). We validate our results empirically, showing that the MultiCounter algorithm can implement scalable relaxed timestamps.","lang":"eng"}],"citation":{"mla":"Alistarh, Dan-Adrian, et al. “Distributionally Linearizable Data Structures.” <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i>, ACM Press, 2018, pp. 133–42, doi:<a href=\"https://doi.org/10.1145/3210377.3210411\">10.1145/3210377.3210411</a>.","ama":"Alistarh D-A, Brown TA, Kopinsky J, Li JZ, Nadiradze G. Distributionally linearizable data structures. In: <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i>. ACM Press; 2018:133-142. doi:<a href=\"https://doi.org/10.1145/3210377.3210411\">10.1145/3210377.3210411</a>","ista":"Alistarh D-A, Brown TA, Kopinsky J, Li JZ, Nadiradze G. 2018. Distributionally linearizable data structures. Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18. SPAA: Symposium on Parallelism in Algorithms and Architectures, 133–142.","short":"D.-A. Alistarh, T.A. Brown, J. Kopinsky, J.Z. Li, G. Nadiradze, in:, Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18, ACM Press, 2018, pp. 133–142.","apa":"Alistarh, D.-A., Brown, T. A., Kopinsky, J., Li, J. Z., &#38; Nadiradze, G. (2018). Distributionally linearizable data structures. In <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i> (pp. 133–142). Vienna, Austria: ACM Press. <a href=\"https://doi.org/10.1145/3210377.3210411\">https://doi.org/10.1145/3210377.3210411</a>","ieee":"D.-A. Alistarh, T. A. Brown, J. Kopinsky, J. Z. Li, and G. Nadiradze, “Distributionally linearizable data structures,” in <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i>, Vienna, Austria, 2018, pp. 133–142.","chicago":"Alistarh, Dan-Adrian, Trevor A Brown, Justin Kopinsky, Jerry Z. Li, and Giorgi Nadiradze. “Distributionally Linearizable Data Structures.” In <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i>, 133–42. ACM Press, 2018. <a href=\"https://doi.org/10.1145/3210377.3210411\">https://doi.org/10.1145/3210377.3210411</a>."},"publication_status":"published","date_created":"2019-02-13T10:17:19Z","conference":{"end_date":"2018-07-18","location":"Vienna, Austria","name":"SPAA: Symposium on Parallelism in Algorithms and Architectures","start_date":"2018-07-16"},"department":[{"_id":"DaAl"}],"language":[{"iso":"eng"}],"scopus_import":"1","publisher":"ACM Press","date_published":"2018-07-16T00:00:00Z","month":"07","page":"133-142","publication":"Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA '18","status":"public","type":"conference","day":"16"},{"arxiv":1,"oa":1,"date_updated":"2023-09-19T10:44:49Z","article_processing_charge":"No","_id":"5966","publication_identifier":{"isbn":["9781450357999"]},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","quality_controlled":"1","oa_version":"Preprint","publication_status":"published","citation":{"ista":"Alistarh D-A, Haider SK, Kübler R, Nadiradze G. 2018. The transactional conflict problem. Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18. SPAA: Symposium on Parallelism in Algorithms and Architectures, 383–392.","short":"D.-A. Alistarh, S.K. Haider, R. Kübler, G. Nadiradze, in:, Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18, ACM Press, 2018, pp. 383–392.","ama":"Alistarh D-A, Haider SK, Kübler R, Nadiradze G. The transactional conflict problem. In: <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i>. ACM Press; 2018:383-392. doi:<a href=\"https://doi.org/10.1145/3210377.3210406\">10.1145/3210377.3210406</a>","mla":"Alistarh, Dan-Adrian, et al. “The Transactional Conflict Problem.” <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i>, ACM Press, 2018, pp. 383–92, doi:<a href=\"https://doi.org/10.1145/3210377.3210406\">10.1145/3210377.3210406</a>.","chicago":"Alistarh, Dan-Adrian, Syed Kamran Haider, Raphael Kübler, and Giorgi Nadiradze. “The Transactional Conflict Problem.” In <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i>, 383–92. ACM Press, 2018. <a href=\"https://doi.org/10.1145/3210377.3210406\">https://doi.org/10.1145/3210377.3210406</a>.","ieee":"D.-A. Alistarh, S. K. Haider, R. Kübler, and G. Nadiradze, “The transactional conflict problem,” in <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i>, Vienna, Austria, 2018, pp. 383–392.","apa":"Alistarh, D.-A., Haider, S. K., Kübler, R., &#38; Nadiradze, G. (2018). The transactional conflict problem. In <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i> (pp. 383–392). Vienna, Austria: ACM Press. <a href=\"https://doi.org/10.1145/3210377.3210406\">https://doi.org/10.1145/3210377.3210406</a>"},"abstract":[{"lang":"eng","text":"The transactional conflict problem arises in transactional systems whenever two or more concurrent transactions clash on a data item. While the standard solution to such conflicts is to immediately abort one of the transactions, some practical systems consider the alternative of delaying conflict resolution for a short interval, which may allow one of the transactions to commit. The challenge in the transactional conflict problem is to choose the optimal length of this delay interval so as to minimize the overall running time penalty for the conflicting transactions. In this paper, we propose a family of optimal online algorithms for the transactional conflict problem. Specifically, we consider variants of this problem which arise in different implementations of transactional systems, namely \"requestor wins'' and \"requestor aborts'' implementations: in the former, the recipient of a coherence request is aborted, whereas in the latter, it is the requestor which has to abort. Both strategies are implemented by real systems. We show that the requestor aborts case can be reduced to a classic instance of the ski rental problem, while the requestor wins case leads to a new version of this classical problem, for which we derive optimal deterministic and randomized algorithms. Moreover, we prove that, under a simplified adversarial model, our algorithms are constant-competitive with the offline optimum in terms of throughput. We validate our algorithmic results empirically through a hardware simulation of hardware transactional memory (HTM), showing that our algorithms can lead to non-trivial performance improvements for classic concurrent data structures."}],"author":[{"first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Haider, Syed Kamran","last_name":"Haider","first_name":"Syed Kamran"},{"first_name":"Raphael","last_name":"Kübler","full_name":"Kübler, Raphael"},{"first_name":"Giorgi","last_name":"Nadiradze","full_name":"Nadiradze, Giorgi"}],"isi":1,"main_file_link":[{"url":"https://arxiv.org/abs/1804.00947","open_access":"1"}],"doi":"10.1145/3210377.3210406","year":"2018","title":"The transactional conflict problem","external_id":{"arxiv":["1804.00947"],"isi":["000545269600046"]},"publication":"Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA '18","page":"383-392","day":"16","type":"conference","status":"public","department":[{"_id":"DaAl"}],"conference":{"start_date":"2018-07-16","location":"Vienna, Austria","end_date":"2018-07-18","name":"SPAA: Symposium on Parallelism in Algorithms and Architectures"},"date_created":"2019-02-13T10:26:07Z","month":"07","date_published":"2018-07-16T00:00:00Z","publisher":"ACM Press","scopus_import":"1","language":[{"iso":"eng"}]}]