Reading list for the course Concurrency: Algorithms and Theories (Fall 2023)

Linearizability, progress properties, and impossibility results

• Wojciech Golab, Lisa Higham, Philipp Woelfel. Linearizable Implementations Do Not Suffice for Randomized Distributed Computation. In STOC 2011.
  
• Dan Alistarh, Keren Censor-Hillel, Nir Shavit. Are Lock-Free Concurrent Algorithms Practically Wait-Free? In STOC 2014.
  
• Joseph Izraelevitz, Hammurabi Mendes, Michael L. Scott. Linearizability of Persistent Memory Objects Under a Full-System-Crash Failure Model. In DISC 2016.
  

Concurrent algorithms

• Timothy L. Harris, Keir Fraser, Ian A. Pratt . A Practical Multi-word Compare-and-Swap Operation. In DISC 2002.
  
• Maurice Herlihy, Yossi Lev, Victor Luchangco, Nir Shavit. A Simple Optimistic Skiplist Algorithm. In SIROCCO 2007.
  
• Anastasia Braginsky, Erez Petrank. A Lock-Free B+Tree. In SPAA 2012.
  
• Alex Kogan, Erez Petrank. A Methodology for Creating Fast Wait-Free Data Structures. In PPoPP 2012.
  
• Thomas A. Henzinger, Hannes Payer, Ali Sezgin. Replacing competition with cooperation to achieve scalable lock-free FIFO queues. In SPAA 2013.
  
• Adam Morrison, Yehuda Afek. Fast Concurrent Queues for x86 Processors. In PPoPP 2013.
  
• Yujie Liu, Kunlong Zhang, Michael Spear. Dynamic-Sized Nonblocking Hash Tables. In PODC 2014.
  
• Dana Drachsler, Martin Vechev, Eran Yahav. Practical Concurrent Binary Search Trees via Logical Ordering. In PPoPP 2014.
  
• Mike Dodds, Andreas Haas, Christoph M. Kirsch. A Scalable, Correct Time-Stamped Stack. In POPL 2015.
  
• Chaoran Yang, John Mellor-Crummey. A Wait-free Queue As Fast As Fetch-and-add. In PPoPP 2016.
  
• Gali Sheffi, Guy Golan-Guetta, Erez Petrank. A Scalable Linearizable Multi-Index Table. In ICDCS 2018.
  
• Ruslan Nikolaev. A Scalable, Portable, and Memory-Efficient Lock-Free FIFO Queue. In DISC 2019.
  
• Gal Milman, Alex Kogan, Yossi Lev, Victor Luchangco, Erez Petrank. BQ: A Lock-Free Queue with Batching. In TOPC 2022.
  

General thinking on WMM

• Hans Boehm. Threads Cannot be Implemented as a Library. In PLDI 2005.
  

Java memory model

• Jeremy Manson, William Pugh, Sarita V. Adve. The Java Memory Model. In POPL 2005.
  
• David Aspinall, Jaroslav Ševčík. Formalising Java's Data Race Free Guarantee. In TPHOLs 2007.
  
• Jaroslav Ševčík, David Aspinall. On Validity of Program Transformations in the Java Memory Model. In ECOOP 2008.
  

C/C++11 memory model

• Hans Boehm, Sarita Adve. Foundations of the C++ Concurrency Memory Model. In PLDI 2008.
  
• Mark Batty, Scott Owens, Susmit Sarkar, Peter Sewell, Tjark Weber. Mathematizing C++ Concurrency. In POPL 2011.
  
• Robin Morisset, Pankaj Pawan, Francesco Zappa Nardelli. Compiler testing via a theory of sound optimisations in the C11/C++11 memory model. In PLDI 2013.
  
• Viktor Vafeiadis, Thibaut Balabonski, Soham Chakraborty, Robin Morisset, Francesco Zappa Nardelli. Common compiler optimisations are invalid in the C11 memory model and what we can do about it. In POPL 2015.
  
• Mark Batty, Alastair F. Donaldson, John Wickerson. Overhauling SC atomics in C11 and OpenCL. In POPL 2016.
  
• Jeehoon Kang, Chung-Kil Hur, Ori Lahav, Viktor Vafeiadis, Derek Dreyer. A Promising Semantics for Relaxed-Memory Concurrency. In POPL 2017.
  
• Ori Lahav, Viktor Vafeiadis, Jeehoon Kang, Chung-Kil Hur, Derek Dreyer. Repairing Sequential Consistency in C/C++11. In PLDI 2017.
  

Hongjin Liang
Last modified: 2023-09-01