Non-blocking Patricia tries with replace operations

DOI10.1007/S00446-019-00347-1zbMATH Open1451.68082arXiv1303.3626OpenAlexW2912768656WikidataQ128495089 ScholiaQ128495089MaRDI QIDQ2010602FDOQ2010602

Niloufar Shafiei

Publication date: 27 November 2019

Published in: Distributed Computing (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

shared memorylock-freenon-blockingdictionaryPatricia trieconcurrent data structure

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (1)

• Non-blocking Patricia tries with replace operations

Uses Software

• MiBench
• PATRICIA

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)