Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A Consistency Framework for Iteration Operations in Concurrent Data Structures
Chalmers University of Technology.
University of Borås, Faculty of Librarianship, Information, Education and IT. (CSL@BS)
Chalmers University of Technology.
Chalmers University of Technology.
2015 (English)In: 2015 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2015, Hyderabad, India, May 25-29, 2015, IEEE Computer Society, 2015, p. 239-248Conference paper, Published paper (Refereed)
Resource type
Text
Abstract [en]

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 iteration has been introduced for collection data structures, as a bulk operation enhancing the native set of operations. Iterations in several of these contexts have been treated as sequential in nature and may provide weak consistency guarantees when running concurrently with the native operations of the data structures. In this work we study iterations in concurrent data structures in the context of concurrency with the native operations and the guarantees that they provide. Besides invariability, we propose a set of consistency specifications for such bulk operations, including also concurrency-aware properties by building on Lamppost's systematic definitions for registers. Furthermore, by using queues and composite registers as case-studies of underlying objects, we provide a set of constructions of iteration operations, satisfying the properties and showing containment relations. Besides the trade-off between consistency and throughput, we point out and study trade-off between the overhead of the bulk operation and possible support (helping) by the native operations of the data structure.

Place, publisher, year, edition, pages
IEEE Computer Society, 2015. p. 239-248
Keywords [en]
concurrency, consistency, data structures, iteration, lock-free
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:hb:diva-5411DOI: 10.1109/IPDPS.2015.84OAI: oai:DiVA.org:hb-5411DiVA, id: diva2:884983
Conference
IEEE International Parallel and Distributed Processing Symposium IPDPS 2015, Hyderabad India, May 25-29, 2015.
Projects
Execution Models for Energy-Efficient Computing Systems - EXCESS (European Union 7th Framework Programme (FP7) under grant agreement 611183)
Funder
EU, FP7, Seventh Framework Programme, 611183Available from: 2015-12-17 Created: 2015-12-17 Last updated: 2018-06-02Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full texthttp://dx.doi.org/10.1109/IPDPS.2015.84
By organisation
Faculty of Librarianship, Information, Education and IT
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 57 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf