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:

Extensibility for performance, policy control and enhanced functionality. Research issues include protection, scheduling, safety, accounting, optimization and indexing in face of object encapsulation.
Transactions and Data Structures, separating physical consistency from logical consistency.
Parallelism, including architectures, memory management, data partitioning, scheduling and query optimization.
Wide-Area Distribution, including distributed transactions, disconnected operation, caching, and query optimization.
Scalability, Availability and Consistency, allowing tradeoffs between these issues.
Recent topics of interest, including perhaps the exploitation of language ideas in OSes, and scalable data analysis.

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

Prerequisites

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.

Projects

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

Readings

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.

Date


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	NOW/Rivers 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	SPRING BREAK
Th 3/28	SPRING BREAK
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. Background: 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. Background: *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 Background: 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

1/22: Introduction
1/24: OS Extensibilility: Exokernel
1/29: OODBMSs I
1/31: OODBMSs II
2/5: ORDBMSs
2/7: Disco
2/12: R-trees and GiST
2/14: GiST and semi-structured data indexing
2/19: RPC mechanisms
2/21: Data security and authentication protocols
2/26: Kerberos and Java extensible security

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