Support material

Tim Harris (Non-blocking data structures and transactional memory)
Keir Fraser (Practical lock-freedom)
Maurice Herlihy and Nir Shavit(The Art of Multiprocessor Programming)

• Compiler Aided Manual Speculation for High Performance Concurrent Data Structures by Lingxiang Xiang (University of Rochester), Michael L. Scott (University of Rochester)

• NUMA-Aware Reader-Writer Locks by Irina Calciu (Brown University), David Dice (Oracle Labs), Yossi Lev (Oracle Labs), Victor Luchangco (Oracle Labs), Virendra Marathe (Oracle Labs), Nir Shavit (MIT and Tel-Aviv University)

• Fast Concurrent Queues for x86 Processors by Yehuda Afek (Tel Aviv University), Adam Morrison (Tel Aviv University)

• Using Hardware Transactional Memory to Correct and Simplify an Readers-Writer Lock Algorithm by Dave Dice (Oracle Labs), Yossi Lev (Oracle Labs), Yujie Liu (Oracle Labs), Victor Luchangco (Oracle Labs), Mark Moir (Oracle Labs)

• Distributed Merge Trees by Dmitriy Morozov (Lawrence Berkeley National Laboratory), Gunther Weber (Lawrence Berkeley National Laboratory

• Query-Directed Adaptive Heap Cloning For Optimizing Compilers by Yulei Sui, Yue Li, and Jingling Xue (UNSW)

• A practical concurrent binary search tree by Nathan G. Bronson, Jared Casper, Hassan Chafi and Kunle Olukotun (Stanford University)

• Scalable Producer Consumer Pools based on Elimination-Diffracting Trees by Yehuda Afek, Guy Korland, Maria Natanzon, and Nir Shavit (Tel Aviv Univ.)

• Related Materials:

• Diffracting Trees by Nir Shavit (Tel Aviv Univ.), Asaph Zemach (Tel Aviv Univ.)

• Elimination Trees and the Construction of Pools and Stacks by Nir Shavit (MIT and Tel Aviv Univ.), Dan Touitou ( Tel Aviv Univ.)

• Counting Networks and Multi-Processor Coordination by James Aspnes (Carnegie Mellon Univ. ), Maurice Herlihy (Digital Eqipment Company) and Nir Shavit (IBM Almaden Research Center).

• The Art of Multiprocessor Programming , Maurice Herlihy and Nir Shavit

• 7.4 Exponential Backoff

• 11.3 Elimination

• 11.4 The Elimination Backoff Stack

• 12.4 Quiescently Consistent Pools and Counters

• 12.5 Counting Networks

• 12.6 Diffracting Trees

• SNZI: scalable NonZero indicators by Faith Ellen, Yossi Lev, Victor Luchangco and Mark Moir (University of Toronto, Brown University and Sun Microsystems Laboratories)

• Split-Ordered Lists: Lock-Free Extensible Hash Tables by Ori Shalev (Tel Aviv Univ.) and Nir Shavit (Tel Aviv Univ. and Sun Microsystems)

• Practical Lock/Unlock Pairing for Concurrent Programs by Hyoun Kyu Cho (University of Michigan), Yin Wang (Hewlett-Packard Labs), Hongwei Liao (University of Michigan), Terence Kelly (Hewlett-Packard Labs), and Stephane Lafortune and Scott Mahlke (University of Michigan)

• vLock: Lock Virtualization Mechanism for Exploiting Fine-grained Parallelism in Graph Traversal Algorithms by Jie Yan, Guangming Tan, Xiuxia Zhang, Erlin Yao and Ninghui Sun (ICT,CAS)

• Scheduling Parallel Programs by Work Stealing with Private Deques by Umut Acar (Carnegie Mellon University), Arthur Chargueraud (Max Planck Institute for Software Systems), Mike Rainey (Max Planck Institute for Software Systems)

• Dynamic circular work-stealing deque by David Chase (Sun Microsystems Laboratories, Burlington, MA), Yossi Lev (Brown University & Sun Microsystems Laboratories, Burlington, MA)

• A Methodology for Implementing Highly Concurrent Data Structures

• Sketching Concurrent Data Structures

• Understanding the Performance of Concurrent Data Structures on Graphics Processors

• Nonblocking Concurrent Data Structures with Condition Synchronization

• Non-Blocking Algorithms for Concurrent Data Structure

• Runtime Refinement Checking of Concurrent Data Structures

• Laws of Order: Expensive Synchronization in Concurrent Algorithms Cannot be Eliminated

• Revisiting the combining synchronization technique

Flat combining and the synchronization-parallelism tradeoff by D Hendler, I Incze, N Shavit, M Tzafrir, 2010, SPAA'10

Using elimination to implement scalable and lock-free FIFO queues by Mark Moir, Daniel Nussbaum, Ori Shalev, Nir Shavit, 2005, SPAA'05

Universal constructions that ensure disjoint-access parallelism and wait-freedom by Faith Ellen, Panagiota Fatourou, Eleftherios Kosmas, Alessia Milani, Corentin Travers, 2012, PODC'12

quasi-linearizability: relaxed consistency for improved concurrency by Yehuda Afek, Guy Korland, Eitan Yanovsky, 2010, OPODIS'10

Quantitative relaxation of concurrent data structures by Thomas A. Henzinger, Christoph M. Kirsch, Hannes Payer, Ali Sezgin, Ana Sokolova, 2013, POPL'13