CS 343 Concurrent and Parallel Programming

Control-flow/Concurrency Papers

Structured Programming

• Corrado Bohm and Giuseppe Jacopini, Flow Diagrams, Turing Machines and Languages with only two Formation Rules 1966
• Edsger W. Dijkstra, Go To Statement Considered Harmful 1968
• W. W. Peterson, T. Kasami and N. Tokura, On the Capabilities of While, Repeat, and Exit Statements 1973
• Donald E. Knuth, Structured Programming with go to Statements 1974

Exceptions

• John B. Goodenough, Exception Handling: Issues and a Proposed Notation 1975
• R. D. Tennent, Language Design Methods Based on Semantic Principles 1977
• M. Donald MacLaren, Exception Handling in PL/I 1977
• Barbara H. Liskov and Alan Snyder, Exception Handling in CLU, 1979
• Jorgen Lindskov Knudsen, Better Exception Handling in Block Structured Systems 1987
• N. H. Gehani, Exceptional C or C with Exceptions 1992
• Mark Dowson, The Ariane 5 software failure 1997
• Robert Miller and Anand Tripathi, Issues with Exception Handling in Object-Oriented Systems 1997
• Jun Lang and David B. Stewart, A Study of the Applicability of Existing Exception-Handling Techniques to Component-Based Real-Time Software Technology 1998
• Michael Zastre and R. Nigel Horspool, Exploiting Exceptions 2001
• Barbara G. Ryder and Mary Lou Soffa, Influences on the Design of Exception Handling 2003
• Marko van Dooren and Eric Steegmans Combining the Robustness of Checked Exceptions with the Flexibility of Unchecked Exceptions using Anchored Exception Declarations 2005

Coroutines

• Melvin E. Conway, Design of a Separable Transition-Diagram Compiler 1963
• Christopher D. Marlin, Coroutines: A Programming Methodology, a Language Design and an Implementation 1980

Concurrency

• Edsger W. Dijkstra, Cooperating Sequential Processes 1965
• Gregory R. Andrews and Fred B. Schneider, Concepts and Notations for Concurrent Programming 1983
• C. A. R. Hoare, Communicating Sequential Processes 1985
• Peter A. Buhr, Are Safe Concurrency Libraries Possible? 1995
• Yuan Shi, Reevaluating Amdahl's Law and Gustafson's Law 1996
• Sarita V. Adve and Kourosh Gharachorloo, Shared Memory Consistency Models: A Tutorial 1996
• David B. Skillicorn and Domenico Talia, Models and Languages for Parallel Computation 1998
• Peter A. Buhr, Ashif S. Harji, Philipp E. Lim and Jiongxiong Chen, Object-oriented Real-Time Concurrency 2000
• Peter A. Buhr and Ashif S. Harji, Concurrent Urban Legends 2005

Concurrent Exceptions

• Andrzej Szalas and Danuta Szczepanska, Exception Handling in Parallel Computations 1985
• Peter A. Buhr, Hamish I. Macdonald, and C. Robert Zarnke, Synchronous and Asynchronous Handling of Abnormal Events in the uSystem 1992
• Jun Lang and David B. Stewart, Exception Handling and Real Time features in an Object-Oriented Concurrent Language 1998
• Peter A. Buhr and W. Y. Russell Mok, Advanced exception handling mechanisms 2000
• Peter A. Buhr and Roy Krischer, Bound Exceptions in Object-Oriented Programming 2006

Locks

• Murray A. Eisenberg and Michael R. McGuire, Further Comments on Dijkstra's Concurrent Programming Control Problem 1972
• Leslie Lamport, A New Solution of Dijkstra's Concurrent Programming Problem 1974
• G. L. Peterson, Myths About the Mutual Exclusion Problem 1981
• J. L. W. Kessels, Arbitration Without Common Modifiable Variables 1982
• Eric C. R. Hehner and R. K. Shyamasundar, An Implementation of P and V 1981
• John M. Mellor-Crummey and Michael L. Scott, Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors 1981
• Maurice Herlihy, A Methodology for Implementing Highly Concurrent Data Objects 1993
• Maged M. Michael and Michael L. Scott, Simple, Fast, and Practical Non-blocking and Blocking Concurrent Queue Algorithms 1996
• Kenneth A. Reek, The Well-Tempered Semaphore: Theme with Variations 2002 (Incorrectly states semantics of Brinch Hansen's monitor semantics in Concurrent Pascal. The signalling thread returns from the monitor rather than continuing in the monitor.)
• Maged M. Michael, Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects, 2004
• Hakan Sundell and Philippas Tsigas, Lock-free Deques and Doubly Linked Lists 2008
• Tim Harris, Simon Marlow, Simon Peyton Jones, and Maurice Herlihy, Composable Memory Transactions 2008
• Peter Sewell, Susmit Sarkar, Scott Owens, Francesco Zappa Nardelli, and Magnus O. Myreen, x86-TSO: A Rigorous and Usable Programmer's Model for x86 Multiprocessors 2010

Monitors

• Per Brinch Hansen, Concurrent Programming Concepts 1973
• C. A. R. Hoare, Monitors: an Operating System Structuring Concept 1974
• John H. Howard, Signaling in Monitors 1976
• J. L. W. Kessels, An Alternative to Event Queues for Synchronization in Monitors 1977
• Peter A. Buhr, Michel Fortier and Michael H. Coffin, Monitor Classification 1995
• Peter A. Buhr and Ashif S. Harji, Implicit-Signal Monitors 2005

Deadlock

• Richard C. Holt, Some Deadlock Properties of Computer Systems 1972
• Yin Wang, Stephane Lafortune, Terence Kelly, Manjunath Kudlur and Scott Mahlke The Theory of Deadlock Avoidance via Discrete Control 2009

Tasks

• W. Morven Gentleman, Message passing between sequential processes: The reply primitive and the administrator concept 1981
• Brian N. Bershad, Edward D. Lazowska, and Henry M. Levy, PRESTO: A System for Object-Oriented Parallel Programming 1988
• Peter A. Buhr and Richard A. Stroobosscher, The μSystem: Providing Light-Weight Concurrency on Shared-Memory Multiprocessor Computers Running UNIX 1990
• P. A. Buhr, Glen Ditchfield, R. A. Stroobosscher, B. M. Younger, and C. R. Zarnke, μC++: Concurrency in the Object-Oriented Language C++ 1992
• Charles E. Leiserson, The Cilk++ Concurrency Platform 2009

Futures

• Henry C. Baker, Jr. and Carl Hewitt, The Incremental Garbage Collection of Processes 1977