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,
- 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
- Tu Mar 6: A Coherent Distributed File
Cache with Directory Write-Behind. Read just Sections 1, 2, 3, and
- 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
What would go wrong if the automounter returned only one symbolic link,
delayed the response to the first and only READLINK, and then returned
- 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.
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
- 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 email@example.com.
6.824 home //