PPoPP 2023
Sat 25 February - Wed 1 March 2023 Montreal, Canada
Mon 27 Feb 2023 10:20 - 10:40 at Montreal 4 - Session 1: Principles Chair(s): Erez Petrank

Concurrent queues are, arguably, one of the most important data structures in high-load applications, which require them to be extremely fast and scalable. Achieving these properties is non-trivial. The early solutions, such as the classic queue by Michael and Scott, store elements in a concurrent linked list. Reputedly, this design is non-scalable and memory-inefficient. Modern solutions utilize the Fetch-and-Add instruction to improve the algorithm’s scalability and store elements in arrays to reduce the memory pressure. One of the most famous and fast such algorithms is LCRQ. The main disadvantage of its design is that it relies on the atomic CAS2 instruction, which is unavailable in most modern programming languages, such as Java, Kotlin, or Go, let alone some architectures.

This paper presents the LPRQ algorithm, a portable modification of the original LCRQ design that eliminates all CAS2 usages. In contrast, it performs the synchronization utilizing only the standard Compare-and-Swap and Fetch-and-Add atomic instructions. Our experiments show that LPRQ provides the same performance as the classic LCRQ algorithm, outrunning the fastest of the existing solutions that do not use CAS2 by up to 1.6$\times$.

Mon 27 Feb

Displayed time zone: Eastern Time (US & Canada) change

10:00 - 12:00
Session 1: PrinciplesMain Conference at Montreal 4
Chair(s): Erez Petrank Technion
10:00
20m
Talk
Boosting Performance and QoS for Concurrent GPU B+trees by Combining-based Synchronization
Main Conference
Weihua Zhang Fudan University, Chuanlei Zhao Fudan University, Lu Peng Tulane University, Yuzhe Lin Fudan University, Fengzhe Zhang Fudan University, Yunping Lu Fudan University
10:20
20m
Talk
The State-of-the-Art LCRQ Concurrent Queue Algorithm Does NOT Require CAS2
Main Conference
Nikita Koval JetBrains, Raed Romanov Higher School of Economics
10:40
20m
Talk
Provably Good Randomized Strategies for Data Placement in Distributed Key-Value Stores
Main Conference
Zhe Wang Washington University in St. Louis, Jinhao Zhao Washington University in St. Louis, Kunal Agrawal Washington University in St. Louis, USA, Jing Li New Jersey Institute of Technology, He Liu Apple Inc., Meng Xu Apple Inc.
11:00
20m
Talk
2PLSF: Two-Phase Locking with Starvation-Freedom
Main Conference
Pedro Ramalhete Cisco Systems, Andreia Correia University of Neuchâtel, Pascal Felber University of Neuchâtel
11:20
20m
Talk
Provably Fast and Space-Efficient Parallel Biconnectivity
Main Conference
Xiaojun Dong University of California, Riverside, Letong Wang University of California, Riverside, Yan Gu UC Riverside, Yihan Sun University of California, Riverside
11:40
20m
Talk
Practically and Theoretically Efficient Garbage Collection for Multiversioning
Main Conference
Yuanhao Wei Carnegie Mellon University, USA, Guy E. Blelloch Carnegie Mellon University, USA, Panagiota Fatourou FORTH ICS and University of Crete, Greece, Eric Ruppert York University