6.824 Spring 2006 Paper Questions

Please remember to print your answer for each day's paper question on a sheet of paper and hand it in at the beginning of class.

Tu May 2: The Design and Implementation of a Next Generation Name Service for the Internet, SIGCOMM 2004.
Figure 5 shows that 50% of all lookups are answered out of the first CoDoNS node's cache. Section 4.4, however, says that each CoDoNS node caches a mere 10% of the records, on average. Explain the discrepancy between the 50% and the 10%.
Th Apr 27: Secure Untrusted Data Repository (SUNDR), OSDI 2004.
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?
Tu Apr 25: Frangipani: A Scalable Distributed File System, SOSP 1997.
Suppose a server modifies an i-node, appends the modification to its log, then another server modifies the same i-node, 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?
Th Apr 13: Replication in the Harp File System, SOSP 1991.
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?
Tu Apr 11: FAB: building distributed enterprise disk arrays from commodity components. (Skip Sections 4.2 and 6.)
To perform reads and writes of replicated blocks, FAB uses two types of timestamps, ordTs and valTs, as described in Section 4.1. Can FAB still guarantee strict linearizability without using ordTs? If yes, explain why; otherwise, describe a scenario where this consistency model breaks if FAB only uses valTs during reads and writes. According to strict linearizability, a read of a block must return the latest write to the block.
Th Apr 6: Guardians and Actions: Linguistic for Robust, Distributed Programs Support, ACM ToPLS 1983.
No question today.
Tu Apr 4: TreadMarks: Distributed Shared Memory on Standard Workstations and Operating systems, USENIX 1994.
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. Deadmarks doesn't otherwise communicate any changes to memory. Outline a specific simple situation in which Treadmarks would provide more useful or intuitive memory behavior than Dreadmarks.
Tu Mar 21: Ivy, PODC 1986.
The write fault handler in Section 3.1 ends by sending a confirmation to the manager, and that the "Write server" code on the manager waits for this confirmation. Suppose you eliminated this confirmation (both the send and the wait) from Ivy. Describe a scenario in which lack of the confirmation would cause Ivy to behave incorrectly. You can assume that the network delivers all messages, and that none of the computers fail.
Thu Mar 16: Hypervisor-based Fault Tolerance, SOSP 1995.
Suppose the primary fails due to a power failure, the backup takes over, and then power to the primary is restored. You would like the primary to resume replicated execution so that the system could tolerate a subsequent failure of the backup. Is this likely to be easy with hypervisor-based fault-tolerance? Why or why not?
Th Mar 9: Manageability, availability, and performance in Porcupine: a highly scalable, cluster-based mail service, 1999.
Suppose a Porcupine node crashes, then a mail message M1 arrives that should be stored in a fragment on the crashed node, then the user reads and deletes M1, then message M2 arrives that should be stored in the fragment, then the node reboots. The fragment is replicated (which is why the read and delete work). Ideally the node would end up with a copy of M2 but not M1 after the reboot. What specific Porcupine mechanism(s) ensure that the node gets a copy of M2? And what mechanism(s) ensure that it does not end up with a copy of M1?
Tu Mar 6: A Coherent Distributed File Cache with Directory Write-Behind. Read just Sections 1, 2, 3, and 4.
Echo's guarantee B on page 6 says that writes to a given object become stable in the same order that they are performed. Does FSD provide ordering semantics at least as strict as this rule? That is, in every situation in which Echo enforces an update order because of this rule, would FSD also write the updates to disk in the same order? If yes, briefly say why; if not, give a counter-example.
Thu Mar 2: Reimplementing the Cedar File System Using Logging and Group Commit, 1987.
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?
Tu Feb 27: Java RMI, 1996.
Suppose that you wanted to implement an NFS-like server and client in Java using RMI. One possibility would be to create a Remote interface for the server object, with calls like FileHandle lookup(FileHandle fh, String name); in this case FileHandle would not be a remote object, but would be an array of bytes just as in the ordinary NFS protocol. A second option would be to make a FileHandle Remote interface, with methods like FileHandle lookup(String name). Why would the second probably be more convenient? Why would the first probably be more robust?
Th Feb 23: A toolkit for user-level file systems, 2001.
Refer to the description of the automounter in Section 4.3. Suppose a user level file system has asked the automounter to mount it on /sfs/newfs. The paper says that when an application first accesses /sfs/newfs, the automounter returns a sequence of two symbolic links. The automounter delays the response to the second READLINK, and eventually returns "/sfs/newfs". What would go wrong if the automounter returned only one symbolic link, delayed the response to the first and only READLINK, and then returned "/sfs/newfs"?
Thu Feb 16: Case study of the Network File System (NFS), 6.033 course notes Appendix 4-B, 2006.
NFS file handles are intended be be file identifiers. Would it be reasonable for an NFS server implementation to use a file's name (e.g. "/usr/rtm/webproxy1. C") in the file handle, instead of the inode number? If not, give an example of a serious problem that would result. Ignore the question of whether file handles are big enough to hold long file names.
Tue Feb 14: Flash: An efficient and portable Web server, 1999.
How would you expect the relative performance of MP, MT and AMPED servers improve if the Flash experiments were run on a multiprocessor machine? (with no modifications to the code)

Questions or comments regarding 6.824? Send e-mail to 6.824-staff@pdos.lcs.mit.edu.

Top // 6.824 home //