Department of Computer Science 


CS 6410: Advanced Systems

Fall 2010

   
    
* Home
* Schedule
* Labs
* Project
 

Note that papers are subject to change

#

Who (click for slides)

Date

Topic

Required Reading

Suggested Reading

0.

Hakim
PDF  PPTX 

08/26

Organizational Meeting

none

 

1.

Hakim
PDF  PPTX 

08/31

What is Systems About?

End-to-end arguments in system design, J.H. Saltzer, D.P. Reed, D.D. Clark. ACM Transactions on Computer Systems Volume 2, Issue 4 (November 1984), pages 277--288.

The Impact of Architectural Trends on Operating System Performance  Rosenblum et al.  15th SOSP, 1995.

Interposition Agents: Transparently Interposing User Code at the System Interface,  Michael Jones.  14th SOSP, 1993, pages 80--93.

Hints for computer system design, B. Lampson. Proceedings of the Ninth ACM Symposium on Operating Systems Principles (Bretton Woods, New Hampshire, United States) 1983, pages 33--48.

2.

Hakim
PDF  PPTX 

09/02

Classic Systems

The UNIX time-sharing system, Dennis M. Ritchie and Ken Thompson. Communications of the ACM Volume 17, Issue 7 (July 1974), pages 365--375.

The nucleus of a multiprogramming system, P, Brinch Hansen. Communications of the ACM Volume 13, Issue 4 (April 1970), pages 238--241.

The structure of the "THE"-multiprogramming system, E.W. Dijkstra. Communications of the ACM Volume 11, Issue 5 (May 1968), pages 341--346.

3.

Hakim
PDF  PPTX 

09/07

Concurrency, Threads, and Events

SEDA: An Architecture for Well Conditioned, Scalable Internet Services, Matt Welsch, David Culler, and Eric Brewer. Proceedings of the Eighteenth ACM Symposium on Operating Systems Principles (Banff, Alberta, Canada, 2001), pages 230--243.

Goal-oriented programming, or composition using events,or threads considered harmful,  Eobbert Van Renesse. Proceeding of the 8th ACM SIGOPS European Workshop on Support for Composing Distributed Applications (Sintra, Portugal, 1998), pages 82--87.

Using Threads in Interactive Systems.  Hauser et al.  14th SOSP, Dec 1993.

An introduction to programming with threads, A. Birrell. Technical Report, Microsoft Research, May 2005.

Capriccio: Scalable threads for internet services, Rob von Behren et al. Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles (Bolton Landing, NY, 2003), pages 268--281.

Events can make sense, Maxwell Krohn, Eddie Kohler, and M. Frans Kaashoek. Proceedings of the 2007 USENIX Annual Technical Conference (Santa Clara, CA, June 2007), pages 87--107.

Using continuations to implement thread management and communication in operating systems, Richard P. Draves, Brian N. Bershad, Richard F. Rashid, and Randall W. Dean. Proceedings of the Thirteenth ACM Symposium on Operating Systems Principles (Pacific Grove, California, 1991), pages 122--136.

Eraser: A Dynamic Data Race Detector for Multi-Threaded Programs  Savage et al.  16th SOSP, 1997.

On the duality of operating system structures, H. C. Lauer and R. M. Needham. ACM SIGOPS Operating Systems Review Volume 12, Issue 2 (April 1979), pages 3--19.

4.

Hakim
PDF  PPTX 

09/09

File Systems

A Fast File System for UNIX. Marshall K. McKusick, William N. Joy, Samuel J. Leffler, Robert S. Fabry.  ACM TOCS 2(3), Aug 1984, pages 181--197.

Soft Updates: A Solution to the Metadata Update problem in File Systems.  Gregory R. Ganger, Marshall Kirk McKusick, Craig A. N. Soules, Yale N. Patt. ACM TOCS 18(2). May 2000, pages 127--153.

The Zebra striped network file system,  John H. Hartman and John K. Ousterhout. Proceedings of the fourteenth ACM symposium on Operating systems principles, 1993, pages 29--43.

When to forget in the Elephant file system,  Douglas S. Santry, Michael J. Feeley, Norman C. Hutchinson, Alistair C. Veitch, Ross W. Carton, and Jacob Ofir.  Proceedings of the seventeenth ACM symposium on Operating systems principles, December 1999, pages 110--123.

The Design and Implementation of a Log-Structured File System, Mendel Rosenblum and Ousterhout. Proceedings of the thirteenth ACM symposium on Operating systems principles, October 1991, pages 1--15.

5.

Ki Suh
PDF  PPTX 

09/14

Novel File Systems

Lightweight Recoverable Virtual Memory, M. Satyanarayanan, Henry H. Mashburn, Puneet Kumar, David C. Steere, and James J. Kistler. Proceedings of the fourteenth ACM symposium on Operating systems principles, 1994, pages 146--160.

A New Presumed Commit Optimization for Two Phase Commit, Butler W. Lampson and David B. Lomet. Proceedings of the 19th International Conference on Very Large Data Bases, 1993, pages 630-640.

The evolution of Coda, M. Satyanarayanan. ACM Transactions on Computer Systems, Volume 20, Issue 2 (May 2002), pages 85--124.

6.

Jason W.
PDF  PPT 

09/16

  µ-Kernels

The Duality of Memory and Communication in the Implementation of a Multiprocessor Operating System, M. Young, A Tavanian, R. Rashid, D. Golub, and J. Eppinger. Proceedings of the Eleventh ACM Symposium on Operating Systems Principles (Austin, Texas, United States), ACM, 1987, pages 63--76.

EMERALDS: A Small-Memory Real-Time Microkernel,  Zuberi et al.  17th SOSP, 1999.

The Flux OSKit: A Substrate for OS and Language Research. Ford et al. 16th SOSP, Oct 1997.

The Performance of µ-Kernel-based Systems.  Härtig et al.  16th SOSP, Oct 1997.

7.

Hakim
PDF  PPTX 

09/21

Virtual Memory

Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Machines, Richard Rashid, Avadis Tevanian, Michael Young, David Golub, Robert Baron, David Black, William Bolosky, Jonathan Chew.  2nd international conference on Architectual Support for Programming Languages and Operating Systems (ASPLOS), November 1987, pages 31--39.

Virtual Memory Primitives for User Programs,  Andrew W. Appel and Kai Li.  4th international conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), April 1991, pages 96--107.

Sharing and Protection in a Single Address Space Operating System,  Jeffrey S. Chase, Henry M. Levy, Michael J. Feeley, Edward D. Lazowska. ACM TOCS, Volume 12, Issue 4, (November 1994), pages 271--301.

Labels and Event Processes in the Asbestos Operating System, Petros Efstathopoulos, Maxwell Krohn, Steve VanDeBogart, Cliff Frey, David Ziegler, Eddie Kohler, David Mazières, Frans Kaashoek, and Robbert Morris.   12th ACM symposium on Operating systems principles (SOSP), October 2005, pages 17--30.

8.

Hakim
PDF  PPTX 

09/23

Extensible Kernels

Exokernel: an operating system architecture for application-level resource management,  Dawson R. Engler, M. Frans Kaashoek, and James O'Toole, Jr.  15th ACM symposium on Operating systems principles (SOSP), December 1995, pages 251--266

Application performance and flexibility on Exokernel systems,  Kaashoek et al.  16th SOSP, 1997.

Microkernels meet Recursive Virtual Machines,  Bryan Ford, Mike Hibler, Jay Lepreau, Patrick Tullmann, Godmar Back, Stephen Clawson.   2nd USENIX symposium on Operating systems design and implementation (OSDI), October 1996, pages 137-151.

Extensibility, Safety and Performance in the SPIN Operating System, Brian N. Bershad, Stefan Savage, Przemyslaw Pardyak, Emin Gun Sirer, Marc E. Fiuczynski, David Becker, Craig Chambers, Susan Eggers.   15th ACM symposium on Operating systems principles (SOSP), December 1995, pages 267--283.

9.

Vainstein K.
PDF  PPT 

09/28

Multi-Processors

Disco: Running Commodity Operating Systems on Scalable Multiprocessors, Edouard Bugnion, Scott Devine, and Mendel Rosenblum.   16th ACM symposium on Operating systems principles (SOSP), October 1997, pages 143--156.

Towards Transparent and Efficient Software Distributed Shared Memory,  Daniel J. Scales and Kourosh Gharachorloo.   16th ACM symposium on Operating systems principles (SOSP), October 1997, pages 157--169.

Performance Isolation: Sharing and Isolation in Shared-Memory Multiprocessors, Ben Verghese, Anoop Gupta, Mendel Rosenblum.   8th international conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), October 1998, pages 181--192.

Tornado: maximizing locality and concurrency in a shared memory multiprocessor operating system,  Ben Gamsa, Orran Krieger, Jonathan Appavoo, and Michael Stumm.   3rd USENIX symposium on Operating systems design and implementation (OSDI), February 1999, pages 87-100.

10.

Brett F.
PDF  PPTX 

09/30

Virtual Machine Monitors: Technology and Trends

Xen and the Art of Virtualization, Paul Barham, Boris Dragovic, Keir Fraser, Steven Hand, Tim Harris, Alex Ho, Rolf Neugebauer, Ian Pratt, Andrew Warfield.  19th ACM symposium on Operating systems principles (SOSP), October 2003, pages 164--177.

Are Virtual Machine Monitors Microkernels Done Right?, Gernot Heiser, Volkmar Uhlig, Joshua LeVasseur.   ACM SIGOPS Operating Systems Review (OSR), Volume 40, Issue 1, January 2006, pages 95--99.

Memory resource management in VMware ESX server, C. A. Waldspurger.  OSDI 2002.

Virtual Machine Monitors: Current Technology and Future Trends, Mendel Rosenblum, Tal Garfinkel. Computer, vol. 38, no. 5, pp. 39-47, May 2005.

Operating System Support for Virtual Machines, S. T. King, G. W. Dunlap, and P. M. Chen. 2003 USENIX Technical Conference.

Are Virtual Machine Monitors Microkernels Done Right?, Steven Hand, Andrew Warfield, Keir Fraser, Evangelos Kotsovinos, Dan Magenheimer. Proceedings of the Tenth Workshop on Hot Topics in Operating Systems (HotOS), Sante Fe, NM, June 2005.

11.

Matt M.
PDF  PPTX 

10/05

Remote method invocation: making distributed computing totally transparent…

Implementing Remote Procedure Calls,  Birrell and Nelson.  ACM TOCS 2(1), Feb. 1984.

Performance of Firefly RPC, Schroeder and Burrows.  ACM TOCS 8(1), 1990.

RPC in the x-Kernel: Evaluating New Design Techniques,  Peterson et al.  12th SOSP, Nov. 1989.

Lightweight remote procedure call,  Bershad et al.  ACM TOCS  8(1), Feb 1990.

12.

Robert E.
PDF 

10/07

Networking (from an OS perspective)

Congestion Avoidance and Control, Van Jacobson. Appears in Proceedings of ACM SIGCOMM, Vo1ume 18, Number 4, (August 1988).

 

TCP Congestion Control with a Misbehaving Receiver, Stefan Savage, Neal Cardwell, David Wetherall and Tom Anderson, Appears in ACM SIGCOMM Computer Communication Review, Volume 29 , Issue 5 (October 1999), pages 71--78.

 

 

10/12

No class: Fall Break

13.

Makoto B.
PDF  PPT 

10/14

Networking

U-Net: A User-Level Network Interface for Parallel and Distributed  Computing,  Von Eicken, Basu, Buch and Werner Vogels. 15th SOSP, December 1995.

Evaluation of the Virtual Interface Architecture (VIA).

Towards an active network architecture, David L. Tennenhouse and David J. Wetherall. Appears in ACM SIGCOMM Computer Communication Review (CCR), Volume 37, Issue 5 (October 2007), pages 81--94.

A Survey of Active Network Research, David L. Tennenhouse, Jonathan M. Smith, W. David Sincoskie, David J. Wetherall, and Gary J. Minden. Appears in IEEE Communications Magazine, Volume 35, Issue 5 (October 1997), pages 80--86.

Active Messages: A Mechanism for Integrated Communication and Control, Thorsten von Eicken, David E. Culler, Seth Copen Goldstein, and Klaus Erik Schauser. In Proceedings of the 19th Annual International Symposium on Computer Architecture, 1992.

14.

Ji Yong S.
PDF  PPTX 

10/19

Speculation

Rethink the Sync,  Edmund B. Nightingale, Kaushik Veeraraghavan, Peter M. Chen, and Jason Flinn. Proceedings of the 7th USENIXE Symposium on Operating Systems Design and Implementation (OSDI), November 2006.

 

Speculative Execution in a Distributed File System,  Edmund B. Nightingale, Peter M Chen, Jason Flinn. Proceedings of the 20th ACM Symposium on Operating Systems Principles (SOSP), October 2005, pages 191--205.

15.

Elisavet K.
PDF  PPTX 

10/21

Peer to peer

Chord: A scalable peer-to-peer lookup service for internet applications, Ion Stoica, Robert Moris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan. Proceedings of the ACM SIGCOMM, August 2001, 149--160. San Diego, California, United States.

 

The Impact of DHT Routing Geometry on Resilience and Proximity, Krishna Gummadi , Ramakrishna Gummadi , Steve Gribble , Sylvia Ratnasamy , Scott Shenker, Ion Stoica. Appears in Proceedings of ACM SIGCOMM, August 2003, pages 381--394.

16.

Haoyan G.
PDF 

10/26

Staggeringly large file systems

The Google file system,  Sanjay Ghemawat, Howard Gobioff, Shun-Tak Leung. Appears in 19th ACM symposium on Operating systems principles (SOSP), October 2003, pages 29--43.

Storage management and caching in PAST, a large scale, persistent peer-to-peer storage utility,  Rowstron and Druschel.  18th SOSP, Oct 2001.

A Distributed Decentralized Information Storage and Retrieval System,  Ian Clark.  University of Edinburgh, 1999 (Original unpublished technical report on Freenet).

Why Gnutella can't scale, no really?,  Ritter, Feb 2001.

Pond: the OceanStore Prototype, Sean Rhea, Patrick Eaton, Dennis Geels, Hakim Weatherspoon, Ben Zhao, and John Kubiatowicz. Appears in Proceedings of the 2nd USENIX Conference on File and Storage Technologies (FAST), March 2003, pages 1--14.

17.

Tom T.
PDF  PPTX 

10/28

Multicast

Overcast: Reliable Multicasting with an Overlay Network,  Jannotti et al.  4th OSDI, Dec 2000.

Bimodal Multicast,  Birman et al.  ACM TOCS 17(2), May 1999.

Enabling Conferencing Applications on the Internet using an Overlay Multicast Architecture,  Chu et al. ACM SIGCOMM, Aug 2001.

SCRIBE: A large-scale and decentralized application-level multicast infrastructure,  Castro et al.  IEEE Journal on Selected Areas in communications (JSAC), 2002.

Resilient overlay networks,  David Andersen, Hari Balakrishnan, Frans Kaashoek, Robert Morris. SOSP 2001

Some observations on BitTorrent performance,  Ashwin R. Bharambe, Cormac Herley, Venkata N. Padmanabhan. SIGMETRICS 05.

SplitStream: high-bandwidth multicast in cooperative environments. Castro, et. al. SOSP 2003.

18.

Makoto
PDF  PPT 

11/02

Epidemic Techniques

Epidemic algorithms for replicated database maintenance,  Alan Demers, Dan Greene, Carl Hauser, Wes Irish, John Larson, Scott Shenker, Howard Sturgis, Dan Swinehart, Doug Terry. Appears in 6th ACM Symposium on Principles of distributed computing (PODC), August 1987, pages 1--12.

Astrolabe: A Robust and Scalable Technology for Distributed System Monitoring, Management, and Data Mining,  Robbert Van Renesse, Kenneth P. Birman, Werner Vogels.  Appears in ACM Transactions on Computer Systems (TOCS), Volume 21, Issue 2, May 2003, pages 164--206.

Kelips: Building an Efficient and Stable P2P DHT Through Increased Memory and Background Overhead,  Indranil Gupta, Ken Birman, Prakash Linga, Al Demers and Robbert van Renesse.  2nd International Workshop on Peer-to-Peer Systems (IPTPS '03); February 20-21, 2003.  Claremont Hotel, Berkeley, CA, USA.

Managing update conflicts in Bayou, a weakly connected replicated storage system, Doug B. Terry, Marvin M. Theimer, Karin Petersen, Alan J. Demers, Mike J. Spreitzer, and Carl H. Hauser. In Proceedings of the 5th ACM Symposium on Operating Systems Principles (SOSP), December 1995, pages 172--182.

19.

Dinesh B.
PDF  PPTX 

11/04

Ordering and Consistent Cuts

Time, Clocks, and the Ordering of Events in a Distributed System,  Lamport. CACM 21(7). July 1978.

 

Distributed snapshots: Determining global states of distributed systems.,&nsp; Chandy, Lamport. ACM TOCS 3(1), 1985, 63-75.

20.

Vainstein K.
PDF  PPT 

11/09

Time

Optimal Clock Synchronization,  Srikanth and Toueg.  JACM 34(3), July 1987.

Understanding protocols for Byzantine Clock Synchronization,  Schneider.  Cornell CS TR 87-859.  Aug 1987.

Using Time Instead of Timeout for Fault-Tolerant Distributed Systems, Lamport.  ACM TOPLAS 6:2, 1974.

Probabilistic Internal Clock Synchronization,  Cristian and Fetzer.

21.

Alex F.
PDF 

11/11

Consensus

Impossibility of Distributed Consensus with One Faulty Process,  Fisher et al.  JACM 32(2), Apr 1985.

Revisiting the Paxos Algorithm,  De Prisco et al. WDAG, Sep 1997.

The weakest failure detector for solving consensus,  Chandra et al. J. ACM 43, 4, Jul. 1996.

Paxos Made Simple,  Lamport.  ACM SIGACT NEWS 32(4).  Dec. 2001.

22.

Ki Suh
PDF  PPTX 

11/16

Virtual Synchrony

The Process Group Approach to Reliable Distributed Computing,  Birman. CACM, Dec 1993, 36(12):37-53.

From Set Membership to Group Membership: A Separation of Concerns,  A. Schiper and S. Toueg.  IEEE TDSC 3:1 (Jan 2006).

A modular approach to fault-tolerant broadcast and related problems,  Hadzilacos and Toueg. Cornell CS TR 94-1425,May 1994.

Building reliable, high-performance communication systems from components,  Liu et al.  17th SOSP, 1999.

Scalable Trusted Computing, Ken's slide set. November 2006.
This discusses the role of consensus and group communication in the context of an emerging problem, namely tracking a dynamically evolving security policy database.

Understanding the Limitations of Causally and Totally Ordered Communication,  Cheriton and Skeen.  14th SOSP, 1993.

Note: This paper has some flaws. Discussion and rebuttals to some of the claims it makes appeared in the January 1994 issue of Operating Systems Review.

23.

Robert E.

11/18

Replication Techniques

Implementing fault-tolerant services using the state machine approach: A tutorial, Fred Schneider. ACM Computing Surveys Volume 22, Issue 4 (December 1990), 299--319.

Dangers of Replication and a Solution, Gray et al.  ACM SIGMOD, Jun 1996.

Maintaining Availability in Partitioned Replicated Databases,  Abbadi and Toueg.  ACM TODS 14(2), Jun 1989.

The Costs and Limits of Availability for Replicated Services,  Yu and Vahdat.18th SOSP, Oct 2001.

Chain Replicationfor supporting high throughput and availability,  Robbert van Renesse and Fred Schneider. Appears in Proceedings of the 6th conference on Symposium on Opearting Systems Design and Implementation (OSDI), December 2004.

24.

Eleanor B.
PDF  PPTX 

11/23

Byzantine Techniques

The Byzantine Generals Problem,  Lamport et al.  ACM TOPLAS 4, 1982.

Randomized Byzantine Generals,  Rabin. FOCS, 1983.

Byzantine Quorum Systems,  Malkhi and Reiter.

Fault-scalable Byzantine Fault-Tolerant Services,  Michael Abd-El-Malek et.al.  SOSP 2005.

Practical Byzantine Fault Tolerance,  Castro and Liskov. 3rd OSDI, Feb 1999.

 

 

11/25

No class: Happy Thanksgiving!

25.

Hakim
PDF  PPTX 

11/30

Game Theory

BAR Gossip,  H. Li, A. Clement, E. Wong, J. Napper, I. Roy, L. Alvisi, M.Dahlin, OSDI 2006, Nov 2006.

How Bad is Selfish Routing?,  T. Roughgarden and E. Tardos.  JACM, 2002, Volume 49 , Issue 2.

A BGP-based Mechanism for Lowest-Cost Routing,  J. Feigenbaum, C. Papadimitriou, R. Sami, and S. Shenker, Distributed Computing 18 (2005), pp. 61-72.(Special issue of selected papers from Proc. of ACM PODC'02.)

Do incentives build robustness in BitTorrent?,  M. Piatek, T. Isdal, T. Anderson, A. Krishnamurthy, A. Venkataramani. NSDI 2007.

 

 

12/02

Final Presentations: Demo Day!


Questions or comments? email hweather@cs.cornell.edu

Policy on academic integrity


Hakim Weatherspoon
Last modified: Mon Dec 6 14:51:08 EST 2010