Advanced
Distributed System

Schedule

Week	Topic-1	Topic-2
1	Sept.11 Lec.1: Intro-Labs Overview, Frangipani - Lab1 released. Lecture Slides     Lab1 Slides	Sept.14 Lec.2: Programming tools:Threads and RPCs. Preparation: Paper&Question Lecture Slides
2	Sept.18 Lec.3: Java RMI, google protocol buffer. Preparation: Paper&Question Lecture Slides	Sept.21 Lec.4: MapReduce, Dryad(Linq). Preparation: Paper&Question Lecture Slides
3	Sept.25 Lec.5: Consistency: Sequential consistency Preparation: Paper&Question Lecture Slides     Lab2 Slides	Sept.28 Lec.6: Consistency: Relaxed consistency Preparation: Paper&Question Lecture Slides
4	Oct.9 Lec.7: Eventual Consistency Preparation: Paper&Question Lecture Slides	Oct.12 Lec.8: Cash Recovery Preparation: Paper&Question Lecture Slides
5	Oct.16 Lec.9: Concurrency control Preparation: Paper&Question Lecture Slides     Lab3 Slides	Oct.19 Lec.10: Two-phase commit Preparation: Paper&Question Lecture Slides
6	Oct.23 Lec.11: Fault Tolerance: Consensus Preparation: Paper&Question Lecture Slides	Oct.26 Lec.12: Large Graph Processing Preparation: Paper&Question Lecture Slides
6	Oct.30 Lec.13: Course Review and Industrial Trends of DS Preparation: Paper&Question	Nov.2 Lec.14: Preparation:

Paper & Questions

Lec.2 Question

Paper: Implementing remote procedure calls
The RPC package described in the paper provides at-most-once semantics (see page 49, last paragraph). Based on the introduction section of lab 1, what kind of semantics do you think the 6.824 RPC implementation has (before you change it by completing lab 1)? How does this difference affect the implementation of your lock server for lab 1?

Lec.3 Question

Paper: A Distributed Object Model for the Java System
Suppose that you re-implemented lab1 using using Java RMI. In what ways might your code become simpler compared to your C++ implementation? Give one or two specific examples.

Lec.4 Question

Paper: DryadLINQ
Suppose you want to implement a distributed program that counts word frequencies, taking as input a collection of files with words in them. Sketch how this program might be implemented using Dryad, and explain how it gets parallel speedup on a cluster.

Lec.5 Question

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.6 Question

Paper: TreadMarks
Suppose that a simplified version of Treadmarks, called Dreadmarks, simply sent all modifications of variables between an acquire and a release to the next processor to acquire the same lock. No other modifications are sent. What changes does Treadmarks send that Dreadmarks does not? Outline a specific simple situation in which Treadmarks would provide more useful or intuitive memory behavior than Dreadmarks.

Lec.7 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.8 Question

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.9 Question

Paper: 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.10 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.11 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.12 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.13 Question

Paper: AnalogicFS experience paper
In many ways, this experiences paper raises more questions than it answers. Please answer one of the following questions, taking into consideration the rich history of AnalogicFS and the spirit in which the paper was written:
a) The analysis of A* search shown in Figure 1 claims to be an introspective visualization of the AnalogicFS methodology; however, not all decisions are depicted in the figure. In particular, if I <= P, what should be the next node explored such that all assumptions in Section 2 still hold? Show your work.
b) Despite the authors' claims in the introduction that AnalogicFS was developed to study SCSI disks (and their interaction with lambda calculus), the experimental setup detailed in Section 4.1 involves decommissioned Gameboys instead, which use cartridge-based, Flash-like memory. If the authors had used actual SCSI disks during the experiments, how exactly might have their results changed quantitatively?
c) AnalogicFS shows rather unstable multicast algorithm popularity (Figure 5), especially compared with some of the previous systems we've read about in 6.824. Give an example of another system that would have a more steady measurement of popularity pages, especially in the range of 0.1-0.4 decibels of bandwidth.
d) For his 6.824 Lab 9 project, Ben Bitdiddle chose to extend YFS such that it faithfully emulates the constant expected seek time across LISP machines, as AnalogicFS does. Upon implementation, however, he immediately ran into the need to cap the extent size to 400 nm, rather than 676 nm. Explain what assumptions made for the AnalogicFS implementation do not hold true for YFS, and why that changes the maximum extent size.