Write a Blog >>
PPoPP 2022
Sat 2 - Wed 6 April 2022
Wed 6 Apr 2022 12:00 - 12:15 - Session 8 Chair(s): Naama Ben-David

We present bundled references, a new building block to provide linearizable range query operations for highly concurrent lock-based linked data structures. Bundled references allow range queries to traverse a path through the data structure that is consistent with the target atomic snapshot. We implement our technique into three data structures: a linked list, skip list, and a binary search tree. Our evaluation reveals that in mixed workloads, our design can improve upon the state-of-the-art techniques by 1.2x-1.8x for a skip list and 1.3x-3.7x for a binary search tree. We also integrate our bundled data structure into the DBx1000 in-memory database, yielding up to 40% gain over the same competitors.

Wed 6 Apr

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

12:00 - 13:15
Session 8Main Conference
Chair(s): Naama Ben-David VMware
12:00
15m
Talk
Bundling Linked Data Structures for Linearizable Range Queries
Main Conference
Jacob Nelson Lehigh University, Ahmed Hassan Lehigh University, Roberto Palmieri Lehigh University
12:15
15m
Talk
Elimination (a,b)-trees with fast, durable updates
Main Conference
Anubhav Srivastava University of Waterloo, Trevor Brown University of Waterloo
12:30
15m
Talk
Jiffy: A Lock-free Skip List with Batch Updates and Snapshots
Main Conference
Tadeusz Kobus Poznan University of Technology, Maciej Kokociński Poznan University of Technology, Paweł T. Wojciechowski Poznan University of Technology
12:45
15m
Talk
Multi-Queues Can Be State-of-the-Art Priority Schedulers
Main Conference
Anastasiia Postnikova ITMO University, Nikita Koval JetBrains, Giorgi Nadiradze IST Austria, Dan Alistarh IST Austria
13:00
15m
Talk
PathCAS: An Efficient Middle Ground for Concurrent Search Data Structures
Main Conference
Trevor Brown University of Waterloo, William Sigouin University of Waterloo, Dan Alistarh IST Austria