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.
@InProceedings{ko:LIPIcs.OPODIS.2018.8, author = {Ko, Jeremy}, title = {{The Amortized Analysis of a Non-blocking Chromatic Tree}}, booktitle = {22nd International Conference on Principles of Distributed Systems (OPODIS 2018)}, pages = {8:1--8:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-098-9}, ISSN = {1868-8969}, year = {2019}, volume = {125}, editor = {Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.8}, URN = {urn:nbn:de:0030-drops-100688}, doi = {10.4230/LIPIcs.OPODIS.2018.8}, annote = {Keywords: amortized analysis, non-blocking, lock-free, balanced binary search trees} }
Feedback for Dagstuhl Publishing