6.824 Spring 2012 Paper Questions

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?

An introduction to Programming with C# threads Will your lock server for lab 1 use mutexes? Condition variables? Why or why not? Give a specific example in your answer.

Plan 9 from Bell Labs List three features introduced by Plan 9 that have not been adopted by today's common operating systems. For each, why do you think the idea hasn't become popular?

Piccolo: Building Fast, Distributed Programs with Partitioned Tables 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 Piccolo, and explain how it gets parallel speedup on a cluster.

Memory Coherence in Shared Virtual Systems 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.

Distributed Shared Memory on Standard Workstations and Operating Systems 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.

File Synchronization with Vector Time Pairs Why does Tra have two vectors times (modification time and synchronization time)?

Managing Update Conflicts in Bayou Suppose we build a distributed filesystem using Bayou, and the system has a copy operation. Initially, file A contains "foo" and file B contains "bar". On one node, a user copies file A to file B, overwriting the old contents of B. On another node, a user copies file B to file A. After both operations are committed, we want both files to contain "foo" or for both files to contain "bar". Sketch a dependency check and merge procedure for the copy operation that makes this work. How does Bayou ensure that all the nodes agree about whether A and B contain "foo" or "bar"?

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?

Guardians and Actions: Linguistic Support for Robust, Distributed Programs In Figure 4, read_mail deletes email from the mailbox. If new mail arrives just before the delete, will the email be deleted but not returned? Please briefly explain your answer.

Hypervisor-based Fault-tolerance Suppose that instead of connecting both the primary and backup to the same disk, we connected them to separate disks with identical copies of the data? Would this work? What else might we have to worry about, and what are some things that could go wrong?

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?

1. A sends prepare requests with proposal number 1, and gets responses from A, B, and C.
2. 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.
3. B sends prepare messages with proposal number 2, and gets responses from B and C.
4. B sends accept(2, "bar") messages to B and C and gets responses from both, so B thinks that "bar" has been chosen.

Replication in the Harp File System Figures 5-1, 5-2, and 5-3 show that Harp often finishes benchmarks faster than a conventional non-replicated NFS server. This may be surprising, since you might expect Harp to do strictly more work than a conventional NFS server (for example, Harp must manage the replication). Why is Harp often faster? Will all NFS operations be faster with Harp than on a conventional NFS server, or just some of them? Which?

Frangipani: A Scalable Distributed File System Suppose a server modifies an i-node, appends the modification to its log, then another server modifies the same i-node, and then the first server crashes. The recovery system will see the i-node modification in the crashed server's log, but should not apply that log entry to the i-node, because that would un-do the second server's change. How does Frangipani avoid or cope with this situation?

Megastore Suppose there are three replicas: R1, R2, and R3. R3 suffers a network fault and cannot communicate with R1 or R2. Can R1 and R2 continue to make progress by commiting transactions? Or must they wait for R3's network to be repaired?

Practical Byzantine Fault Tolerance Suppose that we eliminated the pre-prepare phase from BFT. Instead, the primary multicasts a PREPARE,v,n,m message to the replicas, and the replicas multicast COMMIT messages and reply to the client as before. What could go wrong with this protocol? Give a short example, e.g., ``The primary sends foo, replicas 1 and 2 reply with bar...''

Secure Untrusted Data Repository (SUNDR) In the simple straw-man, both fetch and modify operations are placed in the log and signed. Suppose an alternate design that only signs and logs modify operations. Does this allow a malicious server to break fetch-modify consistency or fork consistency? Why or why not?

PNUTS: Yahoo!'s Hosted Data Serving Platform Briefly explain why it is (or isn't) okay to use relaxed consistency for social applications (see Section 4). Does PNUTS handle the type of problem presented by Example 1 in Section 1, and if so, how?

Democratizing content publication with Coral The Coral paper mentions in Sections 2.3 and 4.2 that Coral's ``sloppy'' DHT can store multiple different values for each key. What would break, or not work as well, if Coral's DHT only stored one value for each key?

Tor: The Second-Generation Onion Router Consider users that employ TOR to read their email via an unencrypted IMAP connection. Does TOR guarantee complete anonymity for these users? If so, please explain why. If not, what information could the attacker learn about the user, and how might it do so?

Experiences with a Distributed, Scalable, Methodological File System: AnalogicFS 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.