Enhancing Concurrent Data Structures with Concurrent Iteration Operations: Consistency and Algorithms

Concurrent data structures provide the means to multi-threaded ap-plications to share data. Data structures come with a set of pre-defined operations, specified by the semantics of the data struc-ture. In the literature and in several contemporary commonly used programming environments, the notion of iterations has been in-troduced for collection data structures, as a bulk operation en-hancing the native set of their operations. Iterations in several of these contexts are treated as sequential in nature and may freeze the data structure while operating or provide a variety of consis-tency guarantees when running concurrently with the native oper-ations of the data structures. In this work we study iterations in concurrent data structures with respect to their coexistence with the native operations of the latter and the guarantees that they pro-vide under concurrency. Besides linearizability, we propose a set o