Write a Blog >>
PPoPP 2021
Sat 27 February - Wed 3 March 2021
Mon 1 Mar 2021 10:30 - 10:45 - Session 1. Concurrency Chair(s): Konstantinos (Kostis) Sagonas

Given a concurrent data structure, we present an approach for efficiently taking snapshots of its constituent CAS objects. More specifically, we support a constant-time operation that returns a snapshot handle. This snapshot handle can later be used to read the value of any base object at the time the snapshot was taken. Reading an earlier version of a base object is wait-free and takes time proportional to the number of successful writes to the object since the snapshot was taken. Importantly, our approach preserves all the time bounds and parallelism of the original data structure.

Our fast, flexible snapshots yield simple, efficient implementations of atomic multi-point queries on a large class of concurrent data structures. For example, in a search tree where child pointers are updated using CAS, once a snapshot is taken, one can atomically search for ranges of keys, find the first key that matches some criteria, or check if a collection of keys are all present, simply by running a standard sequential algorithm on a snapshot of the tree.

To evaluate the performance of our approach, we apply it to three search trees, one balanced and two not. Experiments show that the overhead of supporting snapshots is low across a variety of workloads. Moreover, in almost all cases, range queries on the trees built from our snapshots perform as well as or better than state-of-the-art concurrent data structures that support atomic range queries.

Conference Day
Mon 1 Mar

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

10:00 - 11:00
Session 1. ConcurrencyMain Conference
Chair(s): Konstantinos (Kostis) SagonasUppsala University and National Technical University of Athens
10:00
15m
Talk
Efficient Algorithms for Persistent Transactional Memory
Main Conference
Pedro RamalheteCisco Systems, Andreia CorreiaUniversity of Neuchatel, Switzerland, Pascal FelberUniversity of Neuchâtel
Link to publication
10:15
15m
Talk
Investigating the Semantics of Futures in Transactional Memory Systems
Main Conference
Jingna ZengKTH Royal Institute of Technology, Sweden / IST, ULisboa, Shady IssaINESC-ID, Paolo RomanoINESC-ID / IST, ULisboa, Luis RodriguesINESC-ID, IST, ULisboa, Seif HaridiKTH Royal Institute of Technology, Sweden
Link to publication
10:30
15m
Talk
Constant-Time Snapshots with Applications to Concurrent Data Structures
Main Conference
Yuanhao WeiCarnegie Mellon University, Naama Ben-DavidVMware Research, Guy E. BlellochCarnegie Mellon University, Panagiota FatourouFORTH ICS and University of Crete, Greece, Eric RuppertYork University, Canada, Yihan SunUniversity of California, Riverside
Link to publication
10:45
15m
Talk
Reasoning About Recursive Tree Traversals
Main Conference
Yanjun WangPurdue University, Jinwei LiuBeijing Jiaotong University, Dalin ZhangBeijing Jiaotong University, Xiaokang QiuPurdue University
Link to publication