1. Linearizable Wait-Free Iteration Operations in Shared Double-Ended Queues.
- Author
-
Fatourou, Panagiota, Nikolakopoulos, Yiannis, and Papatriantafilou, Marina
- Subjects
- *
PARALLEL processing , *ITERATIVE methods (Mathematics) , *QUEUING theory , *SYNCHRONIZATION , *INFORMATION storage & retrieval systems - Abstract
Shared data object implementations that allow non-blocking concurrent operations are useful for in-memory data-processing, especially when they support consistent bulk operations like iterations. We propose an algorithmic implementation for concurrent iterators on shared double-ended queues (deques), building on and complementing a known lock-free deque implementation by M. Michael. The proposed construction is linearizable and wait-free. Moreover, it is read-only, so it does not execute expensive synchronization primitives and it does not interfere with update operations. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF