Final projects may be undertaken in teams of two (or more) students. Teams of two can form without any consultation from me. However, if you have a project that you feel warrants more participation, please check with me first. Projects may also be undertaken on cooperation with other graduate courses, but any such project must be approved by the professors of both courses. Not surprisingly, we expect more depth and work for a project that is satisfying two class requirements. Similarly, if you wish to undertake a project related to your own research, I will permit it, but you must demonstrate how what we've learned in CS261 influences your work and/or ways in which your research would have been different had you not been also conducting a project in CS261. In other words, your project in CS261 must extend work you would normally have done in some new and/or diferent way.

Project Proposal and Research Plan (20%)

The proposal part should be a single page that describes your project. You should clearly motivate and state the research question you are investigating. Provide a few sentences of explanation about why you think this is an interesting question, why it is important, and how it qualifies as research.
The research plan is a more comprehensive document. It should include the following components (the numbers in parentheses are an indication of an estimate of the number pages that you might need for the section).
• Related Work (2): Related work falls in two categories. Background readings are those that are required for you to understand the area and problem you are attacking. By the time you complete your proposal, I expect that you have both identified and completed the background reading. You should be able to explain the background in sufficient detail that any of your classmates would understand what you are doing and why. The other category of related work I call contextual work. This includes prior work upon which you are building (if it wasn't needed in the background), the work of others who are solving the same problem you are, but doing so in different ways, work in adjacent areas that influences what you've done. The purpose of this part of the related work section is to help a reader place your work in the research landscape and truly understand your results. You need not have conducted an exhaustive literature search, by the time that you submit the proposal, but you should know what work is out there and at a minimum, in what areas you need to be looking. Consider this: You need to know that you are undertaking new research and not merely repeating assignment 1 -- doing something someone else has already done. If you are not familiar with the related work, you have no way of knowing this. Understand that this means that by the time you submit your proposal, you have a concrete idea of both the problem and how you are tackling the problem.

  If you think earlier related work is flawed and want to correct those flaws, this would be the section where you describe that. Even if you have not yet read all the papers you intend to read, this section should include a bibliography of papers that you intend to read (but the list of papers should not be the only content of this section). Be sure you include papers outside our own reading list.

• Conclusion Format (<1): What sorts of conclusions do you expect to state? Obviously, you do not know what the results are in advance, but you should know the format of those results. For example, if you are comparing two systems, you would expect to be able to say things like, "System A outperforms System B in these instances and System B outperforms System A in these other instances." Naturally, after you have done the research, you should also be able to explain why. You might provide some template sentences that you expect to have in your conclusion (and/or abstract).
• Experimental Setup (1-3): What experiments will you conduct? Why? What question is each experiment designed to answer? What do you hope to learn from each experiment? What measurement tools will you use? How will you determine if your measurements are accurate? What tests will you conduct conditionally? (For example, if we learn X from experiment 1 then we must do A else we'll do B.) What problems do you expect? The more detail you include in this section, the more able I will be to give useful feedback and the more easily you will be able to conduct your research. Think hard about what the important questions are and how you can answer them, and then map those questions and answers back to explicit tasks. Resources Needed (<1): What equipment, software, tools will you need? This section is particularly important so that I can make sure we have the right stuff available. If you have any doubts about the availability of the resources you'll need, please speak to David as soon as possible! You do not want to find out in the middle of November that the hardware and/or software you need is not available!
• Schedule (< 1): (be specific; include dates and milestones).

Status Meeting

I encourage you to come to office hours and talk to me about your project or schedule other meetings with me as the need arises. At a minimum, I want to meet with you twice before the extended abstract is due. One of those meetings must happen before the end of the week of October 13 and the other must happen before the end of the week of November 13. Note that I am traveling October 25-28 and that University accreditation (for which I am the chair) will happen October 19-21, so I may not be as available as I normally would be. These meetings are for your benefit. I expect to answer questions you may have, ask you questions about what you've done, brainstorm about what to do next, etc. If you haven't done anything, you will get little value out of these meetings. Come with questions I can help you answer.

Rough Draft (30%)

This is the version of the paper that we will review at the "Mock Program Committee." You should have all (or at least most) of your research completed by this point. The rough draft should contain all the parts of the paper, although it may have prepliminary results and may be missing some results. It should contain a complete introduction, background, description of your research, related work, and (preliminary) conclusions. It should contain the entire structure of the results section, even if there are still some missing results. You should be able to write significant parts of this immediately after your project proposal is turned in, so please, please, please don't write this all the night before it is due. The better and more complete the rough draft, the more valuable the input that I and your classmates can give you.

In-class Presentation (10%)

Each group will present a short talk on their research during class on November 24. (Depending on the number of groups, we might have to schedule additional time.) You should plan on approximately a 10 minute presentation and 2-5 minutes for questions and answers. You can think of the in-class presentation as being a short conference presentation. You will not have time to present all the details and subtleties of your work, but you should be able to motivate the audience and explain the important results of your work. After your presentation, your classmates should want to read your final report. The presentation is a great way to make sure that they understand what you're trying to do, so that there is no confusion when they read/review your project.

Final Report (40%)

The final report is a research paper. I expect that most reports will be approximately 10 - 15 "Conference pages" including graphs, tables, diagrams and reference. You should complete the writing early enough that you have time to reread your work and critique it with the rigor that you applied to Assignment 1. Be honest. State shortcomings in your work. Discuss follow on projects. I expect that several of these reports will be suitable for submission to a conference (the USENIX Annual Technical Conference deadline is in January), and I will be happy to work with you to turn them into submissions.

Part of your final report grade will be based upon how well you address comments raised by the program committee. Do not ignore my and the reviewer comments!

Project Suggestions

1. The work can reasonably be completed in two months.
2. We have the required hardware and software in-house to enable you to conduct the necessary research.
3. The research question has something to do with operating systems (I'm willing to give a fair bit of freedom here, but if there are any questions, please check with me).
4. The project is structured in such a way that you can have tangible results. (No big idea papers probably.)
5. You will learn something from undertaking this project.

Optimizing space utilization versus reproduction

Imagine that you could recreate any piece of information on your disk. If you could, your system decide dynamically and adaptively whether to store the actual bytes of an object or merely store the "recipe " for how to reproduce the data. One representation consumes space, but not processing time; the other consumes processing time, but less space.

Systems that capture provenance, such as our own PASS system, often retain enough information to let you reproduce objects.

Using PASS as your substrate, design, implement, and evaluate a system that dynamically and adaptively trades off disk space for computation in the manner described here. You will need to augment PASS to store execution times of processes (I think), but once you have that, you can begin developing algorithms to decide when to retain data and when to make it available via recomputation. You will need to figure out exactly how to represent such objects in the file system (that is, they should appear in the file system, but when you open them, you may have to execute one or more processes to create the actual data).

Using Provenance to solve OS Problems

This is a generalization of the last project.

There are many systems papers of the form, "We wanted to solve some problem, so we modified the kernel to produce a bunch of data, and then we used that data to do something." I'd like to see how many of these projects could be done simply by mining the provenance data that our PASS system collects (You will want to go read the PASS paper now, if this is at all interesting. You can find it at: http://www.eecs.harvard.edu/syrah/pass/pubs/usenix06.pdf.)

1. For example, prefetching files requires that you know what files are likely to be accessed, before programs actually access them -- PASS captures much of that data. So, see if you can replicate the work in "An Analytical Approach to File Prefetching (1997 USENIX)" using PASS. Here are other papers on file prefetching to examine:
   • Marginal Cost-Benefit Analysis for Predictive File Prefetching (ACSME 2003)
   • Design and Implementation of Predictive File Prefetch ing (USENIX 2002)
2. Another area where provenance might be useful is in cache replacement algorithms -- if you knew what you might need again soon, you would keep it in your cache. Look for papers on caching, such as:
   A study of integrated prefetching and caching strategies (Sigmetrics PER 1995).
   • Informed prefetching and caching (SOSP 1995)
   • Application controlled prefetching and caching (USENIX 2002)
3. A PhD thesis by Somayaji (from UNM) showed that short sequences of system calls can be used to "fingerprint" applications. By noticing unusual system call sequences, he was able to perform intrusion detection (and correction). Could provenance by used in a similar manner? What kinds of fingerprints could we create/monitor?
4. The Coda file system was designed to help users work in a disconnected mode. One component of that system was a hoarding mechanism where the system would try to figure out what files you were going to need to function while disconnected. It seems that one could exploit provenance to perform better hoarding. Do it!
5. Any other piece of work that requires collecting data that we already collect in PASS. Be creative!

Warning: I have a strong vested interest in this project. The upside is that you are likely to get lots of attention; the downside is that you are likely to get lots of attention.

But seriously, I would like to see multiple groups attack different aspects of this problem, and then I'd like to write a BIG paper about all the wonderful uses of provenance. So, if you're looking for a publication, this is the project for you.

Enhancing the User Experience via Thumbnails

Users are frustrated by the current experience of downloading, browsing, and exchanging files in ad hoc, low bandwidth networks, such as wireless networks. One improvement to this experience is to let users first interact with local, lossy versions of files before fetching complete files. These lossy versions, or \emph{thumbnails}, can be sent quickly over the network to augment traditional metadata such as file names and ownership.

In low bandwidth environments, thumbnails must be generated at the server. In prior work, an application program running on the server generated thumbnails in response to users' requests. In contrast, you might extend the underlying file system to support direct storage of thumbnails, just as human-readable names and ownership are included today. Making thumbnails first class objects linked directly to their lossless version might enable consistency guarantees and comparison of objects via thumbnails.

This project would extend prior work by a former student here. Consult the following reference and then design, implement, and evaluate a system that provides the services described therein. Jonathan Ledlie, File System Support for Low-Bandwidth Thumbnails, Nokia Research Technical Report NRC-TR-2008-004, May 2008.

Analyzing Data Distributions

We can gain access to the collection of hash values for every 4 KB block in the National Software Reference Library (NSRL). Using these hash values, you can compute the number of unique hashes, the distribution of duplicate hash values, etc. This seems like a rich source of interesting data. Using this data, the following projects might be interesting.

Evaluate Deduplication Strategies

It turns out that file systems contain many (many) copies of identical objects or even pieces of objects (blocks). As a result, many storage vendors provide deduplication capabilities, storing each block once and reference counting it. Research how various vendors perform deduplication; use the database to simulate various algorithms and compare, contrast the performance and/or efficacy of the different approaches.

Develop models of data duplication in file systems

Imagine that you wanted to build an image of a real file system. That file system would contain some number of duplicate blocks. How many? How should you distribute them?

Build a model for constructing a realistic file system image including duplicated data. Test it on some real file systems. You might want to pursue this by extending the Impressions tool.

Develop stragegies for extracting file type distrubutions from file systems via random sampling

Generating realistic file system images requires understanding the distribution of different types of files on a system. Obviously, one could simply read every file on the system and create a representative distribution, but can we do better? Develop an efficient, random-sampling based approach that still produces "good" Distributions

Cloud Architectures

Users are moving computation into the cloud, but it's not clear how we should decompose services in a cloud-based world. Devise a framework in which to ask the question, "What is the best way to decompose services in a cloud-centric world?" Then conduct experiments to address the question.

Cloud OS API

Today's cloud offerings have been packaged as services. If all computing moves to the cloud, perhaps the cloud ought to offer a broader API, closer to that of an operating system. Develop a framework in which to ask the question, "What is a reasonable set of APIs that cloud providers should export?" Figure out a way to actually evaluate the answer to this question. (This is still quite vague and will require some work to turn into a concrete proposal.)

The Future of Computing

It seems that there are two opposing models for what computing is going to look like in the next decade. One model suggests that we are moving to the cloud. All data and computation will be performed remotely, on large commercially run compute and storage servers (think Amazon Web Services). The other model suggests that you will carry your entire collection of data around with you on a mobile device -- iPhone, BlackBerry, Treo. That device will have significant computational power, but more importantly, it will seamlessly and easily allow you to use any display on which to work.

Explore the design space for these two models of computing. The first is pretty easily specified today using existing services. The second will require some work -- what research remains to be done? How much of that work could you do this semester? How will you evaluate the two models?

The outcome of this project ought to be a prediction with evidence to back it up.

How Relevant is System/161 for Systems' Research

Because it's simple inside, System/161 has proven a useful tool for kernel prototyping. However, because of that same simplicity it is difficult to evaluate kernels running on System/161. Evaluate how performance under System/161 relates to performance on real hardware. Absolute performance is less interesting than relative performance: how well do speedups measured under System/161 relate to speedups measured using real hardware? You might want to consider some of the following questions:
• Is the lack of DMA support in System/161's system bus a major problem?
• Would it be worthwhile to switch to a better disk mod el (e.g. CMU disksim)?
• Would it be worthwhile to add a processor cache modeler?

Microkernels Reinvented

The ubiquity of multicore processors introduces the possibility that the microkernel architecture, where OS services are provided by a set of specialized cooperating processes might make sense again. It would be interesting to explore this question. You might take any of several different approaches:
• If we used a microkernel, could we use smaller cores and tiny processes (e.g. use a 16-bit architecture that would save power and facilitate many more cores on a chip)?
• Can we get better parallelism out of a microkernel than a monolithic kernel on a chip with multiple thread contexts? Does this perform better than some of the specialized OS structures being proposed?
• Would a microkernel architecture be able to do a better job of addressing the memory bottleneck?
Pick one or more question like this and figure out how to answer it. You might find simulators such as SIMICS useful.

Building an overlay to detect Censorship versus IT Failures

There is an interesting project at the Berkman center called, Herdict that allows users to notify them when it appears that sites are being blocked. However, users reporting blockages have no way to differentiate technical failures (e.g., Google is down for everyone) versus true censorship.

However, imagine that you had a set of machines distributed around the world and when someone reported a blocked site, you could proble the site from a vareity of sources around the world in an attempt to differentiate technical failures from true censorship.

Using Planetlab (a worldwide network of machines availble for research), design, build, and evaluate an overlay for this purpose. Some of the interesting questions is how you decide which nodes should probe a potentially blocked site and how you interpret your results. Ideally the actual construction of the overlay shouldn't require significant research, but should be an educational and entertaining experience.

Make Impressions Really work

Most of you who used the Impressions paper for your first assignment really liked the paper and were extraordinarily disappointed with the tool itself. Let's fix that (I agree that it would be a useful tool).

In particular, let's see if we can get the constraint problem working so you create file system images of the right sizes. Also, I'd like to see if there is a way that we could allow different kinds of distributions for the various parameters rather than assuming that *all* file systems follow the same kinds of distributions as the Microsoft ones. This would require analyzing a bunch of file system disk images and creating distributions for them and then seeing what the different distributions we want to support are. Finally, augmenting the tool so that it would take data from a real file system and spit out an Impressions parameter file (well documented) would be incredibly useful. In other words, let's take all your criticisms and use them to generate a really, really cool tool.