### Skapa referens, olika format (klipp och klistra)

**Harvard**

Nikolakopoulos, Y., Gidenstam, A., Papatriantafilou, M. och Tsigas, P. (2013) *Enhancing Concurrent Data Structures with Concurrent Iteration Operations: Consistency and Algorithms*. Göteborg : Chalmers University of Technology

** BibTeX **

@techreport{

Nikolakopoulos2013,

author={Nikolakopoulos, Yiannis and Gidenstam, Anders and Papatriantafilou, Marina and Tsigas, Philippas},

title={Enhancing Concurrent Data Structures with Concurrent Iteration Operations: Consistency and Algorithms},

abstract={Concurrent data structures provide the means to multi-threaded applications to share data.
Data structures come with a set of predefined operations, specified by the semantics of the data structure.
In the literature and in several contemporary commonly used programming environments,
the notion of iterations has been introduced for collection data structures,
as a bulk operation enhancing 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 consistency guarantees when running concurrently with the native operations 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 provide under concurrency.
Besides linearizability, we propose a set of consistency specifications for such bulk operations, including also concurrency-aware properties by building on Lamport's systematic definitions for registers.
By using queues, fixed-domain sets and composite registers as case-studies of underlying objects, we show a set of constructions of iteration operations, satisfying these properties.
Besides the trade-off between consistency and throughput, we demonstrate the trade-off between the overhead of the bulk operation and possible support (helping) by the native operations of the data structure.
We show a set of algorithms that demonstrate these and study the implications on the efficiency of the implementations.},

publisher={Chalmers University of Technology},

place={Göteborg},

year={2013},

note={12},

}

** RefWorks **

RT Report

SR Print

ID 190338

A1 Nikolakopoulos, Yiannis

A1 Gidenstam, Anders

A1 Papatriantafilou, Marina

A1 Tsigas, Philippas

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

YR 2013

AB Concurrent data structures provide the means to multi-threaded applications to share data.
Data structures come with a set of predefined operations, specified by the semantics of the data structure.
In the literature and in several contemporary commonly used programming environments,
the notion of iterations has been introduced for collection data structures,
as a bulk operation enhancing 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 consistency guarantees when running concurrently with the native operations 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 provide under concurrency.
Besides linearizability, we propose a set of consistency specifications for such bulk operations, including also concurrency-aware properties by building on Lamport's systematic definitions for registers.
By using queues, fixed-domain sets and composite registers as case-studies of underlying objects, we show a set of constructions of iteration operations, satisfying these properties.
Besides the trade-off between consistency and throughput, we demonstrate the trade-off between the overhead of the bulk operation and possible support (helping) by the native operations of the data structure.
We show a set of algorithms that demonstrate these and study the implications on the efficiency of the implementations.

PB Chalmers University of Technology

LA eng

OL 30