Monday, October 12, 2009

SOSP 2009, Day One

I'm in Big Sky, Montana for SOSP 2009 -- widely considered the premier conference on systems. The location is stunning although it's bitterly cold here; I was not ready for this kind of weather for a couple more months. This seems to be the biggest SOSP ever with more than 500 people registered; the last SOSP had a mere 471 attendees. I am not sure what this means. The number of paper submissions has not been going up dramatically, so it's hard to tell if this represents an increasing interest in systems as a field. This year there are a number of co-located workshops, and perhaps with the weak economy people are concentrating their conference travel to focus on fewer high-impact events.

Best paper awards went to three papers: FAWN, RouteBricks, and seL4. These papers all represented a substantial amount of work and have a remarkable number of authors; they are not the kind of papers that were dashed off in two weeks by one or two grad students!

Below are some of the highlights from Day One.

Barbara Liskov - ACM Turing Award Lecture, "The Power of Abstraction"

Barbara used her Turing Lecture as an opportunity to survey the development of Abstract Data Types, CLU, and type hierarchy. It is remarkable how much impact these ideas have had on modern programming languages and practice; Java, C#, Python, and many other languages are the direct descendants of this work. She spend a considerable amount of time talking about the context of programming practice before ADTs were developed, and the issues that computer scientists were concerned about (program structure, control flow, and global state). She surveyed a lot of classic papers -- Dijstra, Wirth, Parnas, and others -- that led to the development of ADTs.

After talking about the mechanisms in CLU, Barbara spent some time reflecting on the current state of programming practice. According to her, modern languages (like Java and C#), but the state of programming is "lousy" -- many untrained programmers developing Internet and browser-based systems rife with things like global state. She wrapped up the lecture by pointing the way to some future opportunities in large multicore systems and reasoning about the semantics of programs running across the Internet.

FAWN - A Fast Array of Wimpy Nodes

The premise of this paper is that it is possible to reduce the power consumption of data centers by an order of magnitude by leveraging much more power-efficient hardware. The idea is to focus on
queries per joule as the metric, rather than simply peak performance. They propose a cluster of inexpensive, power-efficient nodes (based on the AMD Geode platform with a small amount of memory and Compact Flash rather than hard disks) and develop a key-value store application. The system has to address the limited memory on the nodes, the need to minimize random writes to the flash (using a log-structured data store), and the need to add or remove nodes from the cluster (using consistent hashing for lookups and migrating data in background tasks). Among other things, the paper shows that the FAWN prototype can sustain around 350 queries per second per Watt, compared to around 50 queries/sec/W for conventional hardware. They also do a nice analysis of total cost of ownership and talk about the regime (in terms of load and data set size) where FAWN makes the most sense.

The Multikernel: A New OS Architecture for Scalable Multicore Systems

This paper is about revamping the design of OS kernels to account for massively multicore systems with heterogeneous hardware (CPUs, GPUs, programmable NICs, and FPGAs). The key idea is to shift away from a single kernel with shared memory and locks on shared data structures over to running a separate kernel on each core, using message passing as the only coordination primitive between cores. This approach allows one to design interprocessor communication protocols that leverage the topology of the underlying interconnect, which can vary substantially between platforms. In the MultiKernel design, all shared state is treated as replicated across cores and mechanisms for explicit replica management (which are typical in distributed systems) become necessary. The authors have implemented a prototype of this design, called
BarrelFish, and demonstrated its scalability as the number of cores is increased. This is a really nice piece of systems work and is a classic example of "from scratch" OS design to leverage new hardware trends.

Both the MultiKernel and FAWN papers were presented in an earlier form at HotOS 2009, which I have blogged about earlier.

Debugging in the (Very) Large: Ten Years of Implementation and Experience

This paper from Microsoft deals with Windows Error Reporting, which is the largest client-server system in the world by number of installs. WER receives 100 million error reports a day, across 17 million different programs, across a billion or so installed clients. It's been in operation for 10 years and has led to thousands of bugs being fixed, and has fundamentally changed how Microsoft approaches software development. Galen Hunt from MSR gave a great talk on this system.

The system automatically collects "minidumps" from clients when errors occur, which are then classified into buckets by the back-end servers using a variety of statistical analyses. The bucketing strategy takes into account the program name, version, and symbol in which the program crashed. Doing statistical analysis on so many error reports allows them to narrow in on the bugs that affect the most users and therefore concentrate bug fixing efforts. Galen talked about some of the successes of this system over the years, including identifying 5-year-old heisenbugs in the Windows kernel; detection of widespread malware attacks; and even finding bugs in hardware (such as a broken USB controller that did not implement DMA correctly). This is a great paper on a large, real-world system.

I'll blog about the BOFs, banquet, and award ceremony tomorrow.


  1. How different did the FAWN and MultiKernel papers need to be to appear in both conferences. I'm not criticizing, just curious as this is an issue in my field for workshop to conference papers (why I no longer submit ANYTHING to a workshop) and I'm curious about conference to conference.

  2. Well, the HotOS papers were technically "position papers" without a lot of technical detail or evaluation, but it's true that there is a lot of overlap between them. SIGOPS' policy towards HotOS is that it is generally acceptable for a HotOS paper to represent an early form of a later SOSP/OSDI/etc. submission. Indeed, by the time HotOS was happening, the SOSP papers would have already been written and submitted.

    I happen to be the program chair for HotOS in 2011 and one thing I plan to look at is this issue!

  3. This is a great report for those unable to attend.
    I plan on visiting regularly the next couple of days.

    Thank you and please keep up the work!

  4. Thanks for your post! Looking forward to read more.

  5. Very nice - easy to follow, simple, and working. Thanks for the knowledge!
    More templates easy to download