Proceedings of the
`18th ACM Symposium on
`Operating Systems Principles
`(SOSP’01)
`
`October 21-24, 2001
`Chateau Lake Louise, Banff, Alberta, Canada
`
`Sponsored by ACM SIGOPS
`(Association for Computing Machinery Special Interest Group in Operating Systems).
`
`Supported by Microsoft Research, Intel Corporation, QUALCOMM, Mercury Computer Systems,
`Hewlett-Packard Labs, Akamai, and Inktomi.
`
`CSCO-1046
`Page 1 of 11
`
`

`

`The Association for Computing Machinery, Inc.
`1515 Broadway
`New York, New York 10036
`
`Copyright © 2001 by the Association for Computing Machinery, Inc. (ACM). Permission to make digital or hard
`copies of portions of this work for personal or classroom use is granted without fee provided that the copies are not
`made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the
`first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with
`credit is permitted.
`
`To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/
`or a fee. Request permission to republish from: Publications Dept. ACM, Inc. Fax +1-212-869-0481 or E-mail
`permissions@acm.org.
`For other copying of articles that carry a code at the bottom of the first or last page, copying is permitted provided
`that the per-copy fee indicated in the code is paid through the Copyright Clearance Center, 222 Rosewood Drive,
`Danvers, MA 01923.
`
`Additional copies may be ordered prepaid from:
`ACM Order DepartmentPhone: +1-800-342-6626 (U.S.A. and Canada)
`P.O. BOX 11405+1-212-626-0500 (all other countries)
`Church Street StationFax: ..............+1-212-944-1318
`New York, NY 10286-1405E-mail:acmhelp@acm.org
`
`ii
`
`Page 2 of 11
`
`

`

`DEDICATED TO THE MEMORY OF
`JOCHEN LIEDTKE
`(1953-2001)
`
`Jochen Liedtke, a program committee member of this SOSP, died tragically at Frankfurt Airport on Sunday, June
`10, 2001 on his return from the SOSP program committee meeting. He had been in ill health earlier in the year, and
`had undergone two major surgeries. It would have been easy (and entirely understandable) for him to have declined
`to travel to the meeting. Yet, he was committed to participating fully in the process and travelled across the Atlantic
`to attend. His dedication and sense of duty are truly humbling.
`
`At the time of his death, Jochen was a professor at the University of Karlsruhe in Germany. Earlier, he had been a
`researcher at the IBM T.J. Watson Research Center at Yorktown Heights and at the GMD in Bonn. He is widely
`known in the operating systems community for his contributions to microkernel design and implementation, partic-
`ularly the L3 and L4 microkernels. He was an active participant in the research community, serving on the program
`committees of many conferences and workshops. He served as the General Chair of HotOS-VIII, held in Schloss
`Elmau, Germany in May, 2001.
`
`Jochen is survived by his wife, Adelheid, and many friends and colleagues. The SOSP community is deeply sad-
`dened by his passing, and dedicates these proceedings to his memory.
`
`iii
`
`Page 3 of 11
`
`

`

`Eighteenth ACM Symposium on Operating System Principles
`
`MESSAGE FROM THE GENERAL CHAIR
`
`SOSP has moved back into the mountains, this time to the Chateau Lake Louise in Alberta.
`
`The job of a General Chair is, basically, to worry. The people behind this SOSP were outstanding and
`gave me little occasion to exercise the traditional role of a General Chair. Satya’s vision and hard work
`with his committee has resulted in an excellent program that is both broad and deep. Tom Bressoud as
`treasurer made sure that the financial procedures – from contract negotiation to registration cash flow –
`worked smoothly, and was always ready with the right spreadsheet when I felt my worry level rising.
`Norm Hutchinson is the main reason that the conference is in this beautiful historic hotel and in this stun-
`ning location, and he has managed the logistics wonderfully. Lorenzo Alvisi ran publicity smoothly
`despite the deep nondeterministic mysteries of posting to netnews and the interesting cyber-counterat-
`tacks of those who felt e-mail containing a call for papers were the vilest form of spam. Geoff Voelker
`built and maintained the web registration service while simultaneously serving as SIGCOMM local
`arrangements chair, which should earn him a high place in ACM Heaven, and he kept us all sane in tense
`moments with his good humor. Marvin Theimer organized a strong committee which ably distributed the
`student scholarships, Mike Feeley organized the student help and scribes, and Chris Small once again
`arranged the conference CD-ROM production. We also enjoyed the support from many at ACM Head-
`quarters, and it was a joy to work with the people at the Chateau Lake Louise, most notably Amanda Bur-
`rowes and Joanne Trudeau. Finally, I would like to thank Ava Hristova for her design of the conference
`web page structure, David Kotz for his institutional memory and sound advice, and Stefan Savage and
`Fred Schneider for their advice and humor.
`
`I am very thankful to the companies that contributed to SOSP: Akamai, Hewlett-Packard Labs, Inktomi,
`Intel Corporation, Mercury Computer Systems, Microsoft Research, and QUALCOMM.
`
`Thank you all!
`
`Keith Marzullo
`University of California, San Diego
`
`iv
`
`Page 4 of 11
`
`

`

`Eighteenth ACM Symposium on Operating System Principles
`
`MESSAGE FROM THE PROGRAM CHAIR
`
`At the dawn of the new millennium, it is useful to pause and reflect on the role of SOSP. It is hard to believe that
`SOSP is over 35 years old! The first one was held in 1965, long before many of the attendees of this conference
`were born. In those 35 years, computing has been transformed in ways that were unimaginable back in 1965.
`Somehow, SOSP has retained its reputation as the premier forum for research results in experimental computer sys-
`tems. How has it succeeded in this role for so long?
`
`I believe that there are two reasons. First and foremost is the dedication and hard work of the many individuals who
`have served on the SOSP program committees. These are talented individuals with heavy demands on their time.
`Their willingness to devote a substantial part of that time to the SOSP review process shows their commitment to
`preserving the quality of SOSP. The second reason is SOSP’s broad charter. In spite of the emergence of more spe-
`cialized conferences in areas such as networking, mobile computing, reliability and security, SOSP continues to
`welcome work of the highest quality in those areas. This broad view of experimental computer systems has served
`SOSP well, and will continue to be one of its strengths as we discover further new dimensions to computing.
`
`This year we received 85 submissions: lower than in the past two SOSPs, but well within the observed long-term
`range. We accepted 17 of the 85, and nominated two as award papers to ACM TOCS (“Untrusted Hosts and Confi-
`dentiality: Secure Program Partitioning” and “BASE: Using Abstraction to Improve Fault Tolerance”). All accep-
`tances were conditional, pending successful shepherding by a program committee member. This long-standing
`SOSP tradition has been an important factor in ensuring high quality. The reviewing process we used was a variant
`of one that has worked well in the past. Four program committee members reviewed each paper; each of those
`members also obtained one review from an external reviewer. Thus, most papers received eight reviews. In addi-
`tion, each program committee member was required to skim about half the papers he or she did not review. This
`combination of deep understanding as well as broad familiarity with the submissions led to thoughtful and well-
`informed discussions at the program committee meeting. Some of the negative decisions were painful and heart-
`breaking: we felt that many of the rejected papers showed a lot of promise, and that improved versions would be
`strong future submissions to SOSP or other conferences. Besides the reviewed papers, the conference has three
`invited speakers, a poster session, and a work-in-progress session.
`
`One of the pleasant tasks of the program chair is to acknowledge the many individuals who have helped in putting
`the program together. First, I would like to thank the program committee. I could not have asked for a better group
`of people to work with. They did a huge amount of reviewing, were prompt with their reviews, participated vigor-
`ously in the discussions at the meeting, were fair and balanced in their judgments, and kept an open mind at all
`times. Whenever I needed advice on how to handle a tricky situation, they came through with thoughtful sugges-
`tions and carefully considered opinions. Overall, they were superb custodians of SOSP quality.
`
`I would also like to thank the Publications Chair, Greg Ganger, and his assistant, Joan Digney, for taking care of all
`aspects of producing this document. Their help has saved me a considerable amount of time and attention to detail.
`Chris Small handled the production of a CD-ROM companion to the proceedings, and I would also like to thank
`him. Keith Marzullo has been wonderful to work with as General Chair: prompt in his responses, thorough and
`detailed in his follow up, and always in good spirits. To my administrative assistant, Tracy Farbacher, and my grad-
`uate student, Rajesh Balan, both of whom helped me in countless ways with the logistics of the reviewing process
`and the program committee meeting: a big thank you! The dedication and help of all these people, and many others
`not mentioned here, has made it a pleasure to serve as program chair of this SOSP. It has also been an honor and
`privilege.
`
`M. Satyanarayanan
`Program Chair, SOSP-18
`August 2001
`
`v
`
`Page 5 of 11
`
`

`

`Eighteenth ACM Symposium on Operating System Principles
`
`EXTERNAL REVIEWERS
`
`Ali-Reza Adl-Tabatabai
`Atul Adya
`Bikash Agarwalla
`Adnan Agbaria
`Marcos Aguilera
`Ahmed Amer
`David Andersen
`Andrea Arpaci-Dusseau
`Uwe Assmann
`Benjamin Atkin
`Mary Baker
`Magdalena Balazinska
`Gaurav Banga
`Paul Barham
`Rimon Barr
`Tugkan Batu
`Andy Bavier
`Frank Bellosa
`Chuck Blake
`Bill Bolosky
`Dan Boneh
`Gaetano Borriello
`Aaron Brown
`Barry Brumitt
`Emma Brunskill
`Ken Calvert
`Andrew Campbell
`Miguel Castro
`Ugur Cetintemel
`Fay Chang
`Benjie Chen
`Brad Chen
`Peter Chen
`Yuqun Chen
`Tzi-cker Chiueh
`Michal Cierniak
`Jamieson Cobleigh
`Andy Collins
`Mark Corner
`Landon Cox
`David Culler
`Dorothy Curtis
`Steven Czerwinski
`Uwe Dannowski
`Eyal de Lara
`
`John Douceur
`Fred Douglis
`Richard Draves
`Peter Druschel
`Dan Duchamp
`Kenneth Duda
`Derek Eager
`Keith Edwards
`Greg Eisenhauer
`Daniel Ellard
`Carla Ellis
`Carl Ellison
`Kevin Elphinstone
`Dawson Engler
`Michael Ernst
`Deborah Estrin
`Kevin Fall
`Anton Faradjian
`Keith Farkas
`Nick Feamster
`Jason Flinn
`Liana Fong
`Josh Fryman
`Ayalvadi Ganesh
`Ivan Ganev
`Greg Ganger
`Ada Gavrilovska
`Sanjay Ghemawat
`Vadim Gleizer
`Yitzchak Gottlieb
`Ramesh Govindan
`Paul Graunke
`Steven Gribble
`Robert Grimm
`Mark Gritter
`Dirk Grunwald
`Emin GunSirer
`Frank Hady
`Wei Han
`Steven Hand
`Mor Harchol-Balter
`Gernot Heiser
`Johannes Helander
`Michael Hohmuth
`David Holland
`
`vi
`
`Peter Honeyman
`Ken Hopkinson
`John Howard
`Liviu Iftode
`Rebecca Isaacs
`Sitaram Iyer
`Kyle Jamieson
`John Jannotti
`Minwen Ji
`David Johnson
`Alan Jones
`Anthony Joseph
`Frans Kaashoek
`Scott Karlin
`Terence Kelly
`Minkyong Kim
`Jay Kistler
`Emil Kohn
`Olga Kornievskaia
`Lakshman Krishnamurthy
`Arvind Krishnamurthy
`Geoffrey Kuenning
`Sanjeev Kumar
`Yui-Wah Lee
`Kai Li
`Jorg Liebeherr
`Gerd Lieflaender
`Ada Lim
`Jack Lo
`Darrell Long
`David Lowenthal
`Honghui Lu
`Kostas Magoutis
`Scott Mainwaring
`Durga Devi Mannaru
`David Mazieres
`Patrick McDaniel
`Frank Mehnert
`Mike Mesnier
`Yaron Minsky
`Vishal Misra
`Allen Miu
`Jeffrey Mogul
`Robert Morris
`Hans Mulder
`
`Page 6 of 11
`
`

`

`Eighteenth ACM Symposium on Operating System Principles
`
`EXTERNAL REVIEWERS, continued
`
`Sape Mullender
`David Nagle
`Erich Nahum
`Aki Nakao
`Dushyanth Narayanan
`Badri Nath
`Juan Navarro
`Rich Neves
`Tin-Fook Ngai
`Nathaniel Nystrom
`James O’Toole
`Vivek Pai
`Henrique Paques
`Yoonho Park
`Jignesh Patel
`Arnab Paul
`Vern Paxson
`Trevor Pering
`Karin Petersen
`Christian Poellabauer
`Atul Prakash
`Niels Provos
`Calton Pu
`Xiaohu Qie
`Lili Qiu
`Raj Rajkumar
`Suchitra Raman
`Valentin Razmov
`John Regehr
`John Reumann
`Lars Reuther
`Martin Rinard
`Rodrigo Rodrigues
`Timothy Roscoe
`
`Michael Swift
`Renu Tewari
`Marvin Theimer
`Walter Tichy
`Michael Ubell
`Volkmar Uhlig
`Theo Ungerer
`Amin Vahdat
`Amin Vahdat
`Robbert vanRenesse
`Raj Vaswani
`Vivekanand Vellanki
`Roman Vitenberg
`Geoff Voelker
`Jim Waldo
`Carl Waldspurger
`Limin Wang
`Randy Wang
`Yi-Min Wang
`Roy Want
`Weldon Washburn
`Matt Welsh
`Patrick Widener
`John Wilkes
`Alec Wolman
`Theodore Wong
`Rumi Zahir
`Steve Zdancewic
`Matthew Zekauskas
`Ming Zhang
`Lantian Zheng
`Dong Zhou
`Lidong Zhou
`
`Mendel Rosenblum
`Daniela Rosu
`Marcel Rosu
`Dan Rubenstein
`Algis Rudys
`Yasushi Saito
`Constantine Sapuntzakis
`Stefan Saroiu
`Rick Schlichting
`Brian Schmidt
`Sebastian Schoenberg
`Alper Sen
`Mauricio Serrano
`Srinivasan Seshan
`Konstantin Shagin
`Marc Shapiro
`Liuba Shrira
`Dan Simon
`Ambuj Singh
`Jaswinder Pal Singh
`Espen Skoglund
`Christopher Small
`Frederick Smith
`Keith Smith
`Alex Snoeren
`Tammo Spalink
`Oliver Spatscheck
`Christopher Stein
`Daniel Stodolsky
`Ion Stoica
`Daniel Sturman
`Sree Subramoney
`David Sullivan
`Florin Sultan
`
`vii
`
`Page 7 of 11
`
`

`

`Eighteenth ACM Symposium on Operating System Principles
`
`CONFERENCE OFFICERS
`
`General Chair:
`
`Keith Marzullo, UC San Diego
`
`Program Chair:
`Program Committee:
`
`M. Satyanarayanan, Carnegie Mellon University and Intel Research Pittsburgh
`Hari Balakrishnan, MIT
`Maurice Herlihy, Brown University
`Mike Jones, Microsoft Research
`Monica Lam, Stanford University
`Butler Lampson, Microsoft Research
`Jochen Liedtke, University of Karlsruhe
`Andrew Myers, Cornell University
`Brian Noble, University of Michigan
`Larry Peterson, Princeton University
`Margo Seltzer, Harvard University
`David Tennenhouse, Intel Research
`John Zahorjan, University of Washington
`
`Scholarship Chair:
`Scholarship Commitee:
`
`Marvin Theimer, Microsoft Research
`Cary Gray, Wheaton College
`Sharon Perl, Compaq Systems Research Center
`David Steere, Oregon Graduate Institute
`Werner Vogels, Cornell University
`
`Local Arrangements:
`Publication:
`Finance:
`Registration:
`Publicity:
`Scribes and Volunteers:
`CD ROM:
`
`Norm Hutchinson, University of British Columbia
`Greg Ganger, Carnegie Mellon University
`Tom Bressoud, Lucent
`Geoff Voelker, UC San Diego
`Lorenzo Alvisi, UT Austin
`Michael Feeley, University of British Columbia
`Christopher Small, Sun Microsystems
`
`viii
`
`Page 8 of 11
`
`

`

`Eighteenth ACM Symposium on Operating System Principles
`
`TABLE OF CONTENTS
`
`Trust and Dependability
`
`Untrusted Hosts and Confidentiality: Secure Program Partitioning
`Steve Zdancewic, Lantian Zheng, Nathaniel Nystrom, Andrew C. Myers (Cornell University).........................1
`
`BASE: Using Abstraction to Improve Fault Tolerance
`Rodrigo Rodrigues, Barbara Liskov (MIT), Miguel Castro (Microsoft Research)............................................15
`
`The Costs and Limits of Availability for Replicated Services
`Haifeng Yu, Amin Vahdat (Duke University).....................................................................................................29
`
`Deconstructing the OS
`
`Information and Control in Gray-Box Systems
`Andrea Arpaci-Dusseau, Remzi Arpaci-Dusseau (University of Wisconsin, Madison)....................................43
`
`Bugs as Deviant Behavior: A General Approach to Inferring Errors in Systems Code
`Dawson Engler, David Yu Chen, Seth Hallem, Andy Chou, Benjamin Chelf (Stanford University)................57
`
`An Empirical Study of Operating Systems Errors
`Andy Chou, Jun-Feng Yang, Benjamin Chelf, Seth Hallem, Dawson Engler (Stanford University) ................73
`
`Resource Management
`
`Real-Time Dynamic Voltage Scaling for Low-Power Embedded Operating Systems
`Padmanabhan Pillai, Kang G. Shin (University of Michigan)............................................................................89
`
`Managing Energy and Server Resources in Hosting Centres
`Jeffrey S. Chase, Darrell C. Anderson, Prachi N. Thakar, Amin M. Vahdat (Duke University),
`Ronald P. Doyle (IBM Research Triangle Park)...............................................................................................103
`
`Anticipatory Scheduling: A Disk Scheduling Framework to Overcome Deceptive Idleness in Synchronous I/O
`Sitaram Iyer, Peter Druschel (Rice University) ................................................................................................117
`
`Networking
`
`Resilient Overlay Networks
`David G. Andersen, Hari Balakrishnan, M. Frans Kaashoek, Robert Morris (MIT)........................................131
`
`Building Efficient Wireless Sensor Networks with Low-Level Naming
`John Heidemann, Fabio Silva, Chalermek Intanagonwiwat, Ramesh Govindan (USC/ISI),
`Deborah Estrin, Deepak Ganesan (UCLA) ......................................................................................................146
`
`Mesh Based Content Routing using XML
`Alex C. Snoeren, Kenneth Conley, David K. Gifford (MIT) ...........................................................................160
`
`ix
`
`Page 9 of 11
`
`

`

`Eighteenth ACM Symposium on Operating System Principles
`
`TABLE OF CONTENTS, continued
`
`File Systems
`
`A Low-Bandwidth Network File System
`Athicha Muthitacharoen, Benjie Chen (MIT), David Mazières (NYU)...........................................................174
`
`Storage Management and Caching in PAST, A Large-scale, Persistent Peer-to-peer Storage Utility
`Antony Rowstron (Microsoft Research), Peter Druschel (Rice University) ....................................................188
`
`Wide-Area Cooperative Storage with CFS
`Frank Dabek, M. Frans Kaashoek, David Karger, Robert Morris (MIT), Ion Stoica (UC Berkeley)..............202
`
`Event-Driven Architectures
`
`Building a Robust Software-Based Router Using Network Processors
`Tammo Spalink, Scott Karlin, Larry Peterson, Yitzchak Gottlieb (Princeton University)...............................216
`
`SEDA: An Architecture for Well-Conditioned, Scalable Internet Services
`Matt Welsh, David Culler, Eric Brewer (UC Berkeley) ...................................................................................230
`
`x
`
`Page 10 of 11
`
`

`

`Eighteenth ACM Symposium on Operating System Principles
`
`AUTHOR INDEX
`
`Andersen, David G. .............................................. 131
`Anderson, Darrell C. ............................................ 103
`Arpaci-Dusseau, Andrea ........................................ 43
`Arpaci-Dusseau, Remzi.......................................... 43
`Balakrishnan, Hari................................................ 131
`Brewer, Eric ......................................................... 230
`Castro, Miguel........................................................ 15
`Chase, Jeffrey S.................................................... 103
`Chelf, Benjamin ............................................... 57, 73
`Chen, Benjie......................................................... 174
`Chen, David Yu ...................................................... 57
`Chou, Andy ...................................................... 57, 73
`Conley, Kenneth ................................................... 160
`Culler, David ........................................................ 230
`Dabek, Frank ........................................................ 202
`Doyle, Ronald P.................................................... 103
`Druschel, Peter ..............................................117, 188
`Engler, Dawson ................................................ 57, 73
`Estrin, Deborah .................................................... 146
`Ganesan, Deepak.................................................. 146
`Gifford, David K. ................................................. 160
`Gottlieb, Yitzchak ................................................ 216
`Govindan, Ramesh ............................................... 146
`Hallem, Seth..................................................... 57, 73
`Heidemann, John.................................................. 146
`Intanagonwiwat, Chalermek ................................ 146
`
`Iyer, Sitaram.......................................................... 117
`Kaashoek, M. Frans ...................................... 131, 202
`Karger, David........................................................202
`Karlin, Scott..........................................................216
`Liskov, Barbara.......................................................15
`Mazières, David....................................................174
`Morris, Robert ..............................................131, 202
`Muthitacharoen, Athicha ......................................174
`Myers, Andrew C. ....................................................1
`Nystrom, Nathaniel...................................................1
`Peterson, Larry......................................................216
`Pillai, Padmanabhan ...............................................89
`Rodrigues, Rodrigo.................................................15
`Rowstron, Antony.................................................188
`Shin, Kang G...........................................................89
`Silva, Fabio ...........................................................146
`Snoeren, Alex C....................................................160
`Spalink, Tammo....................................................216
`Stoica, Ion .............................................................202
`Thakar, Prachi N. ..................................................103
`Vahdat, Amin M. ............................................ 29, 103
`Welsh, Matt...........................................................230
`Yang, Jun-Feng .......................................................73
`Yu, Haifeng .............................................................29
`Zdancewic, Steve......................................................1
`Zheng, Lantian..........................................................1
`
`xi
`
`Page 11 of 11
`
`