Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Optimistic Concurrency with OPTIK
 
conference paper

Optimistic Concurrency with OPTIK

Guerraoui, Rachid  
•
Trigonakis, Vasileios  
2016
Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming - PPoPP '16
21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming - PPoPP '16

We introduce OPTIK, a new practical design pattern for designing and implementing fast and scalable concurrent data structures. OPTIK relies on the commonly-used technique of version numbers for detecting conflicting concurrent operations. We show how to implement the OPTIK pattern using the novel concept of OPTIK locks. These locks enable the use of version numbers for implementing very efficient optimistic concurrent data structures. Existing state-of-the-art lock-based data structures acquire the lock and then check for conflicts. In contrast, with OPTIK locks, we merge the lock acquisition with the detection of conflicting concurrency in a single atomic step, similarly to lock-free algorithms. We illustrate the power of our OPTIK pattern and its implementation by introducing four new algorithms and by optimizing four state-of-the-art algorithms for linked lists, skip lists, hash tables, and queues. Our results show that concurrent data structures built using OPTIK are more scalable than the state of the art.

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.1145/2851141.2851146
Web of Science ID

WOS:000393580200019

Author(s)
Guerraoui, Rachid  
Trigonakis, Vasileios  
Date Issued

2016

Publisher

ACM Press

Publisher place

New York, New York, USA

Published in
Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming - PPoPP '16
Total of pages

12

Subjects

concurrent data structures

•

concurrency

•

scalability

•

multi-core

URL

URL

https://dl.acm.org/citation.cfm?id=2851146

URL

https://github.com/LPD-EPFL/ASCYLIB

URL

http://lpd.epfl.ch/site/optik
Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCL  
Event nameEvent placeEvent date
21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming - PPoPP '16

Barcelona, Spain

12-16 03 2016

Available on Infoscience
March 8, 2016
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/124719
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés