Reading Schedule for CS85, Spring 2008
Contents:
Reaction Notes
Submitting Reaction Notes
Printing and Viewing Papers
Reading List of Papers
Reaction Notes
For most papers we read, you will post reaction notes prior to our
class meeting to help prepare you for discussing the paper. You will
also have an opportunity read other student's reaction notes prior to
the class meeting.
Reaction notes should should reflect your critical reading of the paper.
Some questions to think about as you read:
Did the authors do what they said they were going to do? What are the
important ideas (just because an author says something is important doesn't
mean it necessarily is)? Do their results make sense? Are their methods
sound? Are there weaknesses in their solution? What assumptions are they
making? How does their work fit in with other similar work? What improvements
and/or extensions to the area do they contribute? Are there terms, ideas,
techniques, that you don't understand?
Your reaction notes should be structured in the following way:
- Summary:
A 1 paragraph summary of the paper. A summary
of what the work is, what problem(s) it addresses, and the results
or new technique (if applicable). Also, include a short list of
the strengths and weaknesses of the work, and list how it is
related to other work we have read (when applicable).
- Answer to Specific Question(s):
A 1-2 paragraph answer to
the specific question(s) associated with this paper.
You are welcome to discuss other parts of the paper in addition
to answering the specific question. However, it is not required that
you do so.
- A list of questions you have about this paper:
If there are terms, ideas, techniques that you don't understand,
list them here. However, for terms you don't understand,
also try to find the answer yourself by using on-line sources such as
whatis.techtarget.com.
If you find an answer, please leave the listing of the term on your
reaction notes; it is helpful to me to see which terms are new to
students so that I can make sure that we discuss their meaning.
Submitting Reaction Notes
The papers listed below should be read prior to the class meeting
for which they are assigned, and your reaction notes should be submitted
using cs85handin before 1am the day of each class:
- write-up your reaction notes in an ascii file.
- submit them by running handin85 before 1am the day of each
class meeting
- by 1:10am, you can run, update85 to get a
copy of every student's reaction notes. These are good to
look at prior to our class meeting to help prepare you for
discussion.
Self-Evaluation and Summary
After each class discussion, you will complete a self-evaluation of
your participation in discussion and you will write a 1 paragraph summary
of the class' critical evaluation of the paper as we discussed it.
Here is a sample evaluation form (it may change):
discussion evaluation form
Viewing and Printing Papers
You can view most postscript files (and gziped postscript files)
using gv on our system:
$ gv file.ps.gz
gv cannot handle some version of postscript, in this case you should
save a copy of the paper.ps.gz file, gunzip it, and
then either view it using gs or convert it to pdf and view it using acroread:
$ gunzip file.ps.gz
$ gs file.ps
$ ps2pdf file.ps
$ acroread file.pdf
You can print postscript using lpr, or print 2-up postscript files using mpage
and lpr:
$ lpr file.ps
$ mpage -2 -M-10 -dp file.ps | lpr
You can print double sided to TheDicer:
$ lpr -PTheDicer file.ps
$ mpage -2 -M-10 -dp file.ps | lpr -TheDicer
You can view (and print) pdf files using acroread:
$ acroread file.pdf
Reading List
In addtion to the assigned readings, there
are some related paper references here:
Additional Cluster and Distributed Computing Papers
Week 1
For Thursday, Distributed Systems Overview:
- Intro to distributed Systems (handed out in class on Tuesday)
Skip part one of the reaction notes (the summary of the work) this week,
and only do part 2 and part 3 (answer to specific question below, and
a list of questions you have while reading.)
Reaction Notes Question:
Pick one of scalability, transparency, or single-system image, and define
what it is and why it is desirable in a distributed system, and discuss
some of the issues associated with supporting it.
Week 2
For Tuesday, Network Communication:
- The Design Philosophy of the DARPA Internet Procotols
David D. Clark, Proceedings of the 1988 SIGCOMM Symposium, pp 106-114,
Stanford, CA, August 1988.
- Overview of Network Communication (handout from class on Thurs)
Reaction Notes Question:
Pick one of the first three "Second Level Goals" listed in section 3, and discuss
why that goal is one of the top three and how that goal shaped the structure
of the Internet.
For Thursday, System Design:
-
End-To-End Arguments in System Design
J.H. Saltzer, D.P. Reed and D.D. Clark. ACM Transactions on Computer Systems,
4(4):277-288, November 1984
Reaction Notes Question: What is ment by an endpoint? Is there
any benefit to puting a function not at an endpoint (in a lower-level
or intermediate point)? If yes, explain what is gained by doing so and if
any guarantee about the functionality can be made by doing so. If no,
explain why not. You may want to use an example to explain your answer.
Week 3
For Tuesday, Message Passing
-
The PVM Concurrent Computing System: Evolution, Experiences, and Trends,
V. S. Sunderam, G. A. Geist, J. Dongarra, R. Manchek, ACM Journal of Parallel
Computing, vol. 20 no. 4, 1994
-
A message passing standard for MPP and workstations
J. J. Dongarra, S. W. Otto, M. Snir, and D. Walker,
CACM, 39(7), 1996, pp. 84-90
To get an idea of what the PVM user interface looks like, you may
want to take a quick look at chapt. 5 from the PVM user's guide:
Chapt. 5 from "A Users' Guide to PVM Parallel Virtual Machine" A. Beguelin,
J. J. Dongarra, G. A. Geist, R. Manchek, and V. S. Sunderam,
Oak Ridge National Laboratory, ORNL/TM-12187, September, 1994
Reaction Notes Question: On one level, PVM and MPI can be thought
of as solutions to the same problem. Define what that problem is,
describe one or two significant ways in which the solutions differ, and
discuss tradeoffs in the two approaches with respect to the difference(s)
you list.
For Thursday, Nswap
- Nswap: A Network Swapping Module for Linux Cluster,
Tia Newhall, Sean Finney, Kuzman Ganchev, Michael Spiegel.
Proceedings of Euro-Par'03 International Conference on
Parallel and Distributed Computing, Klagenfurt, Austria, August 2003.
Presentation: Tia will give a presentation of this work, as one
example of how to structure your oral presentation of a paper(s).
Reaction Notes Question: What do you think is the most difficult
problem that is being addressed by this work and why?
Week 4: Time, Event Ordering, and Distributed State
For Tuesday: Time
-
Time, clocks, and the ordering of events in a distributed system
Leslie Lamport, Communications of the ACM, 21(7):558-565, July 1978.
Reaction Notes Question: Describe in more detail what time means in
distributed systems, and what guarentees there are with respect to time and why.
Week 5
For Tuesday: Distributed State
-
Distributed snapshots: determining global states of distributed systems
, K. Mani Chandy and Leslie Lamport; ACM Trans. Comput.
Syst. 3, 1 (Feb. 1985), Pages 63 - 75
Presentation: Jeff will present this paper in class.
Jeff's talk slides
Reaction Notes Question: no question, just expand part 1 of
your reaction notes with a bit more detailed explaination.
For Thursday: Distributed File Systems
-
"Spritely NFS: experiments with cache-consistency protocols",
V. Srinivasan and J. Mogul,
Proceedings of the Twelfth ACM symposium on Operating Systems Principles,
December 3 - 6, 1989, Litchfield Pk., AZ USA
Presentation: Trilok will present this paper in class.
Trilok's talk slides
Reaction Notes Question: Discuss some of the trade-offs between
a a distributed file system that uses a stateless sever and one that
uses a stateful server.
Week 6: DFS and Condor
For Tuesday: Distributed File Systems
- The Google File System,
Sanjay Ghemawat, Howard Gobioff, Shun-Tak Leung,
Proceedings of the nineteenth ACM symposium on Operating systems principles,
olton Landing, NY, 2003
Presentation: Jake will present this paper in class.
Jake's talk slides
Reaction Notes Question: Discuss two ways in which the file system
was to be used led to its design (and include explaination as to why).
For Thursday: Condor
-
Condor - A Hunter of Idle Workstations"
Michael Litzkow, Miron Livny, and Matt Mutka, Proceedings of the 8th
International Conference of Distributed Computing Systems,
pages 104-111, June, 1988
also, just skim through the following paper to get an idea of where this project is today:
Distributed Computing in Practice: The Condor Experience,
Douglas Thain, Todd Tannenbaum, and Miron Livny,
Concurrency and Computation: Practice and Experience, Vol. 17,
No. 2-4, pages 323-356, February-April, 2005.
Presentation: Drew will present this paper in class.
Reaction Notes Question: Discuss some tradeoffs in the design
of the architecture of Condor with respect to the coordinator and
local schedulers.
Week 7: Project Work Week
For Tuesday: Project Group meetings
Each project group will meet with me for 15 minutes during our regular
classtime to discuss the details of their proposed project and their
project schedule (Project Proposal Requirements).
GROUP |
MEETING TIME |
Jeff and Phyo |
11:20-11:35 |
Trilok, Jake, Derek |
11:40-11:55 |
Adam |
12:00-12:15 |
Drew |
12:20-12:35 |
For Thursday: Project proposal presentations
Written project proposals due and project group presentations of proposed projects
Week 8: Peer-to-Peer systems
For Tuesday: P2P
-
Wide-area cooperative storage with CFS,
Frank Dabek, M. Frans Kaashoek, David Karger, Robert Morris, Ion Stoica,
Proceedings of the eighteenth ACM symposium on Operating systems principles,
Banff, Alberta, Canada, 2001
Reaction Notes Question: Explain how the fast block look-up works
in Chord, and explain in what ways it is fault tolerant.
For Thursday: P2P
- Peer-to-peer: Making gnutella-like P2P systems scalable
Yatin Chawathe, Sylvia Ratnasamy, Lee Breslau, Nick Lanham, Scott Shenker,
Proceedings of the 2003 conference on Applications, technologies,
architectures, and protocols for computer communications, August 2003
Presentation: Derek will present this paper in class.
Derek's talk slides
Reaction Notes Question: Explain how Gia's biased random walk search works, and explain in what ways it more
scalable than the search algorithm used in Gnutella.
Week 9: DSM and Security
For Tuesday: DSM
- Memory Coherence in Shared Virtual Memory Systems
K. Li and P. Hudak.
ACM Trans. Computer Systems Vol. 7, No. 4. Nov. 1989. pp. 321-359.
Reaction Notes Question: No reaction notes question, just
expand one part of your summary with a bit more detail. Also, don't
feel like you have to go through ALL the proofs in the appendicies, but
you should have a good idea of how the different approaches work and
be able to evaluate them.
For Thursday: Security
-
"Encryption and Secure Computer Networks"
Gerald J. Popek, Charles S. Kline,
Computing Surveys, 11 4, December 1979, pp. 331-356.
Presentation: Adam will present this paper in class.
Adam's talk slides
Reaction Notes Question: Define authentication and explain the
public-key based authentication scheme. Why is an authority needed in
this scheme?
Week 10: Fault Tolerance
For Tuesday:
-
The Byzantine Generals Problems,
Leslie Lamport, Robert Shostak, and Marshall Pease,
ACM Transactions on Programming Languages and
Systems, Vol 4, No. 3, July 1982
Focus on sections 1-3, just skim 4 and 6, and you can skip 5 if you'd like.
Presentation: Phyo will present this paper in class.
Phyo's talk slides
No reaction notes for this one, but step through the example of
applying the algorithm on paper or the white board before class meets.
For Thursday: no paper, project progress reports
Week 11: MapReduce and Hadoop
For Tuesday: MapReduce
-
MapReduce: Simplified Data Processing on Large Clusters
Jeffrey Dean and Sanjay Ghemawat,
OSDI'04: Sixth Symposium on Operating System Design and Implementation,
San Francisco, CA, December, 2004.
Reaction Notes Question: No reaction notes question for this one (just
do parts 1 and 2 of the reaction notes).
For Thursday: Hadoop DFS
-
The Hadoop Distributed File System: Architecture and Design, by
Dhruba Borthakur
Reaction Notes Question: Discuss replica placement and rebalancing in
Hadoop, and explain the motivation for the different choices that are made.
Week 12: Security
For Tuesday: Security
- "The Internet Worm: Crisis and Aftermath", Eugene H. Spafford, Communications of the ACM, 32 (6): 678-687, June 1989
Reaction Notes Question:
Just do part 3 of the reaction notes for this paper.
For Thursday: no paper, project progress reports
Week 13:
For Tuesday: no paper, project work day
For Thursday: Scheduling
-
A closer look at co-scheduling approaches for a network of workstations,
Shailabh Nagar, Ajit Banerjee, Anand Sivasubramaniam and Chita R. Das,
Proceedings of the eleventh annual ACM symposium on Parallel algorithms
and architectures , 1999, Pages 96 - 105
Reaction Notes Question: no question, just d parts 1 and 3 of the
reaction notes.
Week 14: Final Project Presentations
For Tuesday: Project Group meetings
Each project group will meet with me for 15 minutes during our regular
classtime to discuss their project report and presentation
GROUP |
MEETING TIME |
Jeff and Phyo |
11:20-11:35 |
Trilok, Jake, Derek |
11:40-11:55 |
Adam |
12:00-12:15 |
Drew |
12:20-12:35 |
Thursday: Project Group Presentations
Note, the change in class time (we will start at 11:15 and go through lunch).
Use my
Presentation Guide to help you structure your 30 minute project presentation.
- group 1: 11:15-11:45: Adam
- group 2: 11:45-12:15: Derek, Jake, Trilok
- group 3: 12:15-12:45: Drew
- group 4: 12:45-1:15: Jeff, Phyo