PIM-tree: A Skew-resistant Index for Processing-in-Memory
The performance of today's in-memory indexes is bottlenecked by the memory latency/bandwidth wall. Processing-in-memory (PIM) is an emerging approach that potentially mitigates this bottleneck, by...
PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections
Many modern programming languages are shifting toward a functional style for collection interfaces such as sets, maps, and sequences. Functional interfaces offer many advantages, including being...
Turning Manual Concurrent Memory Reclamation into Automatic Reference Counting
Safe memory reclamation (SMR) schemes are an essential tool for lock-free data structures and concurrent programming. However, manual SMR schemes are notoriously difficult to apply correctly, and...
FliT: A Library for Simple and Efficient Persistent Algorithms
Non-volatile random access memory (NVRAM) offers byte-addressable persistence at speeds comparable to DRAM. However, with caches remaining volatile, automatic cache evictions can reorder updates...
Practically and Theoretically Efficient Garbage Collection for Multiversioning
Multiversioning is widely used in databases, transactional memory, and concurrent data structures. It can be used to support read-only transactions that appear atomic in the presence of concurrent...
Lock-Free Locks Revisited
This paper presents a new and practical approach to lock-free locks based on helping, which allows the user to write code using fine-grained locks, but run it in a lock-free manner. Although...
NVTraverse: In NVRAM Data Structures, the Destination is More Important than the Journey
The recent availability of fast, dense, byte-addressable non-volatile memory has led to increasing interest in the problem of designing and specifying durable data structures that can recover from...
Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable
There has been significant recent interest in parallel graph processing due to the need to quickly analyze the large graphs available today. Many graph codes have been designed for distributed...
Parallel Batch-Dynamic Graph Connectivity
In this paper, we study batch parallel algorithms for the dynamic connectivity problem, a fundamental problem that has received considerable attention in the sequential setting. The most well...
Work-efficient Batch-incremental Minimum Spanning Trees with Applications to the Sliding Window Model
Algorithms for dynamically maintaining minimum spanning trees (MSTs) have received much attention in both the parallel and sequential settings. While previous work has given optimal algorithms for...
Efficient Parallel Self-Adjusting Computation
Self-adjusting computation is an approach for automatically producing dynamic algorithms from static ones. The approach works by tracking control and data dependencies, and propagating changes...
Optimal (Randomized) Parallel Algorithms in the Binary-Forking Model
In this paper we develop optimal algorithms in the binary-forking model for a variety of fundamental problems, including sorting, semisorting, list ranking, tree contraction, range minima, and...
Space and Time Bounded Multiversion Garbage Collection
We present a general technique for garbage collecting old versions for multiversion concurrency control that simultaneously achieves good time and space complexity. Our technique takes only $O(1)$...
Parallelism in Randomized Incremental Algorithms
In this paper we show that many sequential randomized incremental algorithms are in fact parallel. We consider algorithms for several problems including Delaunay triangulation, linear programming,...
LL/SC and Atomic Copy: Constant Time, Space Efficient Implementations using only pointer-width CAS
When designing concurrent algorithms, Load-Link/Store-Conditional (LL/SC) is often the ideal primitive to have because unlike Compare and Swap (CAS), LL/SC is immune to the ABA problem. However,...
Delay-Free Concurrency on Faulty Persistent Memory
Non-volatile memory (NVM) promises persistent main memory that remains correct despite loss of power. This has sparked a line of research into algorithms that can recover from a system crash....
Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs
Non-volatile main memory (NVRAM) technologies provide an attractive set of features for large-scale graph analytics, including byte-addressability, low idle power, and improved memory-density....
Fast and Fair Randomized Wait-Free Locks
We present a randomized approach for wait-free locks with strong bounds on time and fairness in a context in which any process can be arbitrarily delayed. Our approach supports a tryLock operation...