Advanced Systems Topics
Principal lecturer: Dr Steven Hand
Taken by: Part II
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
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)
exam questions and some sample
- 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
- 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,
- 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
- Operating System Support for Database Management, Stonebraker,
- 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
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.