(HotOS'03 Note)Crash-Only Software

Crash-Only Software
George Candea et al.
HotOS 2003

作者认为所有软件都会crash，不能避免crash，就crash-only。这样，软件要么成功，要么crash，不会存在“带病运行”等中间情况，从而可以简单的使用重新启动的方法来进行错误恢复。Candea等在OSDI 2004中有一篇关于Microreboot的文章，就是在此基础上深入的。

Crash-only systems are built from crash-only components, and the use of transparent component-level retries hides intra-system component crashes from end-users.

文中介绍了实现crash-only的一些准则：
Intra-component:
1. All important non-volatile state is managed bye dedicated state stores.
Inter-component:

1. Components have externally enforced boundaries;


2. All interactions between components have a timeout;


3. All resources are leased;


4. Requests are entirely self-describing.

(HotOS'03 Note)Virtual Appliance in the Collective: A Road to Hassle-Free Computing

Virtual Appliance in the Collective: A Road to Hassle-Free Computing
Constantine Sapuntzakis and Monica S. Lam
HotOS 2003

本文介绍了Monica阿姨小组研究的Collective项目的核心思想Virtual Appliance。

Virtual Appliance基于VMM，将用户需要的功能封装成一个个独立的VM，成为Virtual Appliance。就好像PS2只用来打游戏一样。

这样做的动机主要是降低计算机的使用维护压力，方便用户使用等。我认为和Thin-client的思想相似，不过由于在服务器端使用了VMM，可以进行更好的隔离和QoS保证。

当然，Monica阿姨做这些东东也不奇怪，她是Brian K. Schmidt的导师，而后者的博士论文Support Ubiquitous Computing With Stateless Consoles and Computation Caches总结了SunRay的工作，是Thin-client方向的重量级论文。还有，现在带领哥伦比亚大学NCL(Network Computing Lab)专门研究Thin-client的Jason Nieh，“聂哥”，也是Monica的学生。

这篇论文主要还是介绍Collective的目标、出发点和基本思想。要进一步了解还是要看相关论文。

另外，前两天看Monica的主页，发现她们在Collective的研究基础上创立了一个公司，Moka5，产品叫livePC，试用版本还没有出来……

(HotOS'03 Note)Development Tools for Distributed Applications

Development Tools for Distributed Applications
Mukesh Agrawal and Srinivasan Seshan
HotOS 2003

考虑支持分布式应用开发的整个生命周期的开发工具，包括the design stage, the implementation stage, the testing stage, the deployment and operation stage, and the maintenance and evolution stage.

具体讨论maintenance and evolution阶段和testing阶段的工具。
总结了支持升级/回滚的困难及目前的解决方案。作者使用了VMM方法，用UML（User Mode Linux）来解决升级问题。
对于testing，作者分析了调试支持工具。提到：Single-stepping is inherently an inappropriate debugging primitive for distributed applications.

本文对于领域内困难和已有方案的总结很清晰，尤其是对于Upgrade / Rollback问题。如果想有一个总体的了解，可以读一读相关部分。

(HotOS'03 Note)Scheduling and Simulation: How to Upgrade Distributed Systems

Scheduling and Simulation: How to Upgrade Distributed Systems
Sameer Ajmani, Barbara Liskov and Liuba Shrira
HotOS 2003

讨论分布式系统的升级问题。对于该问题的主要困难有较好的总结描述。

建立了upgrade infrastructure，主要有Schedule functions (SFs)、Simulation objects (SOs)、Transform functions (TFs)等核心概念。

(HotOS'03 Note)TCP Meets Mobile Code

TCP Meets Mobile Code
Parveen Patel, David Wetherall, Jay Lepreau and Andrew Whitaker
HotOS 2003

使用Mobile Code对TCP协议栈进行更新。

设计开发了XTCP，参看Patel (2003), Upgrading Transport Protocols using Untrusted Mobile Code, SOSP 2003.
采用了类型安全的C语言扩展Cyclone。

关注：
TCP rate equation [33]: J. Padhye et al. (1998), Modeling TCP Throughput: A Simple Model and its Empirical Validation, SIGCOMM 1998.

认识Monica S. Lam

Monica S. Lam 林倩玲
Professor
Computer Science Department
Stanford University

Homepage: http://suif.stanford.edu/~lam/

Prof. Lam是SUIF项目的leader，是Brian Schmidt(SunRay协议SLIM的开发者）和Jason Nieh（Thin-client大牛）的导师。

Biography (From her homepage)
Monica Lam received a B.Sc. from University of British Columbia in 1980 and a Ph.D. in Computer Science from Carnegie Mellon University in 1987. She joined the faculty of Computer Science at Stanford in 1988, where she is now a Professor. She has contributed to the research of a wide range of computer systems topics including compilers, program analysis, operating systems, security, computer architecture, and high-performance computing. Her recent research focus is to make computing and programming easier.
In the Collective project, she and her research group developed the concept of a livePC: subscribers of the livePC will automatically run the latest of the published PC virtual images with each reboot. This approach allows computers to be managed scalably and securely. In 2005, the group started a company called moka5 to transfer the technology to industry.
In another research project, her program analysis group has developed a collection of tools for improving software security and reliability. They developed the first scalable context-sensitive inclusion-based pointer analysis and a freely available tool called BDDBDDB, that allows programmers to express context-sensitive analyses simply by writing Datalog queries. Other tools developed include Griffin, static and dynamic analysis for finding security vulnerabilities in Web applications such as SQL injection, a static and dynamic program query language called PQL, a static memory leak detector called Clouseau, a dynamic buffer overrun detector called CRED, and a dynamic error diagnosis tool called DIDUCE.
Prof. Lam is working with Al Aho, Jeff Ullman, and Ravi Sethi on revising the Dragon book. The new revision will be available September 2006.
Previously, Prof. Lam led the SUIF (Stanford University Intermediate Format) Compiler project, which produced a widely used compiler infrastructure known for its locality optimizations and interprocedural parallelization. Many of the compiler techniques she developed have been adopted by the industry. Her other research projects included the architecture and compiler for the CMU Warp machine, a systolic array of VLIW processors, and the Stanford DASH distributed shared memory machine. In 1998, she took a sabbatical leave from Stanford to help start Tensilica Inc., a company that specializes in configurable processor cores.
Prof. Lam is one of the top 50 most cited computer scientists in the world. She received the ACM Programming Language Design and Implementation Best Paper Award in 2004, an ACM SIGSOFT Distinguished Paper Award in 2002, the ACM Most Influential Programming Language Design and Implementation Paper Award in 2001, and an NSF Young Investigator award in 1992. She was the author of two of the papers in "20 Years of PLDI--a Selection (1979-1999)", and one paper in the "25 Years of the International Symposia on Computer Architecture", 1988.
She chaired the ACM SIGPLAN Programming Languages Design and Implementation Conference in 2000, served on the Editorial Board of ACM Transactions on Computer Systems and numerous program committees for conferences on languages and compilers (PLDI, POPL), operating systems (SOSP), and computer architecture (ASPLOS, ISCA).

第二次学术沙龙

今天晚上的第二次学术沙龙在BFT顺利举行，Andy、Brady、Vivian、Water参加。

Vivian报告了连续图像无损压缩领域的一些基本情况，做了一下科普。（其间被Andy打断若干次，很不好意思^_^）对于JPEG-LS等无损压缩算法的基本模式“建模－编码”进行了介绍，顺便普及了下熵、变换等概念。Vivian还简单介绍了Shannon编码、Huffman编码、Glomb编码等编码方案。Vivian后续会贴些文章列表上来。

Water介绍了一篇关于VGA BIOS方面的论文。大家对于VGA BIOS的基本情况有了初步了解。该论文基于x86emu项目，对VGA BIOS中使用legacy代码（INT调用）进行了支持，对大家很有启发。最为激动人心的是，Andy提出了在此基础上的一个新idea，大家都充满憧憬( Water后续会进行做一些调研工作，下次沙龙要进行报告。至于新idea，暂时保密，呵呵～～～

Brady介绍了一篇名为Automatic Worm Fingerprinting的文章。普及了一下关于网络蠕虫的基本知识，介绍了作者的研究动机等。

Andy就HotOS’03中Distributed System主题中的三篇文章进行了介绍。两篇都和系统升级有关，一篇是Monica Lam小组的工作Collective。Collective和目前Thin-client的研究动机有类似之处，后续我们会继续关注。Andy后续会把相关笔记贴上来。

(HotOS'03 Note)TCP Offload is a Dumb Idea Whose Time Has Come

TCP Offload is a Dumb Idea Whose Time Has Come
Jeffrey C. Mogul
HotOS 2003

关于在NIC上实现TCP或者其它传输层协议的分析，即TOE（TCP Offload Engine）问题。

作者分析了TOE在实践中不成功的原因。认为，对于HTTP这样常见的应用，存在大量短时间的链接，从TOE中获得的收益有限，尤其是在当前通用CPU速度快速提高的情形之下。

作者认为对于网络存储等数据吞吐量特别大的应用，TOE还是有用武之地的。作者提出针对RDMA（Remote Direct Memory Access）应用TOE。

RDMA是一个引起我关注的点，似乎和设备/总线映射问题相关。其中有一段话如下。Although much of the network on RDMA has focused on storage systems, high-bandwidth graphics applications (e.g. streaming HDTV videos) have similar characteristic. A video-on-demand connection might use RDMA both at the server (for access to the stored video) and at the client (for rendering the video).

另外，文章中对于协议栈中single-copy technique也进行了总结，有兴趣可以作为一个起点进行检索。例如：Dalton et al. (1995):　NIC Supporting a Single-copy Host OS Implementation of TCP

(HotOS'03 Note) Why Events are a Bad Idea

Why Events are a Bad Idea (for High-concurrency Servers)
Rob von Behren et al.
HotOS 2003

作者认为对于高度并发的服务器应用，设计良好的线程模型要优于事件模型。其一个基本出发点是Lauer和Needham 1978年提出的essage-passing systems and process-based systems are duals.
作者提出的对现有线程库的改进，主要是对合作式调度的有效支持，可以提高线程库在此应用中效率。（线程切换开销主要来源于：a. 为抢占调度保存context；b. kernel crossing。这两点在合作式调度中都可以大大降低。）
作者还强调了编译器和运行时环境结合的作用。通过编译器的全局分析等手段，可以对调度点、栈尺寸等提供优化。
另外，高并发环境下栈分配的问题可能制约scalability，作者提出了动态栈分配、优化跨调度的栈尺寸等解决方法。这让我想起了Art of Computer Programming第一卷中Knuth对多个栈共享空间的分析。当时觉得只有MIX计算机会关注这个问题，现在看来当时的想法太幼稚了。

系统阅读论文集，读什么？

最近花了不少时间系统地阅读SOSP、OSDI、HotOS等论文集，也引得Brady等人“蠢蠢欲动”，但是他们提出一个问题，读什么？和自己做的工作没有太大关系，还要读吗？我也再反思这个问题，花这么多时间是否值得？

我觉得系统的阅读，不能仅仅抱着找和自己相关的方向和工作的目的，否则收获有限，还不如按照关键字检索，再参考reference按图索骥。

这一段时间以来，系统阅读论文集我有几个收获。
其一，走马观花地看看abstract，可以大约了解一下国际上大家都在忙活什么，即便仅仅整理一下index，也可以和大牛的名字混个面熟。例如，Alan Cox都听说过，但他的研究工作是什么，就是我在整理index时了解的。
其二，大多数论文都有很好的introduction，可以帮助我们迅速的了解该领域的关键问题是什么，基本现状是什么，等等。而且，读得多了，很可能就传成了一条线，即便自己目前不做那个方向，了解一下也是非常必要得。例如，关于TCP改进的问题，有协议改进、协议栈升级、移动代码、内核扩展的安全性等等多个研究角度，对这些有一个基本的概念，非常有助于建立完整的、立体的研究视野。
其三，很多论文的选题、研究方法等很好，对自己的研究方法能有所启发。例如，Google的关于GFS和MapReduce等文章，给我留下了很深刻的印象。
其四，随着自己研究工作的深入，一些论文的观点和视角可以提供很好的思路，虽然别人的方向和角度不同，但能够给自己很多启发。例如，有一篇关于文件系统中cache策略的文章就给我了一些启发，他山之石，可以攻玉。其实很多研究工作就是在于“嫁接”不同领域、方向的方法、思想。

当然，多读论文了解各个方向，对于选定研究方向是大有裨益的，建议师弟师妹们不要过早选定一个方向就钻进去，先多了解是非常必要的。

HotOS 2003 -- Index

Workshop on Hot Topics in Operating Systems

HotOS 2003

2003.5

NOTE: This list contains links to articles that may be covered by copyright. Those articles are NOT provided here and you will got a "404 - Page not found" error if you click the links.

---

The Emperor's Clothes

High Availability, Scalable Storage, Dynamic Peer Networks: Pick Two
(talk)

Charles Blake and Rodrigo Rodrigues, MIT Laboratory for Computer Science

One Hop Lookups for Peer-to-Peer Overlays (talk)

Anjali Gupta, Barbara Liskov, and Rodrigo Rodrigues, MIT Laboratory for
Computer Science

An Analysis of Compare-by-hash

Val Henson, Sun Microsystems

Why Events Are a Bad Idea (for High-Concurrency
Servers) (talk)

Rob von Behren, Jeremy Condit, and Eric Brewer, University of California at
Berkeley

---

Popping & Pushing the Stack

TCP Offload Is a Dumb Idea Whose Time Has Come (talk)

Jeffrey C. Mogul, Hewlett Packard Laboratories

TCP Meets Mobile Code (talk)

Parveen Patel, University of Utah; David Wetherall, University of Washington;
Jay Lepreau, University of Utah; Andrew Whitaker, University of Washington

Exploiting the Synergy between Peer-to-Peer and Mobile Ad
Hoc Networks

Y. Charlie Hu, Saumitra M. Das, and Himabindu Pucha, Purdue University

---

Distributed Systems

Scheduling and Simulation: How to Upgrade Distributed
Systems (talk)

Sameer Ajmani and Barbara Liskov, MIT Laboratory for Computer Science; Liuba
Shrira, Brandeis University

Development Tools for Distributed Applications

Mukesh Agrawal and Srinivasan Seshan, Carnegie Mellon University

Virtual Appliances in the Collective: A Road to
Hassle-Free Computing

Constantine Sapuntzakis and Monica S. Lam, Stanford University

POST: A Secure, Resilient, Cooperative Messaging
System (talk)

Alan Mislove, Ansley Post, Charles Reis, Paul Willmann, Peter Druschel, and
Dan S. Wallach, Rice University; Xavier Bonnaire, Pierre Sens, Jean-Michel Busca,
and Luciana Arantes-Bezerra, Université Paris VI

---

When Things Go Wrong

Crash-Only Software

George Candea and Armando Fox, Stanford University

The Phoenix Recovery System: Rebuilding from the
Ashes of an Internet Catastrophe (talk)

Flavio Junqueira, Ranjita Bhagwan, Keith Marzullo, Stefan Savage, and
Geoffrey M. Voelker, University of California, San Diego

Using Runtime Paths for Macroanalysis

Mike Chen, University of California, Berkeley; Emre Kiciman, Stanford
University; Anthony Accardi, Tellme Networks; Armando Fox, Stanford University;
Eric Brewer, University of California, Berkeley

Magpie: Online Modelling and Performance-aware
Systems

Paul Barham, Rebecca Isaacs, Richard Mortier, and Dushyanth Narayanan,
Microsoft Research Ltd, Cambridge, UK

Using Computers to Diagnose Computer Problems

Joshua A. Redstone, Michael M. Swift, and Brian N. Bershad, University of
Washington

---

Performance Optimization

Using Performance Reflection in Systems Software

Robert Fowler and Alan Cox, Rice University; Sameh Elnikety and Willy
Zwaenepoel, EPFL

Cassyopia: Compiler Assisted System Optimization
(talk)

Mohan Rajagopalan and Saumya K. Debray, University of Arizona; Matti A.
Hiltunen and Richard D. Schlichting, AT&T Labs—Research

Cosy: Develop in User-Land, Run in Kernel-Mode

Amit Purohit, Charles P. Wright, Joseph Spadavecchia, and Erez Zadok, Stony
Brook University

---

Storage 1

Why Can't I Find My Files? New Methods for Automating
Attribute Assignment

Craig A. N. Soules and Gregory R. Ganger, Carnegie Mellon University

Secure Data Replication over Untrusted Hosts

Bogdan C. Popescu, Bruno Crispo, and Andrew S. Tanenbaum, Vrije Universiteit

Palimpsest: Soft-Capacity Storage for Planetary-Scale
Services

Timothy Roscoe, Intel Research at Berkeley; Steven Hand, University of
Cambridge Computer Laboratory

---

Trusting Hardware

Certifying Program Execution with Secure Processors
(talk)

Benjie Chen and Robert Morris, MIT Laboratory for Computer Science

Hardware Works, Software Doesn't: Enforcing
Modularity with Mondriaan Memory Protection (talk)

Emmett Witchel and Krste Asanovic, MIT Laboratory for Computer Science

Flexible OS Support and Applications for Trusted
Computing

Tal Garfinkel, Mendel Rosenblum, and Dan Boneh, Stanford University

---

Pervasive Computing

Sensing User Intention and Context for Energy
Management (talk)

Angela B. Dalton and Carla S. Ellis, Duke University

Access Control to Information in Pervasive
Computing Environments (talk)

Urs Hengartner and Peter Steenkiste, Carnegie Mellon University

Privacy-Aware Location Sensor Networks

Marco Gruteser, Graham Schelle, Ashish Jain, Rick Han, and Dirk Grunwald,
University of Colorado at Boulder

---

Storage 2

FAB: Enterprise Storage Systems on a Shoestring

Svend Frølund, Arif Merchant, Yasushi Saito, Susan Spence, and Alistair
Veitch, Hewlett-Packard Laboratories

The Case for a Session State Storage Layer

Benjamin C. Ling and Armando Fox, Stanford University

Towards a Semantic-Aware File Store (talk)

Zhichen Xu and Magnus Karlsson, HP Laboratories; Chunqiang Tang, University
of Rochester; Christos Karamanolis, HP Laboratories

HotOS 2005 -- Index

Workshop on Hot Topics in Operating Systems

HotOS 2005

2005.6

NOTE: This list contains links to articles that may be covered by copyright. Those articles are NOT provided here and you will got a "404 - Page not found" error if you click the links.

---

Religious Wars

Are Virtual Machine Monitors Microkernels Done Right?

Steven Hand, Andrew Warfield, Keir Fraser, and Evangelos Kotsovinos,
University of Cambridge Computer Laboratory; Dan Magenheimer, HP Labs

OS Verification—Now!

Harvey Tuch, Gerwin Klein, and Gernot Heiser, National ICT Australia

Making Events Less Slippery with eel

Ryan Cunningham and Eddie Kohler, University of California, Los Angeles

---

Storage

Parallax: Managing Storage for a Million Machines

Andrew Warfield, Russ Ross, Keir Fraser, Christian Limpach, and Steven Hand,
University of Cambridge Computer Laboratory

Stupid File Systems Are Better

Lex Stein, Harvard University

Aggressive Prefetching: An Idea Whose Time Has
Come

Athanasios E. Papathanasiou and Michael L. Scott, University of Rochester

---

Outside the Comfort Zone

Why Markets Could (But Don't Currently) Solve
Resource Allocation Problems in Systems

Jeffrey Shneidman, Chaki Ng, and David C. Parkes, Harvard University; Alvin
AuYoung, Alex C. Snoeren, and Amin Vahdat, University of California, San Diego;
Brent Chun, Intel Research, Berkeley

Operating Systems Should Support Business Change

Jeffrey C. Mogul, HP Labs

---

It's Not AI, It's Systems

Designing Controllable Computer Systems

Christos Karamanolis, Magnus Karlsson, and Xiaoyun Zhu, Hewlett-Packard Labs

Three Research Challenges at the Intersection of
Machine Learning, Statistical Induction, and Systems

Moises Goldszmidt and Ira Cohen, Hewlett-Packard Labs; Armando Fox and Steve
Zhang, Stanford University

---

Cleaning Up the Mess We've Made

Making System Configuration More Declarative

John DeTreville, Microsoft Research

Reducing the Cost of IT Operations—Is Automation
Always the Answer?

Aaron B. Brown and Joseph L. Hellerstein, IBM Thomas J. Watson Research
Center

Human-Aware Computer System Design

Ricardo Bianchini, Richard P. Martin, Kiran Nagaraja, Thu D. Nguyen, and
Fábio Oliveira, Rutgers University

---

Approaches to OS Research

Thirty Years Is Long Enough: Getting Beyond C

Eric Brewer, Jeremy Condit, Bill McCloskey, and Feng Zhou, University of
California, Berkeley

Broad New OS Research: Challenges and Opportunities

Galen C. Hunt, James R. Larus, David Tarditi, and Ted Wobber, Microsoft
Research

patch (1) Considered Harmful

Marc E. Fiuczynski, Princeton University; Robert Grimm, New York University;
Yvonne Coady, University of Victoria; David Walker, Princeton University

---

Distribution

WiDS: An Integrated Toolkit for Distributed System
Development

Shiding Lin, Aimin Pan, and Zheng Zhang, Microsoft Research Asia; Rui Guo,
Beijing University of Aeronautics and Astronautics; Zhenyu Guo, Tsinghua
University

Causeway: Operating System Support for Controlling
and Analyzing the Execution of Distributed Programs

Anupam Chanda, Khaled Elmeleegy, and Alan L. Cox, Rice University; Willy
Zwaenepoel, EPFL, Lausanne

Treating Bugs as Allergies: A Safe Method for Surviving
Software Failures

Feng Qin, Joseph Tucek, and Yuanyuan Zhou, University of Illinois,
Urbana-Champaign

---

Security

When Virtual Is Harder than Real: Security
Challenges in Virtual Machine Based Computing Environments

Tal Garfinkel and Mendel Rosenblum, Stanford University

Make Least Privilege a Right (Not a Privilege)

Maxwell Krohn, Massachusetts Institute of Technology; Petros Efstathopoulos,
University of California, Los Angeles; Cliff Frey and Frans Kaashoek,
Massachusetts Institute of Technology; Eddie Kohler, University of California,
Los Angeles; David Mazières, New York University; Robert Morris, Massachusetts
Institute of Technology; Michelle Osborne, New York University; Steve
VanDeBogart, University of California, Los Angeles; David Ziegler, Massachusetts
Institute of Technology

Access Control in a World of Software Diversity

Martin Abadi, University of California, Santa Cruz; Andrew Birrell and Ted
Wobber, Microsoft Research

---

Sensor Nets

PRESTO: A Predictive Storage Architecture for
Sensor Networks

Peter Desnoyers, Deepak Ganesan, Huan Li, Ming Li, and Prashant Shenoy,
University of Massachusetts, Amherst

Towards a Sensor Network Architecture: Lowering the
Waistline

David Culler, Prabal Dutta, Cheng Tien Ee, Rodrigo Fonseca, Jonathan Hui,
Philip Levis, and Joseph Polastre, University of California, Berkeley; Scott
Shenker, University of California, Berkeley, and ICSI; Ion Stoica and Gilman
Tolle, University of California, Berkeley; Jerry Zhao, ICSI

---

Breakout Session

Falling Off the Cliff: When Systems Go Nonlinear (Green
Team Paper)

Yvonne Coady, Russ Cox, John DeTreville, Peter Druschel, Joseph Hellerstein,
Andrew Hume, Kimberly Keeton, Thu Nguyen, Christopher Small, Lex Stein, and
Andrew Warfield

The Many Faces of Systems Research—and How to Evaluate
Them (Red Team Paper)

Aaron B. Brown, Anupam Chanda, Rik Farrow, Alexandra Fedorova, Petros
Maniatis, and Michael L. Scott

Open the door!

Open the door, and invite my good friends to here. (Not "open windows" :P)
I wanna be an anti-tradition IT man, may be more conservative in another sense.