Constant-Time Snapshots with Applications to Concurrent Data Structures
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.
Mon 1 MarDisplayed time zone: Eastern Time (US & Canada) change
10:00 - 11:00
|Efficient Algorithms for Persistent Transactional Memory|
Pedro Ramalhete Cisco Systems, Andreia Correia University of Neuchatel, Switzerland, Pascal Felber University of NeuchâtelLink to publication
|Investigating the Semantics of Futures in Transactional Memory Systems|
Jingna Zeng KTH Royal Institute of Technology, Sweden / IST, ULisboa, Shady Issa INESC-ID, Paolo Romano INESC-ID / IST, ULisboa, Luis Rodrigues INESC-ID, IST, ULisboa, Seif Haridi KTH Royal Institute of Technology, SwedenLink to publication
|Constant-Time Snapshots with Applications to Concurrent Data Structures|
Yuanhao Wei Carnegie Mellon University, Naama Ben-David VMware Research, Guy E. Blelloch Carnegie Mellon University, Panagiota Fatourou FORTH ICS and University of Crete, Greece, Eric Ruppert York University, Canada, Yihan Sun University of California, RiversideLink to publication
|Reasoning About Recursive Tree Traversals|
Yanjun Wang Purdue University, Jinwei Liu Beijing Jiaotong University, Dalin Zhang Beijing Jiaotong University, Xiaokang Qiu Purdue UniversityLink to publication