2020/01/02 by Aleksandar Prokopec, Trevor Brown, Prokopec, Aleksandar +3
Computer Science · #Advanced Data Storage Technologies #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #Distributed systems and fault tolerance #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2001.00413
openalex publication_date 2020/01/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We start by summarizing the recently proposed implementation of the first non-blocking concurrent interpolation search tree (C-IST) data structure. We then analyze the individual operations of the C-IST, and show that they are correct and linearizable. We furthermore show that lookup (and several other non-destructive operations) are wait-free, and that the insert and delete operations are lock-free. We continue by showing that the C-IST has the following properties. For arbitrary key distributions, this data structure ensures worst-case O(log n + p) amortized time for search, insertion and deletion traversals. When the input key distributions are smooth, lookups run in expected O(log log n + p) time, and insertion and deletion run in expected amortized O(log log n + p) time, where p is a bound on the number of threads. Finally, we present an extended experimental evaluation of the non-blocking IST performance.