arXiv Open Access 2018

The Amortized Analysis of a Non-blocking Chromatic Tree

Jeremy Ko

Lihat Sumber

Abstrak

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 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.

Topik & Kata Kunci

cs.DC

Penulis (1)

Jeremy Ko

Format Sitasi

APA MLA BibTeX

Ko, J. (2018). The Amortized Analysis of a Non-blocking Chromatic Tree. https://arxiv.org/abs/1811.06383

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2018
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓