Project

Assigned

Proposal – March 13, 2019
Implementation, Report, and Presentation – April 8, 2019

Due

Proposal – April 5, 2019 by 10:30pm
Presentation – May 8, 2019 by class time
Implementation and Report – May 13, 2019 by 10:30pm

As part of this class, you will conduct a small-scale systems research project. While your project will necessarily be smaller than the multi-year efforts that lead to some of the papers we read, it will have many of the same elements as a larger scale project.

Project Requirements

Your project will need to satisfy the following requirements:

Identify a Problem: You will need to select an important problem from systems research that you can focus on.
Identify a Creative Approach: Propose a technique for solving the problem you have identified. The problem you select may be too large to solve in a few weeks, so think about how you can scale down the problem to a size that is manageable. The approach you choose could be your own idea, or you can choose an idea from the research literature that you will implement.
Implement your Solution: Turn your approach into a working system. This is where you will spend much of your time. It is a good idea to think through how you could implement an approach before you commit to it. It’s a great idea to have several possible routes to a solution in mind.
Evaluate your Work: Test your implementation. That means making sure it works in the cases you expect it to, but you will also need to measure the system in some meaningful way. Asses its overhead, the specific issues it can solve, the cases where it cannot solve a problem, and so on.

Project Proposal

We will begin the project with a proposal. Your proposal will be in the form of a short written report, with some supplementary material.

A description of the problem you have identified.
A description of your approach, along with a simple example that illustrates how that approach could solve a small instance of the problem you have identified. You may have noticed that many of the papers we read include such examples in their introductions. Think of this as your very first test case.
A short description of how you plan to evaluate your system, assuming you are able to implement your system as planned.
A list of at least four papers that you believe are relevant to your work. These papers may use similar techniques, address similar problems, or may in fact be the source for the technique you will implement. You should list the paper’s title, authors, and other citation information. Please also include a few sentences that explain what the paper is about and how it relates to your work.
A small piece of code that illustrates the first technique you will need for your implementation. For example, if your project was to use ptrace to sandbox running programs, a piece of code that runs a program and shows that you can catch system calls would be a suitable starting point. Use this as an opportunity to make sure you understand the mechanisms you will be using to complete your implementation. Include comments or a description in your proposal text so I understand how this piece fits into your larger system.

There are now length requirements for your proposal. I will evaluate your work based on how clearly you address each of the requirements, so be as detailed as you can, but try to save some of the technical detail for later stages. Your proposal is due at the end of week 9. We will spend time in class discussing interesting problems, but you should plan to spend time during break thinking about your project. The small implementation tasks and writing should be manageable during week 9, so you do not need to spend your break writing and coding.

Preparing for the Project

We’ll spend some time in class discussing important problems in systems, strategies for completing a successful project, and how to find relevant papers. Details will appear below.

Problems in Systems

What are some basic, open problems in systems research?

Concurrent programs have special bugs. How can we check for them?
Memory errors are bad. How can we find and/or prevent them?
Systems crash. How do we tolerate that?
Distributed systems create parallel timelines. How can distributed components agree on anything?
Programs that run slowly are bad. What information should a programmer be able to get so they can improve their programs?
Programs are insecure. How can we make them secure?
Increasing the scale of a system changes its characteristics. What trade-offs make sense at larger (or smaller) scales?
It’s hard to write programs with threads. What is the right paradigm to implement a parallel program?
It’s hard to understand parallel programs’ performance. How can we find the bottlenecks so we can fix them?
Debugging is hard. How can we improve debugging tools?
Error messages are confusing, especially when they’re about types. Can we give better information when a program does not compile?
It is hard to visualize large linked data structures. Can a tool help with this?
Reverse engineering is hard. Can we learn something about a program from its machine code, memory, etc?
Managing networks to distribute load and avoid bottlenecks is hard. How can we help?
Storing data reliably is important. Can we build fast, reliable storage systems?
Storing multiple versions of a file when multiple users are editing them is hard. Can we do better than git?
Programmers struggle to understand where memory lives in a program’s address space. Can we give better information about this?
It’s hard to manage memory correctly in C. Can we provide useful tools to make it easier, or fix/catch problems?
Lots of systems use key-value stores. How can we make them super fast?
Network access is controlled within some countries. Can systems help people in these countries access the outside world, possibly anonymously?
Little annoyances get in the way of the software developer workflow. Can we improve the tools developers use?

Where can we find papers in OS?

There are many conferences and workshops in OS research, but you should be able to find many good papers by focusing on just a few:

USENIX Symposium on Operating Systems Design and Implementation (OSDI): This conference runs in even-numbered years, and is one half of the top-tier venues for OS research. You can find the list of papers at OSDI by searching for “OSDI 2016” or some other year.
ACM Symposium on Operating Systems Principles (SOSP): SOSP runs in odd-numbered years, and is roughly equivalent to OSDI in its prestige. You can find the list of papers the same way, though these papers will be hosted on the ACM Digital Library. To access papers from off campus you can use the Grinnel library proxy. If you are attempting to access a paper at https://dl.acm.org/path/to/paper, change the URL to http://dl.acm.org.grinnell.idm.oclc.org/path/to/paper. You will need to log in with your Grinnell account, and then you will be forwarded along to the paper.
Subject-Specific Conferences: There are many workshops or smaller conferences in the general area of systems, but a few to look at for ideas are HotOS (general OS work), PPoPP (about parallel programming), and ISMM (memory management). FAST is a high-profile conference that focuses on storage, so if you are interested in a storage project you should look here.
Programming Langauges Conferences: Work in programming languages is often relevant to operating systems. We’ve read a number of PL papers that could easily have appeared in an OS conference. Conferences to look at are PLDI and OOPSLA, which both include a mix of more formal or theoretical work as well as some engineering-focused work that may be helpful.

Project Implementation

The largest component of this project is the actual implementation. You are free to divide up the implementation work as you see fit, and you are welcome to use the language(s) of your choice, provided you are still able to use them to complete your project. Every group member must play a significant role in the implementation, but you are welcome to divide up implementation tasks.

Your implementation will be evaluated using several criteria:

Is the code clearly written and commented?
Does the code check for errors whenever appropriate?
Does the code compile without errors or warnings?
Does the system work?

While the first three pieces should be easy to evaluate, it may be difficult to say whether your system works. Two weeks is a very short time for a large implementation project, so I understand that you may run into issues and your plans could change. I have tried to offer advice about which parts you could drop if you run into issues in my proposal feedback, but if you hit a major roadblock and need to change your project I am happy to help.

To show that your system works, you must provide a README file that precisely describes the basic use of your system, including both general instructions and a specific example that walks through an interaction with the system and the expected output. Your implementation must also include all necessary source and data files and a Makefile that allows me to build your project with the make command. If building or running your project requires any additional software or configuration beyond what is available on MathLAN, please make sure to document these dependencies so I will be able to run your project.

Project Report

Your report must give an overview of your system, describe the design and implementation of the system, and finally present an evaluation of your work. This report should cover all of the information from your in-class presentation, with an additional level of detail. A report that earns an A would include sufficient detail for me to re-implement your system without seeing your code or presentation, while also conveying the high-level ideas underlying your system.

Your report will need to include the following sections:

Section: Project Overview

Give a brief overview of your system’s design, the high level points of your implementation, and summarize your evaluation strategy and results. Your overview will serve as an introduction for your project; make sure it is clear what you tried to do, why you did it, and how you know it worked. You can go into detail in later sections, so keep this section brief; 500 words is a good target length.

Section: Design & Implementation

The design and implementation section should explain the structure of your system and, importantly, the rationale for that structure. Design decisions include details like the data structures and algorithms you used, the places where you used concurrency or decided to run code on the GPU, and any libraries you may have used for your implementation.

Try to organize this section in a top down manner: introduce the major components of your system, outline the responsibilities of each component, and then jump into the specifics of each component. You may want to repeat this process for sub-components if there are reasonable logical divisons within the major pieces of your project.

Another strategy for organizing this section would be to break it down by concerns. System concerns include updating a file index in response to a file deletion, maintaining game state over a network connection, or other general requirements that may not map to specific units of code in your system. If you can identify a handful of high-level concerns it may make more sense to discuss the overall implementation structure and then describe how each concern fits into this structure.

Section: Evaluation

You are required to present an evaluation of your system. The details of this evaluation will depend on your project topic, but there are a few common requirements. First, you must describe the experimental set-up; this includes the hardware and software you are using for the evaluation, versions of any important software tools (including libraries), and the methods you use for gathering data (e.g. we measure execution time using the time command). Then, you should measure an appropriate aspect of your system’s behavior while varying some aspect of the load on your system or its environment. Make sure your evaluation section explains what you are trying to measure and discusses an interpretation of your results. If you are unsure what you can measure about your intended project I am happy to discuss possible approaches with you.

When appropriate, your evaluation should include graphs to show the results of your evaluation. Graphs may not be appropriate for all evaluations, so feel free to be creative in how you present the findings from your evaluation.

Project Presentation

Presentation times will depend on the number of project groups, so check back for more details. Regardless of the available time, presentations must answer the following questions:

What is the problem you are trying to solve?
Why is this problem important?
What is the high-level approach you are taking with your solution?
How did you implement that approach?
Was your project successful?

While you do not need to go into detail about the code you wrote for your implementation, you should try to give us enough information that we understand both the conceptual design of your system and some of the interesting technical challenges you faced during your implementation.

For part five, it’s not enough just to report that your system was successful. You should show us your evaluation, discuss the results, and argue for your interpretation of these results. Remember to relate the evaluation back to the original purpose of your system.

All group members must participate in the presentation, but it is up to you to decide how to divide the presentation topics.