Reading Schedule for CS87, Spring 2016
Submitting Reaction Notes
Reading List of Papers
You will be assigned to a reading group for the semester. Each group
of will consist of 3 or 4 students who are in the same lab section.
We will use the Monday lab times for paper discussions and
Reading groups will meet weekly, their main tasks are:
- Paper discussion and Group Reaction Note writing
to be done prior to the class meeting when we discuss the
assigned paper. This will be an almost weekly event,
so you should schedule a regular weekly meeting time with
your group for working on the following:
If your group is responsible for posting the discussion summary
of the paper to the wiki, then you should
- Meet and discuss the weekly paper prior to the
class meeting in which we will discuss the paper (typically
during Monday lab, later in the semester we may use Tuesday
class time as well).
- Prior to meeting with your Reading group, each group member
should have read the paper (typically more than once:
tips for reading papers), and written their own notes
for the three sections of the Reaction Notes document that you
will write together.
- After/during your discussion of the paper, together you will
work on a single Reaction Notes document (1-2 pages) that will
be submitted by your Reading Group in class on the day we
discuss the paper. One Reaction Notes write-up will be
submitted per Reading Group. Group members should take
turns with the actual write-up. However, you are all
responsible for its content and will all receive the same grade
At the top of your document include:
- Group: list the names of all group members
- Write-up: list the name of the group member who wrote-up
these particular Reaction Notes for the group.
- wiki indicate if your Reading Group is responsible
for the wiki discussion summary for this paper.
- Meet after the in-class discusion to share notes on the
in-class discussion and work together to post them to the wiki.
- The discussion notes should be posted on or before Saturday
of the week we discussed the paper.
- Sometimes your Reading Group will be assigned a group class
presentation that you will work on, and practice, together. Your
group will also serve as an audience for practice talks of
presentations that you will give in class. As group members, you
will help each other polish talks for class presentations.
For most papers we read, your reading group will together 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'd like. They should be about 1 page in
length (not counting the optional section).
The point of Reaction Notes is not that you demonsrate that you have
interpreted everything in the paper 100% correctly (although you should
strive for good interpretation), but that you have thought about the
important ideas presented, that you have thought about a specific
question about the paper, and that you are thinking
about questions prior to in-class discussion. Having an interesting
question about the paper is meaningful and important Reaction Notes
content. It is also to give you practice with written presentation
of your evaluation of a technical paper.
Reaction notes should should reflect your critical reading of the paper.
Reaction notes should be in your own words.
Cutting and pasting prose from the paper into your notes is plagerism.
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.
My tips for reading CS textbooks may also be helpful, but this
is a different type of reading.
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.
- Optional Section: Group Discussion :
An addtional, and optional, extra page to your Group's Reaction
Notes document (and please make this a separate page if you submit this),
is to present/explain/list of any differences of interpretation about
part of the paper on which your group was unable to reach a consensus.
Differences about big ideas can go in your paper summary: "Some in our
group thought that the main contribution of the work was X bacause Y.
Others thought it was Z because of Q." But this optional section can
be for other discussions that don't fit well into the required parts.
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, one reading
group in each discussion section will be responsible for posting notes
from the discussion on the class wiki:
Discussion summaries should not be a verbatim transcript of the class
discussion, but should capture the main points discussed, what we
thought were the most important parts of the paper(s), include any
systems/approachs that were discussed, trade-offs, strengths and
weaknesses, applications of, interesting examples, etc. Unlike Reaction
Notes where I want them written in a prose-style, using lists and bullets
points for parts of this is fine. These should be a few paragraphs long.
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
Paper Assignement 1: Due Monday Jan 25 in lab
Paper Assignment 2: Due Monday Feb 1 in lab
Reaction Notes paper on 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.
Also Skim paper on Network Communication:
Skim papers are ones you should read through quickly to try to get a big picutre.
They are related to the main Reaction Notes paper(s). They may present
comparision systems, provide a example, or help explain some parts of the
main Reaction Notes paper.
- The Design Philosophy of the DARPA Internet Procotols
David D. Clark, Proceedings of the 1988 SIGCOMM Symposium, pp 106-114,
Stanford, CA, August 1988.
We will discuss this paper briefly and at a high-level. As you skim
through it try to understand the main goals and a rough idea of
how those lead to separate protocol layers TCP and IP (and UDP-IP).
You do NOT need to know, nor understand, the details of IP, UDP, TCP.
Nor do you need to know any of the other protocols presented
(just FYI: ISO-OSI is the original layered protocol model for
communication networks, and X.25 is an older protocol for
packet switched networks (pre-dating IP)).
Paper Assignment 3: Due Monday Feb 8 in lab
Reaction Notes Papers (2 papers) on Parallel Languages:
Don't get too bogged down in the code examples in these, focus on
the language, goals, and types of parallelization and target systems.
OpenMP: An Industry-Standard API for Shared-Memory Programming
by Leonardo Dagum and Ramesh Menon, in IEEE Computational Science
and Engineering, January 1998
(local copy: openmp.pdf)
Note: in the Fortran code examples, lines that begin with 'c' are comments.
The Lawrence Livermore National Laboratory
OpenMP tutorial has
examples in C and C++.
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
(local copy: mpi.pdf)
Reaction Notes Question:
What are the target systems for MPI and
OpenMP? How well would each fit for programming on a cluster of multicore
nodes? Explain the strengths and weakness of each for such a system.
Paper Assignment 4: Due Monday Feb 15 in lab
Reaction Notes Paper CUDA: GPGPU Programming
- Scalable Parallel Programming with CUDA by Nickolls, Buck, Garland, and Skadron, in ACM Queue Magazine, Volume 6 Issue 2, March/April 2008. (and here is an on-line version with different formatting)
For the Summary part of your Reaction Notes, breifly describe the
CUDA programming model, and include a short definition of thread,
block and warp.
Reaction Notes Question:
Compare the the level of programming abstraction presented by CUDA to
MPI and OpenMP. What is exposed to the programmer and what is abstracted
away in CUDA? Which of these three languages to you think are the
easiest to program in and which the most difficult? Why?
- Also Skim (super-skim this one: just get the motivation for this language,
you can ignore all the details):
Chestnut: A GPU Programming Language for Non-Experts, by Stromme, Carlson, Newhall, in PMAM'12,
Paper Assignment 5: Due Monday Feb 22 in lab
Some related work (FYI) on languages and libraries for DSM:
Unified Parallel C (UPC), Titanium, Chapel, openSHMEM.
has links to others.
Paper Assignment 6: Due Monday Feb 29 in lab
Paper Assignment 7: Due Monday March 14 in lab
Paper Assignment 8: Due Monday March 21 in lab
Reaction Notes Paper Large Scale Distributed Systems
Read both of these papers. Reaction notes for only the
second paper: "Lessons from Giant-Scale Services".
- Fallacies of
Distributed Computing Explained 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: Explain the DQ principle in your own words.
What is the main idea of the DQ principle? Describe how it can be applied
to evaluating the design choices of replication vs. partitioning of data.
Paper Assignment 9: Due Monday March 28 in lab
Reaction Notes Paper Authentication
"Kerberos: An authentication service for open network systems."
J. G. Steiner, B. C. Neuman, and J. I. Schiller
In Proceedings of the Winter 1988 Usenix Conference, pages 191-201,
Reaction Notes Question:
There is no specific question for this paper. For your reaction notes,
write the summary of the Kerberos paper, and step through the
authentication protocol in your reading group.
Week 11(April 4): No paper discusion: Project Work Week
Paper Assignment 10: Due Monday April 11 in lab
Reaction Notes Paper Cloud Computing
A View of Cloud Compuring
M. Armbrust, A. Fox, R. Griffith, A. D. Joseph, R. H. Katz,
A. Konwinski, G. Lee, D. A. Patterson, A. Rabkin, I. Stoica,
M. Zaharia, Communications of the ACM, April 2010.
Reaction Notes Question: No reaction notes this week due
to your mid-project reports and presentations. But read this paper
and be prepared to discuss it in class on Monday.
Paper Assignment 11: Due Monday April 18 in lab
Reaction Notes Paper Cloud Job Management
Large-scale cluster management at Google with Borg, Verma, Pedrosa, Korupolu, EuroSys, 2015
Reaction Notes Question: Define performance isolation
and evaluate a way in which Borg provides it.
Some the the systems/tools mentioned in this paper include:
Chubby is google's distributed lock server;
Bigtable is google's data storage
system, with a database table-like structure and a map interface to
the data ((key,value) pairs));
Paxos is a distributed consensus protocol (a
protocols for multiple distributed entities to reach an agreement in
the presence of failures).
- Also for Fun (briefly skim, we may discuss a bit):
"The Internet Worm: Crisis and Aftermath", Eugene H. Spafford, Communications of the ACM, 1989