2014/08/08 by Niloufar Shafiei, Shafiei, Niloufar · 3 voices · 2 citations
Computer Science · #Amortized analysis #Blocking (statistics) #Computer network #Computer science #Cryptography and Data Security #Data structure #Distributed systems and fault tolerance #Optimization and Search Problems #Programming language #cs.DC
paper · pdf · doi:10.48550/arxiv.1408.1935
published in arXiv (Cornell University) (Cornell University)
arxiv created 2014/08/08 · openalex publication_date 2014/08/08 · arxiv updated 2014/08/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a new non-blocking doubly-linked list implementation for an asynchronous shared-memory system. It is the first such implementation for which an upper bound on amortized time complexity has been proved. In our implementation, operations access the list via cursors. Each cursor is associated with an item in the list and is local to a process. The implementation supports two update operations, insertBefore and delete, and two move operations, moveRight and moveLeft. An insertBefore(c, x) operation inserts an item x into the list immediately before the cursor c's location. A delete(c) operation removes the item at the cursor c's location and sets the cursor to the next item in the list. The move operations move the cursor one position to the right or left. The update operations use single-word Compare&Swap instructions. The move operations only read shared memory and never change the state of the data structure. If all update operations modify different parts of the list, they run completely concurrently. Let cp(op) be the maximum number of active cursors at any one time during the operation op. The amortized complexity of each update operation op is O(cp(op)) and each move operation is O(1). We have written a detailed correctness proof and amortized analysis of our implementation.