Reading Schedule for CS87, Spring 2018
Contents:
Reading Groups
Reaction Notes
Reading List of Papers
Reading Groups
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
presentations.
The Reading Groups for Spring 2018
Your reading group will meet weekly to do the following main tasks:
- 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:
- Meet and discuss the weekly paper prior to the class meeting in which
the paper will be discussed.
- Prior to meeting with your Reading group, each group member should have
critically read the paper
(tips for reading research papers),
and written their own notes for the
Reaction Notes document that you will write together.
- After your group's discussion of the paper, together you will
work on a single Reaction Notes document that will
be submitted by your Reading Group.
One Reaction Notes write-up will be
submitted per Reading Group. Group members should take
turns with lead editing repsonsibility of the write-up. However,
you are all responsible for
its content and will all receive the same grade on it.
READ THIS: Reacation Notes Requirements for the requirments about Reaction Notes content and structure,
guidlines for discussion roles during your reading group meetings, the latex template
and Reaction Notes git repo information, and submission instructions.
- Once during the semester, your group will be responsible for posting a
summary of the in-class discussion of the paper(s) to the moodle wiki.
You should:
- meet after the in-class discusion to share notes on the
in-class discussion and work together to post them to the wiki.
- Your group's discussion notes should be posted on or before
Saturday of the week we discussed the paper.
- The notes should be a summary of the class's discussion of the
paper
highlighting main ideas and points discussed from the paper, and
including any interesting discussions, questions, disagreements,
ideas or connections that may have come up. They should be about
1 page in length and feel free to use bullet points for some content.
Once your group has posted these, other students are welcome and
encouraged to add content to these summaries. Please, respectful
disagreements and do
not remove or change anyone else's post (you can add only).
- Sometimes your Reading Group will be assigned a group class
presentation that you will work on and practice together. Your
group can also serve as an audience for other practice talks or
presentations that you will give in class. As group members, you
will help each other polish talks for class presentations.
Reaction Notes
For most papers we read, your reading group will write
reaction notes that you will submit prior to our class meeting. The
purpose is to help you prepare for in-class discussions of papers.
Bring a print out or electronic version of your reaction notes and the
paper(s) to class with you.
READ THIS: Reacation Notes Requirements. It includes reqirements and details about Reaction
Notes, discussion roles for your reading group meeting, the latex template
and repo information, and submission instructions.
Reading List
In addition to the assigned weekly readings, there
are some related paper references here:
Additional Cluster and Distributed Computing Papers
Viewing and Printing Papers
You can view and print
pdf files using acroread or evince:
$ acroread file.pdf
$ evince file.pdf
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 try viewing in gs or
convert it to pdf and view it using acroread:
$ gunzip file.ps.gz
$ gs file.ps
$ ps2pdf file.ps # creates file.pdf you can open with acroread
You can
print postscript using lpr:
$ lpr file.ps
$ mpage -2 -M-10 -dp file.ps | lpr # using mpage to create a 2-up version
Paper Assignement 1: Due Monday Jan. 29
Paper Assignment 2: Due Monday Feb 5
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.
Quick Read* paper on 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.
(note: David Clark is a Swarthmore alumn)
* About Quick Read Papers
With the main Reaction Notes paper(s) each week, there may also be
a Quick Read paper assignment. Quick Read papers are ones
you should read through less thoroughly than the
main paper(s)--read through one time to try to get a big picture ideas of
the paper.
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. We discus them in class, but not at the
same depth level as the main paper(s).
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 12
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 19
Reaction Notes Paper on CUDA and 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?
Quick Read Paper: read for big ideas
- OpenCL: A Parallel Programming Standard for Heterogeneous Computing Systems by
Stone, Gohara, Shi. In IEEE Computing in Science and Engineering
(Vol: 12, Issue: 3), 2010
(the .pdf of the full paper is on left side of page if you scroll down)
Paper Assignment 5: Due Monday Feb 26
Reaction Notes Paper on 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.)
FYI: Some related work in Distributed Shared Memory
- Languages and libraries: Unified Parallel C (UPC), Titanium,
Chapel, openSHMEM.
pgas.org (Partitioned Global Address
Space) has more info.
Paper Assignment 6: Due Monday March 05
Pre-Reaction Notes Paper Paper
- Read/skim through this first before
reading the Chord paper
Chapt 2. What is this "Peer to Peer" About?
by Steinmetz R., Wehrle K. (eds) Peer-to-Peer Systems and
Applications. Lecture Notes in Computer Science, vol 3485.
Springer, Berlin, Heidelberg, 2005
(you can download this chapter from link on this page)
Reaction Notes Paper on Peer-to-Peer Systems
-
Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications,
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:
Explain in your own words how the Chord lookup protocol works;
do not repeat all the details, but describe the big idea of
how it works and why it is desgined that way.
Paper Assignment 7: Due Monday March 19
No reaction notes this week, and no reaction notes papers.
Instead, read through these 2 quick read papers, and be
prepared to discuss them at a high-level on Monday.
(both papers are also available off the Publications part of my webpage)
Quick Read Papers:
-
Chestnut: a GPU Programming Language for Non-experts,
Andrew Stromme, Ryan Carlson, Tia Newhall, PMAM'12
-
PeerMon: A Peer-to-Peer Network Monitoring System,
Tia Newhall, Jānis Lībeks, Ross Greenwood, Jeff Knerr, LISA'10
peermon webpage
Paper Assignment 8: Due Monday March 26
Paper Assignment 9: Due Monday April 2
Reaction Notes Paper on Google File System
- The Google File system, Sanjay Ghemawat, Howard Gobioff, Shun-Tak Leung, SOSP'03.
Reaction Notes Question:
In what ways did the intended use of the file system lead to its design?
Pick one of these ways to discuss in more details (include explaination of
why the resulting design choice fits its intended use, and critic the design choice in terms of how well it meets its goal (and explain why)).
Week 11(April 9): No paper discusion: Project Work Week
Paper Assignment 10: Due Monday April 16
Reaction Notes Paper on Distributed Hash Tables
- Scalable, Distributed Data Structures for Internet Service Construction , Steven D. Gribble, Eric A.
Brewer, Joseph M. Hellerstein, David Culler, OSDI'00 (you can download pdf or
view html)
Also, here is some information about the: Two Phase Commit Protocol.
Skim "Assumptions" and "Basic Algorithm" to get the general idea
of the distributed 2PC protocol (ignore details and the logging parts.)
Reaction Notes Question:
Because of Project Work Week, just do parts 1 and 3 (the summary
and questions) of the reaction notes paper this week.
Paper Assignment 11: Due Monday April 23
Reaction Notes Paper on Failure and Consensus
-
The Byzantine Generals Problem, Leslie Lamport, Robert Shostak,
and Marshall Pease, ACM Transactions on Programming Languages and
Systems, Vol 4, No. 3, July 1982
Just focus on sections 1-3, skim 4 and 6, and you can skip 5.
Reaction Notes Question:
No reaction notes this week, but your reading group should meet
and together you should step through the example of applying the
algorithm. Don't get too bogged down by the proofs. Instead,
make sure you understand the algorithm, can step through examples
applying it, and have some intuition about the main proof results
(ex, why need 3m+1 with m traitors).
Also, be prepared to discuss the big ideas from
the quick read paper/presentation.
Quick Read Paper
-
Simple Testing Can Prevent Most Critical Failures:
An Analysis of Production Failures in Distributed Data-Intensive
Systems, Yuan, Luo, Zhuang, Rodrigues, Zhao, Zhang, Jain,
Stumm, USENIX OSDI'14
Either skim this paper or watch the presentation to just get
the big idea/message from this work.
Paper Assignment 12: Due Monday April 30
Cancelled: we will not meet on Monday to discuss
these readings, and you are
not responsible for reading, discussing
or submitting reaction notes for these papers. Instead, you should focus
on making a lot of progress on your project in place of reading, writing,
and discussing these. And your project group
must meet with me
on Monday April 30. Sign-up on the google sheet for a meeting time
(see my email message for the link).
The Worm paper is a fun read. I encourage you to read it over the summer.