2026-07-20T11:57:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10068 2024-03-06T10:45:32Z ddc:004 open_access

The Amortized Analysis of a Non-blocking Chromatic Tree Ko, Jeremy amortized analysis non-blocking lock-free balanced binary search trees 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(dot{c} + log n) for each operation, where dot{c} is the maximum number of concurrent operations at any point 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jeremy Ko 2019 Is Part Of LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2018.8 urn:nbn:de:0030-drops-100688 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.8 eng https://creativecommons.org/licenses/by/3.0/legalcode