Schedule
ADS lectures are held on Monday 5-7 at 308, Chenruiqiu Building.Paper & Questions
Lec.2 Question (Do not need to submit.)
Paper: Memory Coherence in Shared Virtual Memory System
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 (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
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
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
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
Paper: The Chubby lock service for loosely-coupled
distributed systems
Please compare the difference between consistent client caching and time-based caching.
Lec.9 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.10 Question
Paper: Distributed
GraphLab
How does distributed GraphLab provide consistency in parallel computing,
and which consistency is supported by distributed GraphLab?
Lec.11 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.12 Question
Paper: GraphChi
Please briefly describes how parallel sliding windows works.
Lec.13 Question
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.