Advanced Systems Topics
2008–09

Principal lecturer: Dr Steven Hand
Taken by: Part II
Syllabus
Past exam questions

Internet Routing Protocols

Lecturer: Dr Timothy G. Griffin

Internet routing protocols from a distributed systems perspective. We will cover the five most commonly used protocols --- RIP, EIGRP, OSPF, IS-IS (all roughly based on the shortest-paths model) and BGP (which has evolved organically in the interdomain context). Convergence, scalability, and stability are the main concerns. Lecture notes can be found at http://www.cl.cam.ac.uk/~tgg22/ast.

Advanced operating systems

Lecturer: Dr Steven Hand

This section of the course will cover distributed and persistent virtual memory, capability systems, microkernel evolution, virtual machine monitors, extensibility and filesystem & database storage.

• Slides in PDF format.
• Additional slides on EROS (from a guest lecture given in 2004)
• Past exam questions and some sample supervision questions.
• Some sketch answers to the above sample questions; please read these only after attempting the sample questions.
• Recommended books:
  • Singal, M. & Shivaratri, N. (1994). Advanced Concepts in Operating Systems: Distributed, Database, and Multiprocessor Operating Systems. McGraw-Hill.
  • Stonebraker, M. & Shivaratri, N. (1998). Readings in Database Systems. Morgan Kaufmann (3rd ed.).
• Additional reading:
  • Memory Coherence in Shared Virtual Memory Systems, Li et al, PODC 1986.
  • Munin: distributed shared memory based on type-specific memory coherence, Bennet et al, PPOPL 1990.
  • The Multics Virtual Memory: Concepts and Design, Bensoussan et al, CACM May 1972 15(5)
  • Texas: An Efficient, Portable Persistent Store, Singhal et al, POS 1982
  • Lightweight Recoverable Virtual Memory, Satya et al et al, TOCS 1994
  • Free Transactions with Rio Vista, Lowell and Chen, SOSP 1997
  • The Cambridge CAP Computer, Levy, 1998
  • The Duality of Memory and Communication in the Implementation of a Multiprocessor Operating System (aka Mach), Young et al, SOSP 1987
  • On Microkernel Construction, Liedtke, SOSP 1995
  • The Performance of Microkernel-based Systems (aka L4), Haertig et al, SOSP 1997
  • State-caching in the EROS Kernel, Shapiro et al, POS 1996
  • Disco: Running Commodity Operating Systems on Scalable Multiprocessors, Buignon et al, SOSP 1997
  • Scale and Performance in the Denali Isolation Kernel, Whitaker et al, OSDI 2002
  • Xen and the Art of Virtualization, Barham et al, SOSP 2003
  • Extensibility, Safey and Performance in the SPIN Operating System, Bershad et al, SOSP 1995
  • Dealing with Disaster: Surviving Misbehaved Kernel Extensions (aka Vino), Seltzer et al, OSDI 1996
  • Exterminate All Operating System Abstractions (aka ExoKernel), Engler et al, HotOS 1995
  • Application Performance and Flexibility on Exokernel Systems, Kaashoek et al, SOSP 1997
  • Self-paging in the Nemesis Operating System, Hand, OSDI 1999
  • The Ubiquitous B-Tree, Comer, ACM Computing Surveys 1979
  • The Implementation of Postgres, Stonebraker et al, IEEE KDE 1990
  • Operating System Support for Database Management, Stonebraker, CACM 1981
  • RFC 1813: NFS Version 3 Protocol Specification (1995) and RFC 3530: Network File System (NFS) Version 4 Protocol (2003)
  • Interposed Request Routing for Scalable Network Storage, Anderson et al, OSDI 2000
  • Disconnected Operation in the Coda File System, Kistler and Satya, ACM TOCS 1992
  • A Low-bandwidth Network File System, Muthitacharoen et al, SOSP 2001
  • Serverless Network File Systems (aka xFS), Anderson et al, SOSP 1995
  • A Case for Network-Attached Secure Disks, Gibson et al, CMU Tech Report 1996
  • The Design of a Mutlicast-based Distributed File System (aka JetFile), Gronvall et al, OSDI 1999
  • Petal: Distributed Virtual Disks, Thekkath et al, ASPLOS 1996
  • Frangipani: A Scalable Distributed File System, Thekkath et al, SOSP 1996
  • Venti: a new approach to archival storage, Quinlan and Dorward, FAST 2003

  Note that it is not expected that students read all of the above material; however individual papers may be of use to attain more indepth knowledge of certain principles, etc.

  Mobile and Sensor Systems

  Lecturer: Dr Cecilia Mascolo
  

  This section of the course concerns systems and communication in decentralized mobile networks and sensor systems. In mobile systems we will concentrate on issues arising from the application of these systems to vehicular networking, human ad hoc connectivity and decentralized content distribution. In terms of sensor systems we will look at energy and communication tradeoffs for of both mobile and fixed devices with application in various scenarios such as human and animal activity monitoring and environmental monitoring. Lecture Notes can be found here.