The amortized analysis of a non-blocking chromatic tree

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

Jeremy Ko

Publication date: 17 September 2020

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A Randomized Concurrent Algorithm for Disjoint Set Union
• Amortization results for chromatic search trees, with an application to priority queues
• Chromatic binary search trees: A structure for concurrent rebalancing
• Pragmatic primitives for non-blocking data structures
• Randomized Concurrent Set Union and Generalized Wake-Up
• The amortized complexity of non-blocking binary search trees
• A Template for Implementing Fast Lock-free Trees Using HTM

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)