3 citations · 6 across the 8 of their papers we have counts for
9 papers
A Wait-free Queue with Polylogarithmic Step Complexity
Hossein Naderibeni, Eric Ruppert
We present a novel linearizable wait-free queue implementation using single-word CAS instructions. Previous lock-free queue implementations from CAS all have amortized step complex…
When Is Recoverable Consensus Harder Than Consensus?
Carole Delporte-Gallet, Panagiota Fatourou, Hugues Fauconnier +1
We study the ability of different shared object types to solve recoverable consensus using non-volatile shared memory in a system with crashes and recoveries. In particular, we com…
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…
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…
Persistent Non-Blocking Binary Search Trees Supporting Wait-Free Range Queries
Panagiota Fatourou, Eric Ruppert
This paper presents the first implementation of a search tree data structure in an asynchronous shared-memory system that provides a wait-free algorithm for executing range queries…
Pragmatic Primitives for Non-blocking Data Structures
Trevor Brown, Faith Ellen, Eric Ruppert
We define a new set of primitive operations that greatly simplify the implementation of non-blocking data structures in asynchronous shared-memory systems. The new operations opera…