Schedule
ADS lectures are held on Monday 6-8(12:55-15:40) at 308, Chenruiqiu Building.Paper & Questions
Lec.3 Question.1
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 (Do not need to submit.)
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 Question.2
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.6 Question.3
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.7 Question.4
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.8 Question.5
Paper: Google File System
Describe a sequence of events that result in a client reading stale data from the Google File System.
Lec.9 Question.6
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.10 Question.7
Paper: Distributed
GraphLab
How does distributed GraphLab provide consistency in parallel computing,
and which consistency is supported by distributed GraphLab?
Lec.12 Question.8
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.9
Paper: GraphChi
Please briefly describes how parallel sliding windows works.
Lec.14 Question.10
Paper: TMR
Why does Tiled-MapReduce iteratively process small trunks of data
instead of large chunks as traditional MapReduce?
Credits: questions and papers from MIT 6.824 and part of slides come from Paul Krzyzanowski (Rutgers), Haibo Chen (SJTU) and et al.