Papers related to dynamic program analysis for reliable concurrency

Memory Models and Sequential Consistency

The Java 5 Memory Model fixed a lot of issues in the previous Java memory model(s). In particular, race-free programs are guaranteed to execute with sequential consistency semantics, and volatile variable accesses induce happens-before relationships. Recent projects (DRFx and concurrency exceptions) ensure that a program that violates sequential consistency will throw an error. Adversarial Memory identifies harmful races by exploring the range of behaviors possible for data races under a weak memory model.

The Java Memory Model
Jeremy Manson, William Pugh, Sarita V. Adve
POPL 2005

Memory Models: A Case for Rethinking Parallel Languages and Hardware
Sarita V. Adve, Hans-J. Boehm
CACM 2010

Adversarial Memory For Detecting Destructive Races
Cormac Flanagan, Stephen N. Freund
PLDI 2010

DRFx: A Simple and Efficient Memory Model for Concurrent Programming Languages
Daniel Marino, Abhayendra Singh, Todd Millstein, Madanlal Musuvathi, Satish Narayanasamy
PLDI 2010

Conflict Exceptions: Simplifying Concurrent Language Semantics with Precise Hardware Exceptions for Data-Races
Brandon Lucia, Luis Ceze, Karin Strauss, Shaz Qadeer, Hans-J. Boehm
ISCA 2010

Data Races

Recent papers on dynamic, vector clock-based race detection. FastTrack improves the time and space overhead of (dynamically) sound and precise race detection. Pacer and LiteRace are sampling-based race detection approaches.

FastTrack: Efficient and Precise Dynamic Race Detection
Cormac Flanagan, Stephen N. Freund
PLDI 2009

Goldilocks: A Race and Transaction-Aware Java Runtime
Tayfun Elmas, Serdar Tasiran, Shaz Qadeer
PLDI 2007

Detecting and Surviving Data Races using Complementary Schedules
Kaushik Veeraraghavan, Peter M. Chen, Jason Flinn, Satish Narayanasamy
SOSP 2011

Effective Data-Race Detection for the Kernel
John Erickson, Madanlal Musuvathi, Sebastian Burckhardt, Kirk Olynyk
OSDI 2010

Eraser: A Dynamic Data Race Detector for Multithreaded Programs
Stefan Savage, Michael Burrows, Greg Nelson, Patrick Sobalvarro, Thomas Anderson
SOSP and TOCS 1997

Pacer: Proportional Detection of Data Races
Michael D. Bond, Katherine E. Coons, Kathryn S. McKinley
PLDI 2010

LiteRace: Effective Sampling for Lightweight Data-Race Detection
Daniel Marino, Madanlal Musuvathi, Satish Narayanasamy
PLDI 2009

Multithreaded Record and Replay

DoublePlay: Parallelizing Sequential Logging and Replay
Kaushik Veeraraghavan, Dongyoon Lee, Benjamin Wester, Jessica Ouyang, Peter M. Chen, Jason Flinn, Satish Narayanasamy

Respec: Efficient Online Multiprocessor Replay via Speculation and External Determinism
Dongyoon Lee, Benjamin Wester, Kaushik Veeraraghavan, Satish Narayanasamy, Peter M. Chen, Jason Flinn

PRES: Probabilistic Replay with Execution Sketching on Multiprocessors
Soyeon Park, Weiwei Xiong, Zuoning Yin, Rini Kaushik, Kyu H. Lee, Shan Lu, Yuanyuan Zhou
SOSP 2009

A Hardware Memory Race Recorder for Deterministic Replay
Min Xu, Rastislav Bodik, Mark D. Hill
IEEE Micro 2007

Dynamic Analysis of Concurrent Programs

ParaLog: Enabling and Accelerating Online Parallel Monitoring of Multithreaded Applications
Evangelos Vlachos, Michelle Goodstein, Michael Kozuch, Shimin Chen, Babak Falsafi, Phillip B. Gibbons, Todd C. Mowry

Butterfly Analysis: Adapting Dataflow Analysis to Dynamic Parallel Monitoring
Michelle L. Goodstein, Evangelos Vlachos, Shimin Chen, Phillip B. Gibbons, Michael Kozuch, Todd C. Mowry

Atomicity, Serializability, Isolation, and Linearizability

Velodrome is dynamically sound and precise. It detects cycles in the dynamic dependence graph between regions that are supposed to be atomic. On the other hand, I think Atomizer is not precise, i.e., it can report false positives, but it can also report atomicity violations that did not occur on the current run but could have occurred on some run.

Velodrome: A Sound and Complete Dynamic Atomicity Checker for Multithreaded Programs
Cormac Flanagan, Stephen N. Freund, Jaeheon Yi
PLDI 2008

Atomizer: A Dynamic Atomicity Checker for Multithreaded Programs
Cormac Flanagan, Stephen N. Freund
POPL 2004, SCP 2008

A Serializability Violation Detector for Shared-Memory Server Programs
Min Xu, Rastislav Bodik, Mark D. Hill
PLDI 2005

ISOLATOR: Dynamically Ensuring Isolation in Concurrent Programs
Sriram Rajamani, G. Ramalingam, Venkatesh Prasad Ranganath, Kapil Vaswani

Line-Up: A Complete and Automatic Linearizability Checker
Sebastian Burckhardt, Chris Dern, Madanlal Musuvathi, Roy Tan
PLDI 2010

Transactional Memory

Transactional Memory, 2nd edition (sent to you via e-mail with permission from publisher)
Tim Harris, James Larus, Ravi Rajwar
Morgan & Claypool Publishers, 2010

Using Hardware Memory Protection to Build a High-Performance, Strongly Atomic Hybrid Transactional Memory
Lee Baugh, Naveen Neelakantam, Craig Zilles
ISCA 2008

Enforcing Isolation and Ordering in STM
Tatiana Shpeisman, Vijay Menon, Ali-Reza Adl-Tabatabai, Steven Balensiefer, Dan Grossman, Richard L. Hudson, Katherine F. Moore, Bratin Saha
PLDI 2007

Programming Models

Effects for Cooperable and Serializable Threads
Jaeheon Yi, Cormac Flanagan
TLDI 2010

Parallel Programming Must Be Deterministic by Default
Robert L. Bocchino Jr., Vikram S. Adve, Sarita V. Adve, Marc Snir
HotPar 2009

Composable Specifications for Structured Shared-Memory Communication
Benjamin P. Wood, Adrian Sampson, Luis Ceze, Dan Grossman

Studies, Opinions, Infrastructure

Learning from Mistakes: A Comprehensive Study on Real World Concurrency Bug Characteristics
Shan Lu, Soyeon Park, Eunsoo Seo, Yuanyuan Zhou

A Case for System Support for Concurrency Exceptions
Luis Ceze, Joseph Devietti, Brandon Lucia, Shaz Qadeer
HotPar 2009

The RoadRunner Dynamic Analysis Framework for Concurrent Programs
Cormac Flanagan, Stephen N. Freund
PASTE 2010

Deterministic Parallel Java paper

Invariant-Based Bug Detection

Invariant-based bug detection (also called anomaly-based bug detection) finds program behaviors that are well-correlated with errors, by observing both failing and correct executions. The tricky part is choosing the right features as program behavior.

Finding Concurrency Bugs with Context-Aware Communication Graphs
Brandon Lucia, Luis Ceze
MICRO 2009

Cooperative Crug Isolation
Aditya Thakur, Rathijit Sen, Ben Liblit, Shan Lu
WODA 2009

Instrumentation and Sampling Strategies for Cooperative Concurrency Bug Isolation
Guoliang Jin, Aditya Thakur, Ben Liblit, Shan Lu

Do I Use the Wrong Definition? DefUse: Definition-Use Invariants for Detecting Concurrency and Sequential Bugs
Yao Shi, Soyeon Park, Zuoning Yin, Shan Lu, Yuanyuan Zhou, Wenguang Chen, Weimin Zheng

AVIO: Detecting Atomicity Violations via Access-Interleaving Invariants
Shan Lu, Joe Tucek, Feng Qin, Yuanyuan Zhou

ColorSafe: Architectural Support for Debugging and Dynamically Avoiding Multi-variable Atomicity Violations
Brandon Lucia, Luis Ceze, Karin Strauss
ISCA 2010

Exposing Concurrency Bugs

CTrigger: Exposing Atomicity Violation Bugs from Their Hiding Places
Soyeon Park, Shan Lu, Yuanyuan Zhou

A Randomized Dynamic Program Analysis Technique for Detecting Real Deadlocks
Pallavi Joshi, Chang-Seo Park, Koushik Sen, Mayur Naik
PLDI 2009

An Effective Dynamic Analysis for Detecting Generalized Deadlocks
Pallavi Joshi, Mayur Naik, Koushik Sen, David Gay
FSE 2010

PENELOPE: Weaving Threads to Expose Atomicity Violations
Francesco Sorrentino, Azadeh Farzan, P. Madhusudan
FSE 2010

Preemption Bounding

Iterative Context Bounding for Systematic Testing of Multithreaded Programs
Madan Musuvathi, Shaz Qadeer
PLDI 2007

A Trace Simplification Technique for Effective Debugging of Concurrent Programs
Nicholas Jalbert, Koushik Sen
FSE 2010

Tolerating Bugs

By controlling thread interleavings, concurrency bugs such as atomicity violations and deadlocks can be avoided altogether.

Atom-Aid: Detecting and Surviving Atomicity Violations
Brandon Lucia, Joseph Devietti, Karin Strauss, Luis Ceze
ISCA 2008

A Case for an Interleaving Constrained Shared-Memory Multi-Processor
Jie Yu, Satish Narayanasamy
ISCA 2009

Grace: Safe Multithreaded Programming for C/C++
Emery D. Berger, Ting Yang, Tongping Liu, Gene Novark

Gadara: Dynamic Deadlock Avoidance for Multithreaded Programs
Yin Wang, Terence Kelly, Manjunath Kudlur, Stephane Lafortune, Scott Mahlke
OSDI 2008

Deterministic Multithreading & Replay

Kendo: Efficient Deterministic Multithreading in Software
Marek Olszewski, Jason Ansel, Saman Amarasinghe

Dthreads: Efficient Deterministic Multithreading
Tongping Liu, Charlie Curtsinger, Emery D. Berger
SOSP 2011

DMP: Deterministic Shared Memory Multiprocessing
Joseph Devietti, Brandon Lucia, Luis Ceze, Mark Oskin

CoreDet: A Compiler and Runtime System for Deterministic Multithreaded Execution
Tom Bergan, Owen Anderson, Joseph Devietti, Luis Ceze, Dan Grossman