Administrative Information

Professor

T.A.

Course Description

A hands-on project oriented course on what's hot in systems research!

Advanced Operating Systems is a graduate level course on advanced concepts on operating systems and distributed computing. The course covers a wide array of research topics in systems, from historical perspectives to current topics such as peer-to-peer computing and mobile systems. The class consists of two major thrusts: reading and reviewing papers and doing a research project on your own.

Location and Time

Tuesdays and Thursdays 1-2pm.
We will meet in 1890 Maple, Room 342.

In compliance with Section 504 of the 1973 Rehabilitation Act and the Americans with Disabilities Act, Northwestern University is committed to providing equal access to all programming. Students with disabilities seeking accommodations are encouraged to contact the office of Services for Students with Disabilities (SSD) at +1 847 467-5530 or ssd@northwestern.edu. SSD is located in the basement of Scott Hall. Additionally, I am available to discuss disability-related needs during office hours or by appointment.

Course Prerequisites

The basic prerequisite for this classis an undergraduate operating system course (such as CS-343). Please come talk to me if you don't fulfill this requirement.

Communication Channels

There are a number of communication channels set up for this class:

• We will use the course web site to post announcements related to the course. You should check this regularly for schedule changes and other course-related announcements.
• Finally, there is an email alias (CS-495-AOS-Staff@cs) to contact the staff. Questions and comments should be sent there. Please prefix the subject line with "CS-495" for a prompt response.

Announcements

• Given that we always run at least 10/15' over the allocated class time, we have agreed on starting 10' earlier from Tue. Jan 21st.
• If you haven't yet, please email me to set a meeting time in the following week (Tue 21st or Thu 23rd Jan)

Materials

There is no textbook for this course. The course will be structured around readings from conference proceedings and journal articles.

Grading

50% Project
10% Project and paper presentation
20% In-class paper presentations
20% Class participation

Reading Papers

You will be responsible for reading and preparing a short (typed) summary of one or two papers before each class. Your final grade will depend on faithfully submitting summaries for each and every paper before we talk about them in class: this is simple to ensure everybody keeps up with the reading.
We will be reading one or two papers per meeting. Each paper will be presented to the group by a student and then discussed in a round-table manner.

When reading papers it is normally useful to write down a summary of about a page. Your summary should include at least:

1. Paper title and its author(s).
2. Brief one-line summary.
3. A paragraph of the most important ideas: perhaps a combination of their motivations, observations, interesting parts of the design, or clever parts of their implementation.
4. A paragraph of the largest flaws; maybe an experiment was poorly designed or the main idea had a narrow scope or applicability. Being able to assess weaknesses as well as strengths is an important skill for this course and beyond.
5. A last paragraph where you state the relevance of the ideas today, potential future research suggested by the article, etc.

You may find the following brochure useful: Efficient reading of papers in Science and Technology by Michael J. Hanson, 1990, revised 2000 Dylan McNamee.

Research Projects

Research projects (done in groups of size 2+) are a critical component of this course. Your goal is to design, build and evaluate interesting systems that address issues, solve problems and exploit techniques from classroom discussions and readings.

Projects must be written up in a term paper and teams will present their results at the end of the course in a systems class poster session or mini-conference. Projects ideas will be suggested by the instructor, but you are encouraged to come up with your own ideas.

This is a small list of potential ideas for projects (access restricted to inside the Department Computer Science at Northwestern U.).

Project Deliverables and Deadlines

1. Proposal - January 28: 2-3 pages describing the purpose of the project, work to be done and potential load distribution, expected outcome/results, ....
2. Literature Survey - February 4: 2-3 pages (plus references) describing context and related work for the proposed project.
3. Design Document - February 11: 4-5 pages with a detailed description of the software design, load distribution among group members. Construct a detailed sketch of your evaluation plan - what hypothesis is to be tested, how will you control the test circumstances, what workloads will you apply, why will this test enable resolution of the hypothesis, and what and how will specific metrics be measured.
4. Final Report - March 18: The final report is a workshop-level paper describing your work, evaluation, related research, potential avenues to explore, etc. Code should be submitted electronically.

General Advice

• John Wilkes, CSP project startup documents, (HPL-CSP-90-42), 11 Oct. 1990 - A great guideline for project proposals.
• Roy Levin and David D. Redell, An evaluation of the ninth SOSP submissions -or- How (and how not) to write a good systems paper, ACM SIGOPS Operating Systems Review 17(3):35-40 (Jul., 1983)
• George D. Gopen and Judith A. Swan,The Science of Scientific Writing,American Scientist (Nov-Dec 1990), 78: 550-558.

Readings

Operating Systems Design

January 7

• B. Lampson, Hints for Computer System Design, ACM Symposium on Operating Systems Principles, Dec. 1983, pp 33-48.
• Richard P. Gabriel, "Worse is Better", an excerpt (section 2-2.1, pp. 7-10) from LISP: good news, bad news, how to win big, AI Expert, 6(6):31-39, Jun. 1991.

January 9

• Jeffrey Chase, Henry Levy, Michael Feeley, and Edward Lazowska, Sharing and Protection in a Single Address Space Operating System, ACM Trans. on Computer Systems, Nov. 1994.
  Presenter: Geet Duggal

January 14

• Brian Bershad et al.,Extensibility, Safety and Performance in the SPIN Operating System, Proc. of the 15th ACM Symposium on Operating System Principles, Dec. 1995.
  Presenter: Stefan Birrer

Optional Reading

• Andrew S. Tanenbaum, Operating System Design, in Modern Operating Systems, 2nd Ed., Upper-Saddle River, NJ, Prentice-Hall, 2001.
• M. Frans Kaashoek, Dawson R. Engler, Gregory R. Ganger, Hector M. Briceno, Russell Hunt, David Mazieres, Thomas Pinckney, Robert Grimm, John Jannotti, and Kenneth Mackenzie, Application Performance and Flexibility on Exokernel Systems, Proc. of the 16th ACM Symposium on Operating Systems Principles, Oct. 1997.
• J. Liedtke,On Micro-Kernel Construction, Proc. of the 15th ACM Symposium on Operating System Principles, Dec. 1995.
• E. Bugnion, S. Devine and Mendel Rosenblum, Disco: Running Commodity Operating Systems on Scalable Multiprocessors, Proc. of the 16th ACM Symposium on Operating Systems Principles, Oct. 1997.

Communication

January 16

• Andrew D. Birrell and Bruce Jay Nelson. Implementing Remote Procedure Calls ACM Trans. on Computer Systems 2(1):39:59, Feb. 1984.
  Presenter: Bob Adolf

January 21

• David Wetherall, Active Networks: Vision and Reality: Lessons from a Capsule-based System, 17th ACM Symposium on Operating System Principles, Dec. 1999.
  Presenter: Ankit Mohan

Optional Reading

• Andrew S. Tanenbaum and Marteen van Steen, Communication, in Distributed Systems: Principles and Paradigms, Upper-Saddle River, NJ, Prentice-Hall, 2002.
• John Hartman, Larry Peterson, Andy Bavier, Peter Bigot, Patrick Bridges, Brady Montz, Rob Piltz, Todd Proebsting, and Uliver Spatscheck, Joust: A Platform for Liquid Software. IEEE Computer (1999)
• Wallach, D.A., Hsieh, W.C., Johnson, K.K., Kaashoek, M.F., and Weihl, W.E., Optimistic Active Messages: A Mechanism for Scheduling Communication with Computation, Proc. of ACM SIGPLAN Symposium on Principles qPractice of Parallel Programming (PPOPP), pp. 217-225, Jul. 1995.
• Greg Eisenhauer, Fabian E. Bustamante and Karsten Schwan, Native Data Representation: An Efficient Wire Format for High-Performance Computing, IEEE Transaction on Parallel and Distributed Systems, Nov. 2002.
• Kenneth P. Birman, The Process Group Approach to Reliable Distributed Computing. Communications of the ACM (CACM), 36(12):37-53, Dec. 1993.
• Greg Eisenhauer, Fabian E. Bustamante and Karsten Schwan, Event Services for High Performance Computing, Proc. of Ninth International Symposium on High Performance Distributed Computing (HPDC-2000), Pittsburgh, Pennsylvania, Aug. 2000.

Processes and Threads

January 23

• Mor Harchol-Balter and Allen B. Downey, Exploiting Process Lifetime Distributions for Dynamic Load Balancing, ACM Transactions on Computer Systems 15(3):253-285, Aug. 1997.
  Presenter: Yi Qiao

January 30

• D. Milojicic, F. Douglis, Y. Paindaveine, R. Wheeler, and S. Zhou, Process Migration, ACM Computing Surveys 32(3), Sept. 2000.
  Presenter: Kenin Coloma

Optional Reading

• Andrew S. Tanenbaum and Marteen van Steen, Processes, in Distributed Systems: Principles and Paradigms, Upper-Saddle River, NJ, Prentice-Hall, 2002.
• E. Jul, H. Levy, N. Hutchinson, A. Black, Fine-Grained Mobility in the Emerald System, ACM Transactions on Computer Systems 6(1):109-133, Feb. 1988.
• R. Gray, D. Kotz, G. Cybenko, D. Rus, Mobile Agents: Motivations and State-of-the-Art Systems, Dartmouth Technical Report TR2000-365, Apr. 2000. To appear as a chapter in Jeffrey M. Bradshaw, editor, Handbook of Agent Technulogy, AAAI/MIT Press, 2000. In Press.
• C. Hauser, C. Jacobi, et. al, Using Threads in Interactive Systems: A Case Study, Proc. of the ACM Symposium on Operating Systems Principles, Dec. 1993.
• K. Amiri, D. Petrou, G. Ganger, G. Gibson, Dynamic Function Placement for Data-Intensive Cluster Computing, Usenix Annual Technical Conference, Jun. 2000, pp. 307-322.

Naming

February 4

• A. Vahdat, M. Dahlin, T. Anderson, A. Aggarwal, Active Names: Flexible Location and Transport of Wide-Area Resources, USENIX Symposium on Internet Technulogies and Systems (USITS), Oct. 1999.
  Presenter: Bin Lin

Optional Reading

• Andrew S. Tanenbaum and Marteen van Steen, Naming, in Distributed Systems: Principles and Paradigms, Upper-Saddle River, NJ, Prentice-Hall, 2002.
• Fabian E. Bustamante, Greg Eisenhauer, Karsten Schwan, and Patrick Widener, Scalable Directory Services Using Proactivity, Proc. of Supercomputing 2002 (SC 2002), Baltimore, MD, Nov. 2002.
• William Adjie-Winoto, Elliot Schwartz, Hari Balakrishnan, Jeremy Lilley, The design and implementation of an intentional naming system, Proc. of the 17th ACM Symposium on Operating Systems Principles, Dec. 1999.
• David R. Cheriton and Timothy P. Mann, Decentralizing a Global Naming Service for Improved Performance and Fault Tulerance, ACM Transactions on Computer Systems 7(2):147:183, 1989.
• Jaeyeon Jung, Emil Sit, Hari Balakrishnan, and Robert Morris, DNS Performance and the Effectiveness of Caching.ACM SIGCOMM Internet Measurement Workshop, Nov. 2001.

Shared and Virtual Memory

February 6

• C. Amza, A. Cox, S Dwarkadas, P Keleher, H Lu, R. Rajamony, W. Yu and W. Zwaenepoel, TreadMarks: Shared Memory Computing on Networks of Workstations IEEE Computer, Feb., 1996.
  Presenter: David Nguyen

February 11

• Michael J. Feeley, William E. Morgan, Frederic H. Pighin, Anna R. Karlin and Henry M. Levy, Implementing Global Memory Management in a Workstation Cluster, Fifteenth ACM Symposium on Operating System Principles, Dec. 1995.
  Presenter: Fabián E. Bustamante

Optional Reading

• Kai Li and Paul Hudak, Memory Coherence in Shared Virtual Memory Systems, ACM Trans. on Computer Systems 7(4):321-359, Nov. 1989.
• K. Harty and D.Cheriton. Application-Contrulled Physical Memory using External Page-Cache Management. Proc. of the 5th International Conference on Architectural Support for Programming Languages and Operating Systems, 1992, pp. 187-197.

• Anderson, T.E., The Performance Implications of Spin-Waiting Alternatives for Shared-Memory Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, 1(1):6-16, Jan. 1990.
• Daniel J. Scales and Kourosh Gharachorloo. Towards Transparent and Efficient Software Distributed Shared Memory Proc. of the 16th ACM Symposium on Operating Systems Principles, Oct. 1997

• Andrew W. Appel and Kai Li. Virtual Memory Primitives for User Programs, Proc. of the 4th International Conference on Architectural Support for Programming Langauges and Operating Systems, 1991.

Synchronization

February 13

• Leslie Lamport, Robert Shostak, Marshall Pease, The Byzantine General's Problem ACM Transactions on Programming Languages and Systems, 4(3):382-401, July 1982.
  Presenter: Aaron Johnson

Optional Reading

• Leslie Lamport, Time, Clocks, and the Ordering of Events in a Distributed System, Communications of the ACM, 21(7):558-565, Jul. 1978.
• Andrew S. Tanenbaum and Marteen van Steen, Synchronization, in Distributed Systems: Principles and Paradigms, Upper-Saddle River, NJ, Prentice-Hall, 2002.
• Divyakant Agrawal and Amr el Abbadi, An Efficient and Fault-Tulerant Sulution for Distributed Mutual Exclusion, ACM Transactions on Computer Systems 9(1):1-20, Feb. 1991.
• K. Mani Chandy and Leslie Lamport, Distributed Snapshots: Determining Global States of Distributed Systems.ACM Transactions on Computing Systems, 3(1):63-75, Feb. 1985.

Replication, Caching and Consistency

February 18

• M. Wiesmann, F. Pedone, A. Schiper, B. Kemme, and G. Alonso, Understanding Replication in Databases and Distributed Systems, Proc. of the 20th International Conference on Distributed Computing Systems (ICDCS), 2000, pp. 464-474.
  Presenter: Bob Adolf

February 20

• Alan Demers, Dan Greene, Carl Hauser, Wes Irish and John Larson, Epidemic Algorithms for Replicated Database Maintenance. Proc. of the Sixth Annual ACM Symposium on Principles of Distributed Computing, 1987.
  Presenter: Ananth Sundararaj

Optional Reading

• Michael D. Dahlin, Randulph Y. Wang, Thomas E. Anderson, David A. Patterson, Cooperative Caching: Using Remote Client Memory to Improve File System Performance, Proc. of the Symposium on Operating Systems Design and Implementation, Nov. 1994.
• Andrew S. Tanenbaum and Marteen van Steen, Consistency and Replication, in Distributed Systems: Principles and Paradigms, Upper-Saddle River, NJ, Prentice-Hall, 2002.
• C. Gray and D. Cheriton, Leases: an Efficient Fault-tulerant Mechanism for Distributed File Cache Consistency. Proc. of the 12th ACM Symposium on Operating Systems Principles, Dec. 1989.
• Alec Wulman, Geoffrey M. Voelker, Nitin Sharma, Neal Cardwell, Anna Karlin, and Henry M. Levy, On the scale and performance of cooperative Web proxy caching, Proc. of the 17th Symposium on Operating System Principles, Dec. 1999.
• D. B. Terry, M. M. Theimer, Karin Petersen, A. J. Demers, M. J. Spreitzer, and C. H. Hauser, Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System. Proc. of the Fifteenth ACM Symposium on Operating Systems Principles, 1995.
• R. Ladin, B. Liskov, L. Shira, and S. Ghemewat, Providing High Reliability using Lazy Replication. ACM Transactions on Computer Systems, 10(4):360--391, 1992.

Storage and File Systems

February 25

• Mahadev Satyanarayanan, James J. Kistler, Puneet Kumar, Maria E. Okasaki, Ellen H. Siegel and David C. Steere, Coda: A Highly Available File System for a Distributed Workstation Environment, IEEE Transactions on Computers 39(4):447-459, Apr. 1990.
  Presenter: Avery Ching

February 27

• Athicha Muthitacharoen, Benjie Chen, and David Mazieres, A Low-Bandwidth Network File System, Proc. of the 18th ACM Symposium on Operating Systems Principles (SOSP '01), Oct. 2001, pp. 174-187.
  Presenter: Jeremy Kwock

Optional Reading

• Andrew S. Tanenbaum and Marteen van Steen, Distributed File Systems, in Distributed Systems: Principles and Paradigms, Upper-Saddle River, NJ, Prentice-Hall, 2002.
• Mahadev Satyanarayanan, Distributed File Systems, in Distributed Systems, 2nd Ed., S. Mullender (ed.), NY, ACM Press, 1993.
• Thomas E. Anderson, Michael D. Dahlin, Jeanna M. Neefe, David A. Patterson, Drew S. Roselli and Randolph Y. Wang Serverless Network File System, ACM Transpaction on Computer Systems, Feb. 1996.
• Richard G. Guy, John S. Heidemann, Wai Mak, Thomas W. Page, Jr., Gerald J. Popek, and Dieter Rothmeier, Implementation of the Ficus Replicated File System, In USENIX Conference Proc., pp. 63-71. Anaheim, CA, USENIX. Jun., 1990.
• Mendel Rosenblum and John K. Ousterhout, The Design and Implementation of a Log-Structured File System. ACM Trans. on Computer Systems 10(1):26-52, Feb. 1992.
• Michael N. Nelson, Brent B. Welch, and John K. Ousterhout. Caching in the Sprite Network File System.ACM Trans. on Computer Systems 6(1):134-154, Feb. 1988.
• John H. Howard, Michael L. Kazar, Sherri G. Menees, David A. Nichuls, M. Stayanayanan, Robert N. Sidebotham, and Michael J. West. Scale and Performance in a Distributed File System. ACM Trans. on Computer Systems 6(1):51-81, Feb. 1988.

Internet Services

March 4

• Armando Fox, Steven Gribble, Yatin Chawathe, Eric Brewer, and Paul Gauthier. Cluster-based Scalable Network Services Proc. of the 16th ACM Symposium on Operating Systems Principles, Oct. 1997, pp. 78-91.
  Presenter: Ashish Gupta

March 6

• Y. Saito, B. Bershad, and H. Levy. Manageability, Availability and Performance in Porcupine: A Highly Scalable Internet Mail Service.Proc. of the 17th ACM Symposium on Operating Systems Principles, Dec. 1999.
  Presenter: Aaron Johnson

Optional Reading

• V.S. Pai, M. Aron, G. Banga, M. Svendsen, P. Druschel, W. Zwaenepoel, and E. Nahum. Locality-Aware Request Distribution in Cluster-Based Network Servers."Proc. of the 8th ACM/IEEE Symposium on Arch. Support for Prog. Lang. and Operating Systems, Oct. 1998, pp.205-216.
• M. Welsh, D. Culler, E. Brewer. SEDA: An Architecture for Well-Conditioned, Scalable Internet Services. Proc. of the 18th ACM. Symposium on Operating Systems Principles, Oct. 2001.
• S. Gribble, E. Brewer, J. Hellerstein, and D. Culler. Scalable, Distributed Data Structures for Internet Service Construction. Proc. of the Fourth USENIX Symposium on Operating Systems Design and Implementation (OSDI 2000), Oct. 2000.

Peer-to-Peer, Mobile and Grid Computing

March 11

• A. Rowstron and P. Druschel. Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility.Proc. of the 18th ACM. Symposium on Operating Systems Principles, Oct. 2001.
  Presenter: Hunter Morris

March 13

• M. van Steen, P. Homburg and A.S. Tanenbaum, The Architectural Design of GLOBE: a wide-area distributed system, Technical Report IR-422 (Vrije Universiteit, Amsterdam, 1997)
  Presenter: Ananth Sundararaj

Optional Reading

• B. Noble, M. Satyanarayanan, D. Narayanan, J. Tilton, J. Flinn, and K. Walker. Agile Application-Aware Adaptation for Mobility. Proc. of the 16th ACM Symposium on Operating Systems Principles, Oct. 1997.
• John Kubiatowicz, David Bindel, Yan Chen, Steven Czerwinski, Patrick Eaton, Dennis Geels, Ramakrishna Gummadi, Sean Rhea, Hakim Weatherspoon, Westley Weimer, Chris Wells, and Ben Zhao, OceanStore: An Architecture for Global-Scale Persistent Storage, Proc. of the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2000), Nov. 2000.
• F. Dabek, M. F. Kaashoek, D. Karger, R. Morris, I. Stoica. Wide Area Cooperative Storage with CFS.Proc. of the 18th ACM. Symposium on Operating Systems Principles, Oct. 2001.
• William J. Bolosky, John R. Doceur, David Ely, and Marvin Theimer,Feasibility of a Serverless Distributed File System Deployed on an Existing Set of Desktop PCs, Proc. of the 2000 SIGMETRICS Conference, Jun. 2000, Santa Clara, California.
• David De Roure, Mark A. Baker, Nichulas R. Jennings and Nigel R. Shadbult, The Evulution of the Grid (pre print), Universities of Portsmouth and Southampton, UK. In Grid Computing: Making the Global Infrastructure a Reality.