conference paper published yes Dan-Adrian Alistarh author 4A899BFC-F248-11E8-B48F-1D18A9856A870000-0003-3650-940X Trevor A Brown author 3569F0A0-F248-11E8-B48F-1D18A9856A87 Justin Kopinsky author Jerry Z. Li author Giorgi Nadiradze author DaAl department SPAA: Symposium on Parallelism in Algorithms and Architectures 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. ACM2018Vienna, Austria eng 9781450357999 1804.01018 00054526960001610.1145/3210377.3210411 133-142 https://research-explorer.ista.ac.at/record/10429 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, 2018, pp. 133–142. 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. 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, 2018. <a href="https://doi.org/10.1145/3210377.3210411">https://doi.org/10.1145/3210377.3210411</a>. 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. 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; 2018:133-142. doi:<a href="https://doi.org/10.1145/3210377.3210411">10.1145/3210377.3210411</a> 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. <a href="https://doi.org/10.1145/3210377.3210411">https://doi.org/10.1145/3210377.3210411</a> 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, 2018, pp. 133–42, doi:<a href="https://doi.org/10.1145/3210377.3210411">10.1145/3210377.3210411</a>. 59652019-02-13T10:17:19Z2026-04-08T07:00:45Z