CS-522: Principles of Computer Systems (Fall 2018)

A modern computer system spans many layers: applications, libraries, operating systems, networks, and hardware devices. Building a good system entails making the right trade-offs (e.g., between performance, durability, and correctness) and understanding emergent behaviors—the difference between great system designers and average ones is that the really good ones make these trade-offs in a principled fashion, not by trial-and-error. In this course, we identify some of the key principles underlying successful systems, and learn how to solve problems in computing using ideas, techniques, and algorithms from operating systems, networks, databases, programming languages, and computer architecture. The basic courses on these topics teach how the elemental parts of modern systems work; POCS picks up where those courses leave off and focuses on how the pieces come together to form useful, efficient systems.

This course is targeted primarily at students who wish to acquire a deep understanding of computer system design or pursue research in systems. It is an intellectually challenging, fast paced course, in which survival requires a good background in operating systems, databases, networking, programming languages, and computer architecture. Please see the syllabus for more information.

Staff

Instructors

Teaching assistants

We are delighted to have two guest lecturers this semester: Edouard Bugnion and Anne-Marie Kermarrec.

Readings

We use as a textbook Principles of Computer System Design: An Introduction by J. H. Saltzer and M. F. Kaashoek. The linked online book is free for EPFL students. Chapters 7 - 11 are also freely available online as a PDF. You can get the Kindle version or a 20th-century-style paperback for your own library.

Logistics

We hold in-class interactive sessions on Tuesdays 12:15-14:00 and Thursdays 13:15-15:00, both in INM10. Some of these sessions take the form of classic lectures, while others are recitations in which we discuss the week’s readings. The goal of all in-class sessions is to understand in depth the principle(s) of that week, and the connection between it and the concrete instantiations in the assigned readings.

We occasionally assign 1-page writeups called one-pagers (OPs); they are due on Friday night. If, over the weekend, you have new ideas about how to improve your OP, you are welcome to submit an update by Sunday night. However, you must submit a first version by Friday night.

Your grade in the class is broken down approximately as follows: 30% midterm, 40% final, 20% one-pagers, 10% participation and contribution to the in-class discussions.

POCS is a heavyweight course carrying 7 units of ECTS credit (according to the Conférence universitaire suisse, this means 210 learning hours/semester, i.e., 15 hours/week). This course is meant primarily for students who intend to pursue research in the area of systems, therefore you must have a solid systems background. One way to acquire this background is, for example, by taking at least the following:

Without a solid systems background, it is hard to succeed in POCS. If you wish to brave it out despite an incomplete background, please be ready to spend at least 2x more time than the other students in order to acquire, on the side, the necessary background on your own.

Collaboration policy

We encourage you to discuss the reading materials with your peers, but every assignment you turn in must be your own work. You are not permitted to discuss the topic of the OP with other students prior to your or their final submission. Cheating, plagiarism, and any form of dishonesty will be handled with maximum severity. If you are ever in doubt about whether an action on your part may constitute unacceptable collaboration, please ask the course staff before proceeding—doing so afterward is too late.

Syllabus

One-Pagers (OPs)

Below are sample one-page writing assignments; instructions appear at the bottom of this page. After grading the OPs, we select some that stand out in one way or another. These are not “perfect OPs” but rather OPs that put forth a clear design and make for an intellectually interesting read.


OP2 (due 19-Oct-2018)

We want to build an emergency response service (EMS) that enables a user to place an emergency voice call to an operator and satisfies the following requirements: (1) As long as the device (e.g., smartphone) used to make the call can transmit/receive at the rate that is necessary to perform a voice call, the system will reliably deliver the call; (2) If the call is disrupted due to a technical/network failure or the caller being incapacitated, the operator will dispatch emergency help to the physical location where the call originated from. Can we build such a service over the current Internet architecture (i.e., if the caller and the operator communicate only over the Internet)? If yes, describe the architecture of the system and how it could meet the two requirements. If not, explain the minimum changes we would need to make to the Internet architecture (the network stack) in order for the system to meet the two requirements.

  • Matteo Rizzo [view] proposes marking and prioritization of emergency packets, routing of emergency packets through all available routes, and geolocation through link-layer and network-layer extensions. What makes this OP stand out is the clear statements, lack of redundancy, and excellent use of references to support the OP’s position.
  • Aunn Raza [view] proposes DiffServ to identify and prioritize emergency packets, combined with SMS as backup: when the caller cannot communicate with the emergency operator over the Internet, her device simply SMS’s her physical location to the operator, and the operator dispatches help. What makes this OP stand out is the simplicity and practicality of the proposed solution.

OP1 (due 12-Oct-2018)

Linux Kernel Modules are a representative example of soft modularity. Explain why they only provide soft modularity and propose a way to implement enforced modularity for Linux Kernel Modules. Describe the implications of your solution and discuss the associated trade-offs between fault isolation and performance.

  • Sachin John [view] proposes isolating LKMs by virtualizing the LKM/kernel interface via a userspace library
  • Matteo Rizzo [view] proposes to use formal verification to guarantee that LKMs do not escape their module boundary, and relies on a formalization of the interface between the LKM and the Linux kernel.
  • Thanassis Xygkis [view] proposes separate page tables per kernel module, with compiler-enforced switching of the page directory base register upon entry in an LKM, effectively implementing in-kernel processes.
  • Rishabh Iyer [view] proposes to run drivers in user-space processes, then memory-isolate their respective devices via the IOMMU to protect the system from rogue writes, and mirror into user-space the kernel interfaces needed by the LKMs via a duo of an in-kernel proxy plus an in-user-space server process.
  • Aunn Raza [view] proposes to leverage Mondriaan memory protection—a way for protecting domains at finer granularity than address spaces with arbitrary permissions control at the granularity of individual memory locations—as a way to isolate each LKM in its own protection domain without the overhead of address space switching.

Instructions for writing an OP

Use a maximum of 500 words for the body of your writeup; in the words of Antoine de Saint-Exupéry, “perfection is achieved not when there is nothing more to add, but when there is nothing left to take away.” OPs require in-depth consideration of the assigned materials, along with good technical writing.

Your submission must be in PDF and consist of one single-spaced A4 page, including all figures, tables, and references. References should have complete citations at the bottom of the OP, which in turn are hyperlinked to electronic versions of the cited materials, whenever possible. The OP should be single-column and use Times New Roman font with 10-point type or greater. Not respecting these rules will be severely penalized. The title and references do not count toward the 500-word limit.

Submit your OP through the POCS submission system. It must be received by 23:59 CEST on Friday. If you submit on time a first version of the OP, then you get an automatic extension to finalize the OP until 23:59 CEST on Sunday. Please prefix your title with the number of the OP, that is “OP1: Title” for the first week’s OP. Do not write your name on the OP.

Before submitting your first OP, you have to create an account on the system. Registration is straightforward: simply enter your email address and choose “I’m a new user and want to create an account using this email address”. The system will shortly send you an email with instructions on how to complete your registration. Once you register, you should fill in the new paper form.

You are not allowed to discuss the topic of the OP with anyone else until after Sunday. The OP must be 100% your own work.