PPoPP 2016
Sat 12 - Wed 16 March 2016 Barcelona, Spain
Tue 15 Mar 2016 11:35 - 12:00 at Mallorca+Menorca - Optimistic concurrency Chair(s): Milind Chabbi

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.

Tue 15 Mar

Displayed time zone: Belfast change

11:35 - 12:50
Optimistic concurrencyMain conference at Mallorca+Menorca
Chair(s): Milind Chabbi Rice University
11:35
25m
Talk
Optimistic Concurrency with OPTIKArtifact Evaluation
Main conference
Rachid Guerraoui EPFL, Switzerland, Vasileios Trigonakis EPFL
Link to publication DOI
12:00
25m
Talk
Refined Transactional Lock Elision
Main conference
Dave Dice Oracle Labs, Alex Kogan Oracle Labs, Yossi Lev Oracle Labs
Link to publication DOI
12:25
25m
Talk
Drinking from Both Glasses: Combining Pessimistic and Optimistic Tracking of Cross-Thread DependencesArtifact Evaluation
Main conference
Man Cao Ohio State University, USA, Minjia Zhang Ohio State University, USA, Aritra Sengupta Ohio State University, Michael D. Bond Ohio State University
Link to publication DOI