CS262-B: Advanced Topics in Computer Systems

CCN:  26986

Mike Franklin and Kim Keeton, Spring 2002

CS262-B is the second semester of a year-long sequence on computer systems research, including operating systems, database systems, and internet infrastructure systems.  The goal of the course is to cover abroad array of research topics in computer systems, and to engage you in systems research.

The second semester is devoted to advanced research themes in computer systems:

The class is based on a discussion of important research papers, and a research project.  Homework may also be assigned.


CS262A is a prerequisite for this course.  If you have taken CS262 and CS286 in years before 1999, you may not be eligible to enroll for CS262-B; please email an instructor for more information.

Exams, Papers, Homework, etc.

The main work of this class is to read steadily, while working toward a group research project of publishable quality.  Each student will be individually responsible for writing up a short summary of every paper. There will also be several homework assignments.


Research projects are a critical aspect of the course.  The goal is to do some quality systems research; that is, to add to our understanding of how to build software systems.  Research projects must be written up in a term paper, and will be presented in a poster in a departmental mini-conference.  In some cases, it may be appropriate to extend your project from CS262A, in others it would be better to pick a new project. Please contact Prof.  Franklin or Keeton for guidance on projects.

Project suggestions
Dates Project Milestone
Week of 2/25/02 Initial group meetings with instructors
Friday, 3/8/02 5pm Project proposals due
Friday, 3/22/02 5pm Related work summary due
Week of 4/15/02 Progress meetings with instructors
Week of 5/13/02 Final meetings with instructors
Tuesday, 5/21/02  1pm - 3pm Poster session for department (tentative)
Thursday, 5/23/02 12pm (noon) Final reports due


There is one required textbook, which should be available at ASUC (and on the web).  It is Readings in Database Systems.  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. An additional suggested test is Gray and Reuter's Transaction Processing: Concepts and Techniques.
Week 1
T 1/22 
Course Introduction
Th 1/24 OS Extensibility I

Exokernel:  An Operating System Architecture for Application-Level Resource Management
D. Engler, M. F. Kaashoek, and J. O'Toole, Jr., Proc. of SOSP-15, December 1995. 

Application Performance and Flexibility on Exokernel Systems (opt.) 
M. F. Kaashoek, et al., Proc of SOSP-17, 1997.

Week 2 

T 1/29


Object-oriented DB I

Object and File Management in the EXODUS Extensible Database System
Carey, DeWitt, Richardson and Shekita, Proc. of VLDB, 1986. 

Of Objects and Databases: A Decade of Turmoil
D. DeWitt and M. Carey, VLDB 10-year award lecture, Proc. of VLDB, 1996.

Th 1/31 Object-oriented DB II

The ObjectStore Database System (in red book) 
Lamb, Landis, Orenstein and Weinreb, Communications of the ACM, 34(10), 1991.

QuickStore: A High Peformance Mapped Object Store
White and DeWitt (in red book)

Week 3 

T 2/5


Object-relational DBs

The POSTGRES Next-Generation Database Management System
Stonebraker and Kemnitz (in red book)

O-O, What Have They Done to DB2?
M. Carey, et al., Proc. VLDB, 1999.

T 2/7 OS Virtualization

Disco:  Running Commodity Operating Systems on Scalable Multiprocessors
Bugnion, Devine and Rosenblum, Proc. SOSP-16, October 1997. 

Week 4 

T 2/12


DB Indexing I

R-Trees: A Dynamic Index Structure for Spatial Searching
Guttman (in Red Book)

Generalized Search Trees for Database Systems
Hellerstein, Naughton and Pfeffer (in Red Book)

Th 2/14 DB Indexing II

GIST (cont)

A Fast Index for Semi-structured Data
Cooper, et al.

Week 5 

T 2/19

RPC Mechanisms

Implementing Remote Procedure Calls
Birrell and Nelson, ACM Transactions on Computer Systems, Vol. 2, No. 1, Febrary 1984.

Simple Object Access Protocol (SOAP)
Box, et al.  (skim)

Related background reading from CS262A:
Active Messages: A Mechanism for Integrated Communication and Control
von Eicken, Culler, Goldstein, and Schauser

Th 2/21 Security I

Data Security
Denning and Denning, Computing Surveys, Vol. 11, No. 3, September 1979, pp. 227-249.

Using Encryption for Authentication in Large Networks of Computers
Needham and Schroeder, Communications of the ACM, 21(12), December 1978, pp. 993-999.

Week 6 

T 2/26

Security II

Kerberos: An Authentication Service for Open Network Systems
J. G. Steiner, C. Neuman, J. I. Schiller, Proc. of USENIX '88, Dallas, TX, February 1988, pp. 191-202.

Extensible Security Architectures for Java
D. Wallach, D. Balfanz, D. Dean and E. Felten, Proc. of SOSP-16, October 1997.

Reflections on trusting trust (for fun) 
Ken Thompson, ACM Turing Award Lecture, Communications of the ACM, Vol. 27, No. 8, August 1984, pp. 761-763.

Th 2/28 Security III 

Extensible Security Architectures for Java (cont)

Data and Database Security and Controls
 Ravi Sandhu and Sushil Jajodia,
Handbook of Information Security Management, Auerbach, 1993

Week 7 

T 3/5

DB: Logical vs. Physical Consistency

KVL- A Key-Value Locking Method for Concurrency Control ...
C. Mohan, VLDB 1990

Th 3/7 Parallel Databases

The Gamma Database Machine Project
DeWitt, et al. (in Red Book) 

Parallel Database Systems- The Future of High Performance Database Systems
DeWitt & Gray,  CACM June 1992.

HW 2 assigned (due Tuesday, 3/19) 

Week 8 

T 3/12

Parallel databases (cont.)


Th 3/14 AlphaSort and Benchmarking

AlphaSort:  A Cache-Sensitive Parallel External Sort
Chris Nyberg, Tom Barclay, Zarka Cvetanovic, Jim Gray, Dave Lomet, VLDB Journal 4(4): 603-627 (1995)

The Sort Benchmark Home Page (for reference)

The Benchmark Handbook Home Page (for reference)

Week 9 

T 3/19 

HW 2 due


A Case for NOW
Anderson, et al.

Cluster I/O with River: Making the Fast Case Common
Arpaci-Dusseau et al.

Th 3/21 Using Clusters for Network Services

Lessons from Giant-Scale Services
E. Brewer, IEEE Internet Computing, July/August 2001.

Extensible Cluster-Based Scalable Network Services
A. Fox, S. Gribble, Y. Chawathe, E. Brewer, and P. Gauthier, SOSP-16, 1997.

Week 10
T 3/26
Week 11 

T 4/2

Network Service Semantics (ACID vs. BASE)

Extensible Cluster-Based Scalable Network Services
A. Fox, S. Gribble, Y. Chawathe, E. Brewer, and P. Gauthier, SOSP-16, 1997.

Th 4/4 Messaging Semantics

The Process Group Approach to Reliable Distributed Computing.
Kenneth P. Birman,Communications of the ACM (CACM), 36(12):37-53, December 1993.

Understanding the Limitations of Causal and Totally Ordered Multicast.
D.R. Cheriton and D. Skeen, Proceedings of the 14th Symposium on Operating System Principles (SOSP '93), December 1993.

Week 12 

T 4/9 

HW 3 assigned

Distributed Query Processing

The State of the Art in Distributed Query Processing
D. Kossmann, ACM Computing Surveys,  Sept, 2000. 

Th 4/11 Distributed File Systems 101

Design and Implementation of the Sun Network Filesystem
R. Sandberg, et al., Proceedings of the Summer 1985 USENIX Conference, June 1985, pp. 119-130.

Scale and Performance in a Distributed File System
J. Howard, et al., ACM Transactions on Computer Systems, Vol. 6, No. 1, February 1988, pp. 51-81.

Caching in the Sprite Network File System
M. Nelson, B. Welch and J. Ousterhout, ACM Transactions on Computer Systems Vol. 6, No1, February 1988, pp. 134-154.

Week 13 

T 4/16 

HW 3 due

Cleverness in File Systems

Cooperative Caching: Using Remote Client Memory to Improve File System Performance
M. D. Dahlin, R. Y. Wang, T. E. Anderson, D. A. Patterson, Proc. First Symposium on Operating Systems Design and Implementation (OSDI), pp. 267-280. 

Deciding When to Forget in the Elephant File System
D. Santry, et al., Proc. of 17th SOSP, December 1999, pp. 110-123.


Global Memory Management in Client-Server Database Architectures
Michael J. Franklin, Michael J. Carey, Miron Livny,  VLDB 1992, pp. 596-609.

The Design of the POSTGRES Storage Manager 
M. Stonebraker 

Th 4/18 Measurement of File Systems

A Comparison of File System Workloads
D. Roselli, J. Lorch and T. Anderson, Proc. of 2000 USENIX Technical Conference, June 2000. 

Week 14 

T 4/23

Transactional Caching

Transactional Cache Consistency: Alternatives and Performance
M. Franklin, M. Carey, and M. Livny, ACM TODS, September, 1997.


Transaction Management in the R* Distributed Database System 
C. Mohan, B. Lindsay, and R. Obermark. (in red book)

Th 4/25 Class cancelled - Faculty Retreat 
Week 15 

T 4/30

Data Management for Weakly Connected I

The Dangers of Replication and a  Solution
J. Gray et al. , SIGMOD 1996 (in the red book).

Th 5/2 

HW 4 assigned

Data Management for Weakly Connected II

 Disconnected Operation in the Coda File System
 Kistler and Satyanarayanan 


Flexible Update Propagation for Weakly Consistent Replication
Petersen at al, SOSP 1997 

Week 16 

T 5/7

Self-managing OSes

Hippodrome:  running circles around storage administration
E. Anderson, M. Hobbs, K. Keeton, S. Spence, M. Uysal and A. Veitch, Proc. of USENIX File and Storage Technologies Conference (FAST), January 2002.

Managing Energy and Server Resources in Hosting Centers
J. Chase, D. Anderson, P. Thakar, A. Vahdat and R. Doyle, Proc. of SOSP, October 2001.

Th 5/9 Self-managing DBs

AutoAdmin "What-if" Index Analysis Utility
S. Chaudhuri and V. Narasayya, SIGMOD 98.

LEO-DB2's LEarning Optimizer
Stillger et al., VLDB 2001.

Week 17 

T 5/14 

HW 4 due

OS and DB research challenges and course wrap-up

Lecture Notes

Links to Previous semesters' courses: