Schedule
Paper & Questions
Lec.2
Paper & Question
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
Paper & Question
MapReduce: Simplified Data Processing on Large ClustersIn 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.
Topic Papaer
Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster ComputingLec.4
Paper & Question
Memory Coherence in Shared Virtual Memory SystemsHere's a strawman implementation of a distributed shared memory system: there are three nodes (N1,N2,N2) each having a full copy of all of the memory. A read request is satisifed by reading from the local copy of the memory (i.e. if a process executes on N1, then its reads are obtained from N1's local copy of the memory). A write is forwarded to all other nodes and the process issuing the write is allowed to continue without waiting for writes to finish at remote nodes. Does this DSM implementation satisfy sequential consistency? Give concrete examples.
Lec.5
Paper & Question
Don't Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPSSuppose 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?)
Topic Paper
Making Geo-Replicated Systems Fast as Possible, Consistent when NecessaryLec.8
Paper & Question
Reimplementing the Cedar File System Using Logging and Group CommitAt 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?
Topic Paper
Segment-Based Recovery: Write-ahead logging revisitedLec.9
Paper & Question
A Critique of ANSI SQL Isolation LevelsSnapshot 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.
Topic Paper
Transactional storage for geo-replicated systemsLec.10
Paper & Question
Sinfonia: A New Paradigm for Building Scalable Distributed SystemsWhat's the difference between coordinator in mini-transaction's 2PC protocol and standard 2PC protocol?
Topic Paper
Large-scale Incremental Processing Using Distributed Transactions and NotificationsLec.11
Paper & Question
Paxos Made SimpleSuppose 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.
Topic Paper
Dynamic Reconfiguration of Primary/Backup ClustersLec.12
Paper & Question
Distributed GraphLab: a Framework for Machine Learning and Data Mining in the CloudHow does distributed GraphLab provide consistency in parallel computing, and which consistency is supported by distributed GraphLab?
Topic Paper
PowerGraph: Distributed Graph-Parallel Computation on Natural GraphsLec.13
Paper & Question
The Chubby Lock Service for Loosely-Coupled Distributed SystemsPlease compare the difference between consistent client caching and time-based caching.
Topic Paper
TFS: A Transparent File System for Contributory StorageLec.14
Paper & Question
Dynamo: Amazon’s Highly Available Key-value StoreDynamo Suppose Dynamo server S1 is perfectly healthy with a working network connection. By mistake, an administrator instructs server S2 to remove S1 using the mechanisms described in 4.8.1 and 4.9. It takes a while for the membership change to propagate from S2 to the rest of the system (including S1), so for a while some clients and servers will think that S1 is still part of the system. Will Dynamo operate correctly in this situation? Why, or why not?
Topic Paper
Spanner: Google's Globally-Distributed DatabaseLec.15
Paper & Question
Practical Byzantine Fault ToleranceIf faulty nodes produce random results as opposed to being actively malicious, what is the number of replicas needed to handle f bad nodes? Why?
Topic Paper
CheapBFT: Resource-efficient Byzantine Fault ToleranceCredits: questions and papers from MIT 6.824 and part of slides come from Paul Krzyzanowski (Rutgers), Haibo Chen (SJTU) and et al.