CSE 914, Fall 2008

Readings and References

 

Introduction to threads and synchronization issues:

  The Problem with Threads, by Edward A. Lee.  Computer, Vol. 29, Issue 5, IEEE Computer Society Press, May 2006.  Publisher Site.

   A taxonomy of correctness criteria in database applications, by Krithi Ramamritham, Panos K. Chrysanthis.  The VLDB Journal - The International Journal on Very Large Data Bases, Vol. 5, Issue 1, January 1996.  pdf(218.49 KB)

  The Java memory model, by Jeremy Manson, William Pugh, Sarita V. Adve.  POPL'05: Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, ACM, January 2005, pp. 378 - 391.  Pdf (261 KB)

 

Data Races

  Eraser: A Dynamic Data Race Detector for Multithreaded Programs, by Stefan Savage, Michael Burrows, Greg Nelson, Patrick Sobalvarro, and Thomas Anderson.  Transactions on Computer Systems, vol. 15, no. 4, pages 391-411. Pdf(136 KB)

  Hybrid dynamic data race detection, by Robert O'Callahan, Jong-Deok Choi.  PPoPP '03: Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, ACM, June 2003.  pdf(158.47 KB)

  Effective static race detection for Java, by Mayur Naik, Alex Aiken, John Whaley.  PLDI '06: Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, ACM, June 2006.  pdf(195.21 KB)

  High-Level Data Races, by Cyrille Artho, Klaus Havelund, and Armin Biere.  Journal on Software Testing, Verification & Reliability (STVR).  http://ase.arc.nasa.gov/docs/../papers/VVEIS03/vc1.ps.

  Dynamic detection of atomic-set-serializability violations, by Christian Hammer, Julian Dolby, Mandana Vaziri, Frank Tip.  ICSE '08: Proceedings of the 30th international conference on Software engineering, ACM, May 2008.  pdf(349.88 KB).

 

Software Transactional Memory

  Transactional Memory, by James Larus and Christos Kozyrakis.  Communications of the ACM, Vol. 51, Issue 7, July 2008, pp. 80 - 88.  Pdf (410 KB)

  On the correctness of transactional memory, by Rachid Guerraoui, Michal Kapalka.  PPoPP '08: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, ACM, February 2008.  pdf(242.03 KB)

  Software transactional memory for dynamic-sized data structures, by Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer, III.  PODC '03: Proceedings of the twenty-second annual symposium on Principles of distributed computing, ACM, July 2003.  pdf(1.11 MB)

  Design tradeoffs in modern software transactional memory systems, by Virendra J. Marathe, William N. Scherer, and Michael L. Scott.  LCR '04: Proceedings of the 7th workshop on Workshop on languages, compilers, and run-time support for scalable systems, ACM, October 2004.  pdf(158.62 KB)

  Enforcing isolation and ordering in STM, by Tatiana Shpeisman, Vijay Menon, Ali-Reza Adl-Tabatabai, Steven Balensiefer, Dan Grossman, Richard L. Hudson, Katherine F. Moore, Bratin Saha.  PLDI '07: Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, ACM, June 2007.  pdf(257.39 KB)

 

Nesting in STM

  Open nesting in software transactional memory, by Yang Ni, Vijay S. Menon, Ali-Reza Adl-Tabatabai, Antony L. Hosking, Richard L. Hudson, J. Eliot B. Moss, Bratin Saha, Tatiana Shpeisman.  PPoPP '07: Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, ACM, March 2007.  pdf(227.65 KB)

  Supporting nested transactional memory in logTM, by Michelle J. Moravan, Jayaram Bobba, Kevin E. Moore, Luke Yen, Mark D. Hill, Ben Liblit, Michael M. Swift, David A. Wood.  ACM SIGOPS Operating Systems Review, Vol. 40, Issue 5, October 2006.  pdf(239.03 KB)

  Safer open-nested transactions through ownership, by Kunal Agrawal, I-Ting A. Lee, Jim Sukha.  PPoPP '08: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, ACM, February 2008.  pdf(200.58 KB)

  Nested Transactional Memory: Model and Preliminary Architecture Sketches, J. E. Moss and A. L. Hosking.  Science of Computer Programming, Volume 63 , Issue 2  (December 2006), Pages: 186 - 201

 

Beyond STM

  Transactional collection classes, by Brian D. Carlstrom, Austen McDonald, Michael Carbin, Christos Kozyrakis, Kunle Olukotun.  PPoPP '07: Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, ACM, March 2007.  pdf(256.98 KB)

  Transactions with isolation and cooperation, by Yannis Smaragdakis, Anthony Kay, Reimer Behrends, Michal Young.  OoPSLA '07: Proceedings of the 22nd annual ACM SIGPLAN conference on Object oriented programming systems and applications, ACM, October 2007.  pdf(252.95 KB)

  Advanced contention management for dynamic software transactional memory, by William N. Scherer, III, and Michael L. Scott.  PODC '05: Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, ACM, July 2005.  Full text available: pdf(480.97 KB)

  Adaptive Locks: Combining Transactions and Locks for Efficient Concurrency, by Takayuki Usui, Yannis Smaragdakis and Reimer Behrends, Technical Report, Computer Science Department, University of Oregon, Eugene, OR.  

 

Language solutions

  Ownership types for safe programming: preventing data races and deadlocks, by Chandrasekhar Boyapati, Robert Lee, Martin Rinard.  OOPSLA '02: Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, ACM, November 2002.  pdf(459.57 KB)

  Language support for lightweight transactions, by Tim Harris, Keir Fraser.  OOPSLA '03: Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, ACM, October 2003.  pdf(224.15 KB)

  Checkpoints and continuations instead of nested transactions, by Eric Koskinen, Maurice Herlihy.  SPAA '08: Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, ACM, June 1998.  pdf(412.97 KB)

  SCOOP: Concurrent Programming Made Easy, by Piotr Nienaltowski, Volkan Arsian, and Bertrand Meyer.  Draft.

 

  

Related papers (which we probably will not get to): 

  Systematic Concurrent Object Oriented Programming, by Bertrand Meyer.  Communications of the ACM, September 1993, Vol.36, No.9.

  Hybrid Transactional Memory, by Peter Damron, Alexandra Fedorova, Yossi Lev, Victor Luchangco, Mark Moir, Daniel Nussbaum.  ACM SIGPLAN Notices, Vol. 41, Issue 11, November 2006.  pdf(195.89 KB)

  MapReduce: simplified data processing on large clusters, by Jeffrey Dean, Sanjay Ghemawat.  OSDI'04: Symposium on operating system design and implementation, December 2004.  (Shorter version appears in Communications of the ACM, Vol. 51, Issue 1, January 2008.  pdf(235.24 KB))

  Abstraction in recovery management, by J. Eliot B. Moss, Nancy D. Griffeth and Marc H. Graham.  ACM SIGMOD Record, Vol. 15, Issue 2, ACM, 1986.  Full text available: pdf(1.41 MB).

  Toward a theory of transactional contention managers, by Rachid Guerraoui, Maurice Herlihy, and Bastian Pochon.  PODC '05: Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, ACM, July 2005.  Full text available: pdf(163.56 KB)

  Memory models for open-nested transactions, by Kunal Agrawal, Charles E. Leiserson, Jim Sukha.  MSPC '06: Proceedings of the 2006 workshop on Memory system performance and correctness, ACM, October 2006.  pdf(713.14 KB)

  A Classification of Concurrency Failures in Java Components, by B. Long and P. Strooper.  Proceedings of the International Parallel and Distributed Processing Symposium,IEEE Computer Society, April 2003. Page(s):8 pp. Full Text: PDF(315 KB).