Reading Schedule for CS87, Spring 2012
Submitting Reaction Notes
Reading List of Papers
For most papers we read, you will write reaction notes prior to our
class meeting to help prepare you for discussing the paper. You
should bring a print out of your reaction notes and the paper to class
with you. Reaction notes can be written in ascii, or Word, or latex, or
... whatever you want.
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?
some tips for reading research papers
Reaction notes should be no more than one page in length and
structured in the following way:
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
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
Bring to class a printout of your reaction notes and the paper to
discuss. You will hand in your reaction notes at the end of class.
For the weeks in which we read and discuss research papers, we will
spend time summarizing the paper discussions at the end of the week.
Students will take turns writing up the group summary on the
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
$ lpr file.ps
$ mpage -2 -M-10 -dp file.ps | lpr
You can view (and print) pdf files using acroread
$ acroread file.pdf
$ xpdf file.pdf
In addition to the assigned readings, there
are some related paper references here:
Additional Cluster and Distributed Computing Papers
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.
Read through this for Tuesday's lecture. We may also discuss it
a bit in class on Thursday along with Thursday's paper.
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 meant by an endpoint? Is there
any benefit to putting 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.
We will likely discuss Tuesday's paper a bit as well.
For Thursday Parallel Programming Languages
OpenMP: An Industry-Standard API for Shared-Memory Programming
by Leonardo Dagum and Ramesh Menon, in IEEE Computational Science
and Engineering, January 1998
Reaction Notes Question:
What is meant by data parallelism and task parallelism? What makes pthreads
a task parallel programming model?
Note: in the Fortran code examples, lines that begin with 'c' are comments
Look at this week's reading from the textbook (p.193-199) on OpenMP
for an openMP example in C.
For Tuesday Large Scale Distributed Systems
Read both of these papers for Tuesday. Write reaction notes for only the
second paper: "Lessons from Giant-Scale Services".
- Fallacies of
Distributed Computing Explained: Explaining Peter Deutsch's fallacies of
distributed computing (introduced circa 1994) and their relevance for today's
distributed systems. by Arnon Rotem-Gal-Oz
- Lessons from Giant-Scale Services by
Eric A. Brewer, IEEE Computing, 2001
(note: the "levels" refer to the ISO-OSI standard. Level 7 is application,
like http, and level 4 is transport, like TCP.)
Reaction Notes Question:
Pick a system that you have used that fits their definition of giant-scale
services (ex. Facebook, Google, Yahoo, Amazon, CNN, YouTube, ...), and
briefly describe or list in what ways it fits their definition.
This paper advocates replication over partitioning, although not
necessarily exclusively. How well does this conclusion fit the system
you pick? Explain why and/or why not and describe when it does fit and/or
when does it not.
For Tuesday Distributed Shared Memory
TreadMarks: Shared Memory Computing on Networks of Workstations,
C. Amza, A. L. Cox, S. Dwarkadas, P. Keleher, H. Lu, R. Rajamony, W. Yu, and W. Zwaenepoel, IEEE Computer, February 1996.
Reaction Notes Question: Describe Lazy Consistency.
What data consistency guarentees does it make? Evaluate Lazy Consistency
for Distributed Shared Memory systems (why? what are the trade-offs? explain.)
For Thursday Peer-to-Peer Look up
- Chord: A Scalable Peer-to-peer Lookup Protocol for
Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger, M.
Frans Kaashoek, Frank Dabek, Hari Balakrishnan, IEEE/ACM Transactions on
Networking, Vol. 11, No. 1, February 2003
Reaction Notes Question: In addition to the summary
part of your reaction notes, add a detailed explaination of
how the Chord lookup protocol works: explain it in detail in your own
For Tuesday Cluster Node Architecture
- Incorporating Network RAM and Flash
into Fast Backing Store for Clusters", Tia Newhall and Douglas Woos,
Proceedings of IEEE Cluster, Austin, TX, September 2011
Reaction Notes Question: Network RAM and Distributed Shared
Memory are related in some ways. Discuss in which ways they are similar
and in which ways they are different. What are strengths and weaknesses
of each? Make sure to explain your answers (why/how).
Section 3 of the first Nswap paper
has more details about Nswap's Network RAM. You may want to refer to
this paper to help you answer this question.
For Tuesday Security
- Computer Security in the Real World, Butler W. Lampson, IEEE Computer,
June 2004 (vol. 37 no. 6)
Reaction Notes: Just do the summary part of the reaction notes for this
paper. Also, list any terminology with which you are not familiar (and look
it up and see if you can find a definition for it, and if so include a short
- and skim over Chapter 2 (p.13-30) of this: The Datacenter as a Computer: An Introduction to the Design of Warehouse-Scale Machines,
Luiz Andre Barroso and Urs Holzle, Synthesis Lectures on Computer
Architecture, Morgan and Claypool Publishers, 2009
For Thursday Map Reduce
- MapReduce: simplified data processing on large clusters, Jeffrey Dean and Sanjay Ghemawat, Communications of the ACM,
Volume 51 Issue 1, January 2008
Reaction Notes: No reaction notes due for this one, but be prepared to
discuss it in class.