6 papers
Concurrent Balanced Augmented Trees
Evan Wrench, Ajay Singh, Younghun Roh +4
Augmentation makes search trees tremendously more versatile, allowing them to support efficient aggregation queries, order-statistic queries, and range queries in addition to inser…
Sharded Elimination and Combining for Highly-Efficient Concurrent Stacks
Ajay Singh, Nikos Metaxakis, Panagiota Fatourou
We present a new blocking linearizable stack implementation which utilizes sharding and fetch&increment to achieve significantly better performance than all existing concurrent sta…
Recoverable Lock-Free Locks
Hagit Attiya, Panagiota Fatourou, Eleftherios Kosmas +1
This paper presents the first transformation that introduces both lock-freedom and recoverability. Our transformation starts with a lock-based implementation, and provides a recove…
PIPQ: Strict Insert-Optimized Concurrent Priority Queue
Olivia Grimes, Ahmed Hassan, Panagiota Fatourou +1
This paper presents PIPQ, a strict and linearizable concurrent priority queue whose design differs from existing solutions in literature because it focuses on enabling parallelism…
Concurrent Double-Ended Priority Queues
Panagiota Fatourou, Eric Ruppert, Ioannis Xiradakis
This work provides the first concurrent implementation specifically designed for a double-ended priority queue (DEPQ). We do this by describing a general way to add an ExtractMax o…
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…