The amortized analysis of a non-blocking chromatic tree

DOI10.1016/J.TCS.2020.07.007zbMATH Open1460.68032OpenAlexW3043633409MaRDI QIDQ2202000FDOQ2202000

Authors Jeremy Ko

Publication date 17 September 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

distributed computingconcurrent data structures

Mathematics Subject Classification ID

Data structures (68P05) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: A non-blocking chromatic tree is a type of balanced binary search tree where multiple processes can concurrently perform search and update operations. We prove that a certain implementation has amortized cost $O(dotc+logn)$ for each operation, where $dotc$ is the maximum number of concurrent operations during the execution and $n$ is the maximum number of keys in the tree during the operation. This amortized analysis presents new challenges compared to existing analyses of other non-blocking data structures.

Recommendations

• The amortized complexity of non-blocking binary search trees
• Amortization results for chromatic search trees, with an application to priority queues
• Amortization results for chromatic search trees, with an application to priority queues
• Chromatic binary search trees: A structure for concurrent rebalancing
• Lower bounds on the amortized time complexity of shared objects

Cites work

• scientific article; zbMATH DE number 2006660 (Why is no real title available?)
• A randomized concurrent algorithm for disjoint set union
• A template for implementing fast lock-free trees using HTM
• Amortization results for chromatic search trees, with an application to priority queues
• Chromatic binary search trees: A structure for concurrent rebalancing
• Non-blocking doubly-linked lists with good amortized complexity
• Pragmatic primitives for non-blocking data structures
• Randomized Concurrent Set Union and Generalized Wake-Up
• The amortized complexity of non-blocking binary search trees

Cited in

(2)

• A wait-free queue with polylogarithmic step complexity
• A Wait-free Queue with Polylogarithmic Step Complexity

This page was built for publication: The amortized analysis of a non-blocking chromatic tree

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