Alternative Programming Models for Concurrency ("Not Threads")

CSE 590 L: Languages Seminar, Spring 2003
Wednesdays, 1:30-2:20 p.m. MGH 085

This quarter, we'll be studying unusual ways of describing concurrency (and maybe also distribution and mobility), with a focus on language approaches. However, we also plan to read some papers on library-based or systems-based programming models, which may suggest new language ideas.

Schedule (subject to change)

Notes on preparing your presentation

As usual, we'd like to use the papers as an avenue for discussing some interesting research-level questions, rather than simply presenting a book report. What's perhaps unusual this quarter is that we're discussing some dusty old historical languages, as well as some papers that aren't directly language designs at all. So, it may take extra effort on your part to think about issues that might be interesting for current languages research, or at least that will spark some interesting discussion about novel ways to think about programming.

To help get you started on your presentation, here are some questions (feel free to ignore these if you have others you like better):

• In what domains do the authors envision this language being used? Can you give examples of programs that look beautiful in this language and ugly in most others? What about the other way around (ugly in this language, easy in others)?
• What operations and costs does this language make explicit, and which implicit? In other words what operations are programmer-controlled, as opposed to compiler-controlled, or hard-coded in the dynamic semantics? In what programming domains might these choices about explicit and implicit control be appropriate?
• What would the programmer sacrifice if this language's key features were implemented at the library level instead of the language level? (What if you implemented these features with Java classes? Haskell type classes? C++ templates? Aspects? Self?)
• If the language has been evaluated in real-world systems, what did the authors learn? (Besides the obvious: "My language is the best!", which is what every language designer inevitably discovers about his/her language.)
• Sometimes a language integrates an interesting feature, but does not go far enough. Simula was generalized by Smalltalk, which was generalized by Self. How could you take the features described in this language or system to the "next level"?

Topic & paper list

The papers linked below are preliminary choices, intended to represent entire lines of work rather than specific points. You can choose some other paper in that line of work for your talk. In some cases, individual papers may not give you enough material to make an interesting presentation; you should perhaps present a synthesis of multiple papers in that line of research.

Polyphonic C#

Polyphonic C# augments C# with synchronization constructs based on join patterns, from the Join Calculus.

Modern Concurrency Abstractions for C#. N. Benton, L. Cardelli, C. Fournet. ECOOP'02, April 2002. project web page, Acrobat (.pdf).

A more comprehensive version of this paper is currently under submission to TOPLAS. Look in NFS at ~klee/public/polyphony-toplas.pdf for this version.

Events vs. threads

Cooperative Task Management without Manual Stack Management. A. Adya, J. Howell, M. Theimer, W. J. Bolosky, J. R. Douceur. USENIX June 2002. project web page, Acrobat (.pdf)

Why Threads are a Bad Idea (For Most Purposes) T. Ousterhout. Invited talk slides, USENIX 1996. web slides (.html), PowerPoint (.ppt), Acrobat (.pdf).

TinyOS & nesC (resource-constrained concurrency)

Kurt has been programming in TinyOS, an operating system for embedded systems with an event-driven execution model. Programming TinyOS in raw C is quite cumbersome, because the user must do manual task management. It might be interesting to examine language designs or program analysis techniques to enable a better programming model in extremely resource-constrained environments.

TinyOS project web page

The nesC Language: A Holistic Approach to Networked Embedded Systems. D. Gay, P. Levis, R. von Behren, M. Welsh, E. Brewer, D. Culler. To appear in PLDI'03. This is in NFS at ~klee/public/p072-gay.pdf.

A Network-Centric Approach to Embedded Software for Tiny Devices. D. E. Culler, J. Hill, P. Buonadonna, R. Szewczyk, A. Woo. EMSOFT 2001, Oct. 2001. Acrobat (.pdf)

nesC Language Reference Manual. D. Gay, D. Culler, P. Lewis. nesC Language Reference Manual

OCCAM, CSP, and extensions

OCCAM was the system programming language for the INMOS transputer. Its semantic foundation was Hoare's CSP.

An OCCAM approach to transputer engineering. P. H. Welch. Third Conference on Hypercube Concurrent Computers and Applications. ACM link.

Type Checking Concurrent I/O. W. H. Carlisle. TOPLAS 17(3):448-460. ACM link.

Introduction to the Programming Language Occam

TupleSpaces and its relatives

Linda in Context. N. Carreiro, D. Gelernter. Communications of the ACM, 32(4):444-458, Apr. 1989. project web page, ACM paper link.

ActorSpaces: An Open Distributed Computing Paradigm. G. Agha, C. J. Callsen. PPOPP 4, 1993. ACM paper link.

XML Dataspaces for Mobile Agent Coordination G. Cabri, L. Leonardi, F. Zambonelli. ACM paper link

JavaSpaces: Innovative Java Technology that Simplifies Distributed Application Development. Sun Microsystems. White paper. project web page, Acrobat (.pdf),

Distributed Computation with JavaSpaces Technology. M. S. Noble. Talk slides, JavaOne 2001. Acrobat (.pdf)

Concurrent logic programming

Programming in concurrent logic languages. (Survey paper) M. M. Huntbach, G. A. Ringwood. IEEE Software 12(6), Nov. 1995. abstract, Acrobat (.pdf) (IEEE access required)

The Concurrent Language, Shared Prolog. A. Brogi, P. Ciancarini. TOPLAS 13(1):99-123, Jan. 1991. ACM link.

Distributed Programming with a Logic Channel Based Coordination Model. M Diaz, B. Rubio and J. M. Troya. Computer Journal 39(10), May 1997. gzip'd PostScript (.ps.gz), Acrobat (.pdf)

The Concurrent Object-Oriented Language Braid. M. Huntbach. Proc. 1995 Symposium on Applied Computing. ACM link

Streaming workloads (with implicit concurrency)

Infopipes: an Abstraction for Multimedia Streaming. A. P. Black, J. Huang, R. Koster, J. Walpole, and C. Pu. Multimedia Systems (special issue on Multimedia Middleware), 8(5):406-419, 2002. Acrobat (.pdf)

The Click Modular Router. E. Kohler, R. Morris, B. Chen, J. Jannotti, M. F. Kaashoek. ACM TOCS 18(3):263-297, Aug. 2000. web page, gzip'd PostScript (.ps.gz), Acrobat (.pdf)

Staged architectures (scalable concurrency)

SEDA: An Architecture for Well-Conditioned, Scalable Internet Services. M. Welsh, D. Culler, E. Brewer. SOSP 18, Oct. 2001. project web page, Acrobat (.pdf)

Using Cohort Scheduling to Enhance Server Performance. J. Larus, M. Parkes USENIX June 2002. Acrobat (.pdf)