Basic Info
 Lecture Notes
 Project Ideas
We will read and discuss 2-4 papers per week.  Many of the papers for the class will be available either on-line, or as handouts in a previous class.

Date Readings

 Part 1:  Basics and Classics

Tu 8/30 The UNIX Time-Sharing System
Dennis M. Richie and Ken Thompson
(New electronic version) 
Th 9/1 Entrance Exam
Tu 9/6 A History and Evaluation of System R
Donald D. Chamberlin, Morton A. Astrahan, Michael W. Blasgen, James N. Gray, W. Frank King, Bruce G. Lindsay, Raymond Lorie, James W. Mehl, Thomas G. Price, Franco Putzolu, Patricia Griffiths Selinger, Mario Schkolnick, Donald R. Slutz, Irving L. Traiger, Bradford W. Wade and Robert A. Yost

Anatomy of a Database System, Sections 1-3 Hellerstein & Stonebraker (in textbook). No summary required

Optional Reading: The Design and Implementation of Ingres
Michael Stonebraker, Eugene Wong, Peter Kreps and Gerald Held.

Th 9/9
Concurrency Control and Recovery, M. Franklin, in "The Computer Science and Engineering Handbook", 1997. Read only sections 1 through 3.1.1 (although we will cover all of it eventually). No summary required.

Optional: Pages 159-173 of Gray and Reuter's Transaction Processing: Concepts and Techniques, Morgan-Kaufmann, 1993. Available outside 685 Soda.

Part 2: Volatile Storage

Tu 9/13 Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures
Rashid, Tavanian, Young, Golub, Baron, Black, Bolosky and Chew
Th 9/15 Virtual Memory Primitives for User Programs
Appel and Li
Lightweight Recoverable Virtual Memory
M. Satyanarayanan, Henry H. Mashburn, Puneet Kumar, David C. Steere, and James J. Kistler
Tu 9/20 The Multics Virtual Memory: Concepts and Design
Bensoussan, Clingen and Daley
Th 9/22
The Five-Minute Rule Ten Years Later, and Other Computer Storage Rules of Thumb
Graefe and Gray (in textbook)

Optional Reading: An Evaluation of Buffer Management Strategies for Relational Database Systems
Hong-Tai Chou and David J. DeWitt

FYI on interesting DB-centric page replacement policies: LRU-K, 2Q, CAR.
Application-Controlled Physical Memory using External Page-Cache Management
Harty and Cheriton
Tu 9/27 Xen and the Art of Virtualization
P. Barham, B. Dragovic, K Fraser, S. Hand, T. Harris, A. Ho, R. Neugebauer, I. Pratt and A. Warfield.
Are Virtual Machine Monitors Microkernels Done Right? S. Hand, A. Warfield, K. Fraser, E. Kotsovinos, D. Magenheimer.
(likely but tentative: Steve Hand guest lecture).

Part 3: Persistent Storage

Th 9/29 Principles of Transaction-Oriented Database Recovery Computing Surveys 15(4): 287-317 (1983). In textbook, read Sections 1 and 2.
Theo Haerder & Andreas Reuter

The Design of the POSTGRES Storage Manager
M. Stonebraker
Tu 10/4 A Fast File System for UNIX
McKusick, Joy, Leffler and Fabry
The Design and Implementation of a Log-Structured File System
Rosenblum and Ousterhout (229K) 
Th 10/6 ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-ahead Logging, 2-up version
C. Mohan et al. (in Red Book)
Tu 10/11 Logging and recovery wrapup.
Th 10/13 The HP AutoRAID Hierarchical Storage System [My temporary local copy, 2-up version]
Wilkes, Golding, Staelin and Sullivan 

Part 4: Locking and Consistency

Tu 10/18 Experience with Processes and Monitors in Mesa
Butler Lampson and David Redell
Th 10/20 Granularity of Locks and Degrees of Consistency in a Shared Database
Gray et al. (Section I-II, pp. 173-193 in red book, copies outside 685)
Optional reading: Generalized Isolation Levels
Atul Adya, Barbara Liskov, Patrick O'Neil.
Tu 10/25 On Optimistic Methods for Concurrency Control
Kung and Robinson
Concurrency Control Performance Modeling: Alternatives and Implications
Agrawal et al.

Part 5: Query Processing

Th 10/27
Query Evaluation Techniques for Large Databases , Intro and Section 1 ONLY -- no summary required
Goetz Graefe
Join Processing in Database Systems with Large Main Memories[in Red Book]
L. D. Shapiro
Tu 11/1 Access Path Selection in a Relational Database Management System [all new version!] [in Red Book]
Selinger, Astrahan, Chamberlain, Lorie & Price
The Volcano Optimizer Generator: Extensibility and Efficient Search Graefe and McKenna.
Optional reading: Grammar-like Functional Rules for Representing Query Optimization Alternatives. G. Lohman [in Red Book]
Th 11/3 Encapsulation of Parallelism in the Volcano Query Processing System
Goetz Graefe
Eddies: Continuously Adaptive Query Processing
Joseph M. Hellerstein and Ron Avnur
Tu 11/8 The Click Modular Router
Kohler, Morris, Chen, Jannotti and Kaashoek

Part 6: Threads and Scheduling

Th 11/10 Cooperative Task Management without Manual Stack Management.
Adya, Howell, Theimer, Bolosky, and Douceur.
Capriccio: Scalable Threads for Internet Services.
von Behren, Condit, Zhou, Necula, and Brewer.
Optional reading: On the Duality of Operating System Structures.
Lauer and Needham.
Optional reading: John Ousterhout's 1996 slides on "Why threads are a bad idea"
Tu 11/15 Lottery Scheduling: Flexible Proportional-Share Resource Management
Waldspurger and Wiehl
Th 11/17 First class user-level threads.
B. D. Marsh, M. L. Scott, T. J. LeBlanc, and E. P. Markatos.
Scheduler Activations
Anderson, Bershad, Lazowska and Levy
Optional reading: The Structuring of Systems Using Upcalls.

Part 7: Networking

Tu 11/22
Congestion Avoidance and Control [PDF]
Van Jacobson
TCP Congestion Control with a Misbehaving Receiver
Savage, Cardwell, Wetherall and T. Anderson
Th 11/24 Thanksgiving holiday.
Tu 11/29
Layered multiplexing considered harmful
D. Tennenhouse

Architectural Considerations for a New Generation of Protocols"
Clark and Tennenhouse
Thu 12/1 Active Messages: A Mechanism for Integrated Communication and Control
von Eicken, Culler, Goldstein, and Schauser

U-Net: A User-Level Network Interface for Parallel and Distributed Computing
If you have problems with the postscript: PDF from the ACM
Basu, Buch, Vogels, and von Eicken

Part 8: Wind Up

Tu 12/6 Implementing Declarative Overlays. Loo et al.
Th 12/8 Final Lecture
Hints for Computer System Design
Butler Lampson. [No summary required]
What Next? A Dozen Information-Technology Research Goals. Jim Gray. [No summary required]