Classes: Tuesdays and Thursdays, 10:10-11:25; Upson 109
A page with details on the class is here.
Who (click for slides) |
Date |
Topic |
Required
|
Suggested
|
|
8/23 |
Organizational Meeting |
none |
Background materials for one of the ideas for a possible project |
|
|
8/25 |
Concurrency, Threads, and Events. |
Using Threads in Interactive Systems. Hauser et al. 14th SOSP, Dec 1993. |
Goal-oriented programming, or composition using events,or threads considered harmful. Van Renesse. ACM SIGOPS European Workshop, Sep 1998. Eraser. A Dynamic Data Race Detector for Multi-Threaded Programs. Savage et al. 16th SOSP, 1997. |
|
|
SEDA: An Architecture for Well Conditioned, Scalable Internet Services. Welsh et al. 18th SOSP, Oct 2001. |
||||
|
8/30 |
File Systems |
Soft Updates: A Solution to the Metadata Update problem in File Systems. Ganger et al. ACM TOCS 18(2). May 2000. |
A Fast File System for UNIX. McKusick et al. ACM TOCS 2(3), Aug 1984. The Zebra striped network file system; Hartman and Ousterhout; 14th SOSP, 1993. When to forget in the Elephant file system. Santry et al. 17th SOSP, 1999. |
|
|
The Design and Implementation of a Log-Structured File System. Rosenblum and Ousterhout. 13th SOSP, Oct 1991. |
||||
|
9/4 |
OS Kernels |
The Performance of µ-Kernel-based Systems. Härtig et al. 16th SOSP, Oct 1997. |
The UNIX Time-Sharing System. Richie and Thompson. 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. |
||||
|
RvR (vm |
9/6 |
Virtual Memory |
Virtual Memory Primitives for User Programs. Appel and Li. 4th ASPLOS, April 1991. |
|
|
Labels and Event Processes in the Asbestos Operating System. Petros Efstathopoulos et. al. SOSP 2005 |
||||
|
Ken |
9/11 |
Extensible Kernels |
Application performance and flexibility on Exokernel systems. Kaashoek et al. 16th SOSP, 1997.
Microkernels
meet Recursive Virtual Machines. Ford et al. 2nd OSDI, Oct 1996. |
|
|
Matt Watkins |
9/13 |
Multi-Processors |
Towards Transparent and Efficient Software Distributed Shared Memory. Scales and Gharachorloo. 16th SOSP, 1997. Performance Isolation: Sharing and Isolation in Shared-Memory Multiprocessors. Verghese et al. 8th ASPLOS, Oct 1998. |
|
|
Jon Kaldor |
9/18 |
Virtual Machine Monitors: Technology and Trends |
Xen and the Art of Virtualization,
Dragovic, et. al. Proc 19th SOSP, Oct. 2003 |
Memory resource management in VMware ESX server, C. A. Waldspurger. OSDI 2002 |
|
Jonathan Winter |
9/20 |
If the CPU is so fast, why are the programs running so slowly? |
- The DEC Alpha 21164 Data Sheet ftp://ftp.digital.com/pub/Digital/info/semiconductor/literature/21164ds.pdf - An IEEE Micro article about the 21164http://ieeexplore.ieee.org/iel1/40/8521/00372349.pdf?tp=&arnumber=372349&isnumber=8521 Power Architecture: A High-Performance Architecture with a History. IBM Technical White Paper. |
|
|
System Support for Automated Profiling and Optimization.
Zhang, et. al. SOSP 1997 |
||||
|
Xin Zheng |
9/25 |
Remote method invocation: making distributed computing totally transparent… |
Implementing Remote Procedure Calls. Birrell and Nelson. ACM TOCS 2(1), Feb. 1984. |
RPC in the x-Kernel: Evaluating New Design Techniques. Peterson et al. 12th SOSP, Nov. 1989. |
|
Performance of Firefly RPC. Schroeder and Burrows. ACM TOCS 8(1), 1990. |
||||
|
9/27 |
To infinity and beyond! |
|||
|
Lightweight remote procedure call; Bershad et al. ACM TOCS 8(1), Feb 1990. |
||||
|
Matt Watkins |
10/2 |
System Design |
Hints for Computer Systems Design. Lampson. ACM OSR 15(5), Oct 1983. |
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. Jones. 14th SOSP, 1993. |
|
End-to-End Arguments in System Design. Saltzer et al. ACM TOCS 2(4), Nov 1984. |
||||
|
Xin Zheng |
10/4 |
Network Objects |
Fine-Grained Mobility in the Emerald
System The Jini architecture for network-centric computing. Waldo. CACM 42(7), Jul 1999. |
|
|
Linda in Context. Carriero and Gelernter. CACM 32(4), Apr 1989. |
||||
|
Jon
Kaldor |
10/11 |
Stopping Worm/Virus Attacks |
Vigilante: End-to-End Containment of Internet Worms. Manuel Costa et. al. SOSP 2005 |
The Taser Intrusion Recovery System. Ashvin Goel et. al. SOSP 2005 |
|
10/16 |
Speculation |
|
||
|
10/18 |
Publish/Subscribe |
Mesh-based Content Routing using XML. Snoeren et al. 18th SOSP, Oct 2001. Design and evaluation of a wide-area event notification service. Carzaniga et al. TOCS 19(3), Aug 2001. |
||
|
Matching Events in a Content-based Subscription System. Aguilera et al. 18th PODC, 1999. |
||||
|
Yao Yue |
10/23 |
Staggeringly large file systems |
File and storage systems: The Google file system. Ghemawat, Gobioff, Leung. SOSP-19, Oct 2003. |
Why Gnutella can't scale, no really? Ritter, Feb 2001. |
|
Kiyan Ahmadizadeh |
10/25 |
Application-Level Multicast Routing |
||
|
Overcast: Reliable Multicasting with an Overlay Network Jannotti et al. 4th OSDI, Dec 2000. |
||||
|
Yao
Yue
(Ken
out of town, Lakshmi Ganesh will cover for him) |
10/30 |
Peer to peer dissemination |
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. |
||||
|
Ken (“chalk talk”) |
11/1 |
Epidemic Techniques |
Epidemic algorithms for replicated database maintenance; Demers et al. 6th PODC, 1987. |
|
|
|
11/6 |
Ordering and Consistent Cuts |
Time, Clocks, and the Ordering of Events in a Distributed System. Lamport. CACM 21(7). July 1978. |
|
|
|
11/8 |
Time |
Optimal Clock Synchronization. Srikanth and Toueg. JACM 34(3), July 1987. |
Using Time Instead of Timeout for Fault-Tolerant Distributed Systems. Lamport. ACM TOPLAS 6:2, 1974 |
|
Probabilistic Internal Clock Synchronization. Cristian and Fetzer. |
||||
|
11/13 |
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. |
||||
|
Ken |
11/15 |
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. |
|
Ken |
11/20 |
Practical Replication |
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.
Robbert and Fred: Chain Replication
The
Costs and Limits of Availability for Replicated Services. Yu and Vahdat. 18th SOSP, Oct 2001. |
|
Dan Freedman |
11/27 |
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 |
||||
|
Barry Burton |
11/29 |
Byzantine Techniques |
The Byzantine Generals Problem. Lamport et al. ACM TOPLAS 4, 1982. |
Randomized Byzantine Generals. Rabin. FOCS, 1983.
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. |
How to prepare a cs614 presentation
Each
time we meet, we’ll start with a fairly short presentation, lasting
perhaps 45 minutes, after which there will be a discussion lasting an
additional half hour or so.
Preparing the lecture is a significant challenge and you should expect
to spend as much as a week or two working on it before the date of your
presentation.
For
each date, there are several suggested references. Any one of these papers could be the
subject of a full-length lecture in itself, and several would take multiple
lectures to cover in any depth.
Accordingly, you face a tough choice: either learn to speak at an
extremely rapid rate, which will be completely incomprehensible, or select
within the material, focusing on a core aspect or idea and leaving the
surrounding material for others to either absorb simply by virtue of having
done the readings, or to raise during the discussion.
Your
choice of material and approach to the presentation should satisfy several
properties:
1) Within 45 minutes
you only have time to convey a very small number of technical points. For example, you probably have time to
state a single theorem and to present its proof, but even if the paper contains
many theorems, unless they are very simple you won’t have time to talk about
more than one (perhaps two).
2) Every talk needs
to be placed in context. You need
to plan on starting by spending at least a few minutes (10 would be a good
estimate) explaining what the problem attacked by the authors was, why this was
an important problem (what alternative ideas were being advanced at the time?)
and what prior work people need to be aware of. You should say enough about this prior
work to place the results you’ll focus on into a broader setting.
3) You should tell
us what you’ll be telling us, but in a non-technical way. For example, if you are presenting the
“consistent cuts” paper, give some intuition into what a consistent
cut is all about before trying to define the idea formally. As you move into the formal material,
remind us of this intuition and show us how the formal definition captures the
intuitive one. Your job is to make
the formalism seem natural. If you
are talking about a systems result, try and talk about the thing the authors
are doing from a high level – why did this excite them, and the
community? What was the key
question they were interested by, and what was their “angle”?
4) Now, perhaps 10
to 15 minutes into your “slot” you’ll get to the more
detailed material. This is where
you might briefly explain a formalism and present a theorem and its proof, or
lay out the major architectural pieces of a system and explain how they were
put together.
5) In the second
half of the technical part of your talk, you might illustrate the way that a
proof works using a small example, or present the experimental data associated
with a systems paper. Systems
people tend to be nearly obsessive about experimental data. It should be presented lovingly with
attention to the insights that can only be gained by really building something
and putting it through its paces.
Where are the fundamental costs in an approach? How well does it scale? Are their little warts and hidden problems
that the data reveals?
6) In the final part
of your talk, you should wrap things together by reminding us what the original
premise of the paper you presented was, how the authors attacked the problem,
and what the data revealed about the limitations and successes of their
approach. Express your opinions at
this stage. For a theory talk, try
and put the results back into the broader context. Do they say something broad and
powerful, or is the main insight narrow?
Your
talk will need to be on Powerpoint slides (or some similar system, if you
prefer something else). Powerpoint
makes suggestions about font sizes but in fact you can certainly pack more on a
slide than is possible using the intial choices. Keep in mind that your audience has to
be able to read the slides when projected on a screen at a sensible size! Either make plastic slides, or have your
material on a laptop that can connect to the overhead display system.
PLEASE
DON’T MAKE US WAIT 10 MINUTES WHILE YOU FIDDLE WITH CONNECTIONS AT THE
START OF CLASS. COME EARLY AND MAKE
SURE YOUR DISPLAY SETUP WILL WORK.
DO IT THE DAY BEFORE IF POSSIBLE.
People
who have never given formal talks before often make one of two kinds of
mistakes: they estimate their own pace incorrectly, or they simply make far too
many slides. Generally, figure that
you can cover one slide with text on it per minute. About half of your material should be
graphics or illustrations of some sort – people get bored with endless
text.
So,
for a 45 minute talk, you would probably make up something like 30 to 35 slides
of actual text and an addition 10 to 15 that are mostly pictures you’ll
explain during the talk. Often you
can copy some of this material right out of the online versions of papers or
from the web site of the author.
However, we probably won’t have a network connection in the
lecture room, so your slides do need to be self contained.
A
fast speaker who is comfortable in front of a group and familiar with her
slides could perhaps use as many as 60 slides for a 45 minute talk. But she would need to have relatively
little text on each slide to get away with this.
Feel
free to stray from the papers I’ve suggested. But do read the papers I suggested. It may be wise to start reading them two
weeks early, since many are tough, high-content papers with a lot of meat to
them. People attending the class
really should read them too, but probably will do so the day before your talk
and won’t have time to really pick away at the material and think hard
about it. So your job is to take
them to a deeper level of understanding than they will have gotten in reading
the papers quickly over a few beers.
And their job is to have read the papers carefully enough to contribute
to a spirited discussion in class.