Non-blocking Patricia Tries with Replace Operations

Abstract

This paper presents a non-blocking Patricia trie implementation for an asynchronous shared-memory system using Compare&Swap. The trie implements a linearizable set and supports three update operations: insert adds an element, delete removes an element and replace replaces one element by another. The replace operation is interesting because it changes two different locations of tree atomically. If all update operations modify different parts of the trie, they run completely concurrently. The implementation also supports a wait-free find operation, which only reads shared memory and never changes the data structure. Empirically, we compare our algorithms to some existing set implementations.

To appear in the 33rd IEEE International Conference on Distributed Computing Systems (ICDCS 2013)

References in corpus (1)

• Non-blocking Patricia Tries with Replace Operations

Cited by in corpus (7)

• Non-blocking Patricia Tries with Replace Operations
• Techniques for Constructing Efficient Lock-free Data Structures
• Non-Blocking Doubly-Linked Lists with Good Amortized Complexity
• Jiffy: A Lock-free Skip List with Batch Updates and Snapshots
• Pragmatic Primitives for Non-blocking Data Structures
• NBR: Neutralization Based Reclamation
• Quadboost: A Scalable Concurrent Quadtree