Advanced
Distributed System 2019

Schedule

Week	Lecture	Paper reading
2.25	Lec.1: Introduction and Distributed Systems Lecture Slides
3.04	Lec.2: Sequential Consistency Lecture Slides     Paper
3.11	Lec.3: Eventual Consistency Lecture Slides     Paper&Question	Reading Redblue consistency
3.18	Lec.4: Recovery & Logging Lecture Slides     Paper	Reading Aether
3.25	Lec.5: Distributed Sandbox Lecture Slides     Paper
4.01	Lec.6: Concurrency Control: 2PL / SI Lecture Slides     Paper&Question	Reading Parallel snapshot isolation
4.08	Lec.7: Consensus: 2PC Lecture Slides     Paper&Question	Reading Percolator
4.15	Lec.8: Consensus: Paxos Lecture Slides     Paper&Question	Reading RAFT
4.22	Lec.9: NFS & GFS & Chubby Lecture Slides     Paper&Question	Reading TFS
4.29	Lec.10: Data-parallel programming: MapReduce & Dryad Lecture Slides     Paper&Question	Reading TensorFlow
5.06	Lec.11: Graph: Pregel & GraphLab Lecture Slides     Paper&Question	Reading PowerGraph
5.13	Lec.12: Graph Advance: PowerLyra & BiGraph Lecture Slides     Paper&Question	Reading #1 CUBE	Reading #2 TUX2
5.20	Lec.13: Graph processing on Single machine: GraphChi Lecture Slides     Paper&Question	Reading #1 X-Stream	Reading #2 GridGraph
5.27	Lec.14: Multicore & NUMA: Phoenix & TMR Lecture Slides     Paper&Question	Reading Polymer	Reading #2 Thread and Memory Placement
6.03	Lec.15: Fault-tolerance for Computation: Imitator Lecture Slides     Paper	Reading Zorro
6.10	Lec.16:Review Lecture Slides

Paper & Questions

Lec.2 Question (optional: no need to answer)

Paper: Shared Virtual Memory
ivy-code.txt is a version of the code in Section 3.1 with some clarifications and bug fixes. The write fault handler ends by sending a confirmation to the manager, and the "Write server" code in the manager waits for this confirmation. Suppose you eliminated this confirmation (both the send and the wait) from the system. Describe a scenario in which lack of the confirmation would cause the system to behave incorrectly. You should assume that the network delivers all messages, and that none of the computers fail.

Lec.3 Question

Paper: Don't Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS
Suppose an application client at data center D1 writes object x with version 2 (x_2) and then object y with version 3 (y_3). Suppose y_3 has propagated from data center D1 to data center D2 but x_2 has not yet arrived at D2. Suppose another application client data center D2 has just read Y_3, is it possible that it might read x_1 next? (If not, why not?) Will the client be blocked waiting for x_2 to arrive from D1? (If not, why not?)

Lec.4 Question (no need to bring it to the class :) )

Paper: Reimplementing the Cedar File System Using Logging and Group Commit
At the end of Section 4, the paper says that during a one-byte file create FSD writes the leader+data page synchronously to the disk, but records the update to the file name table in memory and only writes it back to disk later. Why do you suppose the FSD designers decided to write the data page synchronously? What (if anything) might go wrong if FSD instead wrote the file's data in the in-memory disk cache, and only wrote it to disk later?

Lec.5 Paper

Paper: Royan

Lec.6 Question

Paper & Question: A Critique of ANSI SQL Isolation Levels
Snapshot isolation (SI) differs from serilizatiability due to one anomaly that is possible under SI but not under serilizatiability. Describe the anomality and also give a concrete application for which the anomaly is undesirable.

Lec.7 Question

Paper: Sinfonia: A New Paradigm for Building Scalable Distributed Systems
What's the difference between coordinator in mini-transaction's 2PC protocol and standard 2PC protocol?

Lec.8 Question

Paper: Paxos made simple
Suppose that the acceptors are A, B, and C. A and B are also proposers. How does Paxos ensure that the following sequence of events can't happen? What actually happens, and which value is ultimately chosen?

A sends prepare requests with proposal number 1, and gets responses from A, B, and C.
A sends accept(1, "foo") to A and C and gets responses from both. Because a majority accepted, A thinks that "foo" has been chosen. However, A crashes before sending an accept to B.
B sends prepare messages with proposal number 2, and gets responses from B and C.
B sends accept(2, "bar") messages to B and C and gets responses from both, so B thinks that "bar" has been chosen.

Lec.9 Question

Paper: The Chubby lock service for loosely-coupled distributed systems
Please compare the difference between consistent client caching and time-based caching.

Lec.10 Question

Paper: MapReduce
In MapReduce each Mapper saves intermediate key/value pairs in R partitions on its local disk. Contrast the pros and cons of this approach to the alternative of having Mappers directly send intermediate results to R reducers that shuffle and save intermediate results on reducers' local disk before feeding them to the user- defined reduce function.

Lec.11 Question

Paper: Distributed GraphLab
Distributed GraphLab: a Framework for Machine Learning and Data Mining in the Cloud Question: How does distributed GraphLab provide consistency in parallel computing, and which consistency is supported by distributed GraphLab?

Lec.12 Question

Paper: PowerLyra
Please explain the claim in the paper "For high-degree vertices, the upper bound of increased mirrors due to assigning a new high-degree vertex along with in-edges is equal to the number of partitions (i.e. machines) rather than the degree of vertex".

Lec.13 Question

Paper: GraphChi
Please briefly describes how parallel sliding windows works.

Lec.14 Question

Paper: TMR
Why does Tiled-MapReduce iteratively process small trunks of data instead of large chunks as traditional MapReduce?