6 citations · 22 across the 15 of their papers we have counts for
17 papers
Upper and Lower Bounds on the Space Complexity of Multi-word Single-Writer Registers
Yuanhao Wei, Yousof Yavari
We prove matching upper and lower bounds on the space complexity of simulating a large shared register using smaller shared registers. We focus on the case where both the simulated…
CleANN: Efficient Full Dynamism in Graph-based Approximate Nearest Neighbor Search
Ziyu Zhang, Yuanhao Wei, Joshua Engels +1
Approximate nearest neighbor search (ANNS) has become a quintessential algorithmic problem for various other foundational data tasks for AI workloads. Graph-based ANNS indexes have…
Aggregating Funnels for Faster Fetch&Add and Queues
Younghun Roh, Yuanhao Wei, Eric Ruppert +3
Many concurrent algorithms require processes to perform fetch-and-add operations on a single memory location, which can be a hot spot of contention. We present a novel algorithm ca…
Practically and Theoretically Efficient Garbage Collection for Multiversioning
Yuanhao Wei, Guy E. Blelloch, Panagiota Fatourou +1
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 presen…
Survey of Persistent Memory Correctness Conditions
Naama Ben-David, Michal Friedman, Yuanhao Wei
The study of concurrent persistent programs has seen a surge of activity in recent years due to the introduction of non-volatile random access memories (NVRAM), yielding many model…
Turning Manual Concurrent Memory Reclamation into Automatic Reference Counting
Daniel Anderson, Guy E. Blelloch, Yuanhao Wei
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…
Lock-Free Locks Revisited
Naama Ben-David, Guy E. Blelloch, Yuanhao Wei
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…
FliT: A Library for Simple and Efficient Persistent Algorithms
Yuanhao Wei, Naama Ben-David, Michal Friedman +2
Non-volatile random access memory (NVRAM) offers byte-addressable persistence at speeds comparable to DRAM. However, with caches remaining volatile, automatic cache evictions can r…
Space and Time Bounded Multiversion Garbage Collection
Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou +3
We present a general technique for garbage collecting old versions for multiversion concurrency control that simultaneously achieves good time and space complexity. Our technique t…
Concurrent Fixed-Size Allocation and Free in Constant Time
Guy E. Blelloch, Yuanhao Wei
Our goal is to efficiently solve the dynamic memory allocation problem in a concurrent setting where processes run asynchronously. On processes, we can support allocation and f…
Constant-Time Snapshots with Applications to Concurrent Data Structures
Yuanhao Wei, Naama Ben-David, Guy E. Blelloch +3
We present an approach for efficiently taking snapshots of the state of a collection of CAS objects. Taking a snapshot allows later operations to read the value that each CAS objec…
NVTraverse: In NVRAM Data Structures, the Destination is More Important than the Journey
Michal Friedman, Naama Ben-David, Yuanhao Wei +2
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…
Concurrent Reference Counting and Resource Management in Wait-free Constant Time
Guy E. Blelloch, Yuanhao Wei
A common problem when implementing concurrent programs is efficiently protecting against unsafe races between processes reading and then using a resource (e.g., memory blocks, file…
LL/SC and Atomic Copy: Constant Time, Space Efficient Implementations using only pointer-width CAS
Guy E. Blelloch, Yuanhao Wei
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 pro…
Space Complexity of Implementing Large Shared Registers
Yuanhao Wei
We prove two new space lower bounds for the problem of implementing a large shared register using smaller physical shared registers. We focus on the case where both the implemented…
Delay-Free Concurrency on Faulty Persistent Memory
Naama Ben-David, Guy E. Blelloch, Michal Friedman +1
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 sy…
Multiversion Concurrency with Bounded Delay and Precise Garbage Collection
Naama Ben-David, Guy E. Blelloch, Yihan Sun +1
In this paper we are interested in bounding the number of instructions taken to process transactions. The main result is a multiversion transactional system that supports constant…