Non-blocking Patricia tries with replace operations

DOI10.1007/S00446-019-00347-1MaRDI QIDQ2010602zbMATH OpenOpenAlexWikidataFDO

Authors Niloufar Shafiei

Publication date 27 November 2019

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1303.3626

zbMATH Keywords

shared memorylock-freenon-blockingdictionaryPatricia trieconcurrent data structure

Mathematics Subject Classification ID

Data structures (68P05) Distributed systems (68M14)

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.

Recommendations

• Pragmatic primitives for non-blocking data structures
• New trie data structures which support very fast search operations
• The SkipTrie, low-depth concurrent search without rebalancing
• scientific article; zbMATH DE number 2006660
• The amortized complexity of non-blocking binary search trees

Cites work

• CBTree: a practical concurrent self-adjusting search tree
• Efficient lock-free binary search trees
• Non-blocking Patricia tries with replace operations
• Performance of memory reclamation for lockless synchronization
• Pragmatic primitives for non-blocking data structures
• Reuse, don't recycle: transforming lock-free algorithms that throw away descriptors
• SP-GiST: An extensible database index for supporting space partitioning trees
• Software transactional memory
• Supporting Lock-Free Composition of Concurrent Data Objects: Moving Data between Containers
• The SkipTrie, low-depth concurrent search without rebalancing
• Universal constructions that ensure disjoint-access parallelism and wait-freedom

Cited in

(1)

• Non-blocking Patricia tries with replace operations

Describes a project that uses

Uses Software

• PATRICIA
• MiBench

This page was built for publication: Non-blocking Patricia tries with replace operations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2010602)