CPS 212 Midterm ExamFall 2007Answer all questions. Please do not waste any words: answers are graded on content, not style. It is notnecessary to write complete sentences when a few key words or phrases will suffice. The questions areworth 50 points each, and you earn 50 points for stapling your answers together and writing your name oneach page, for a total of 300 points. Allocate your time carefully. You have 74 minutes.1. Sharing data. Consider the following consistency properties for shared data objects, defined with respectto a global clock. A write is confirmable if the writer can determine when it completes. The system is safeif each read returns the value of the last completed write, and some arbitrary value if there is a concurrentwrite. The system is regular if it is safe and, in addition, a read returns the value of one of the writers ifthere are one or more concurrent writes. Sequences of reads and writes are atomic if they appear to executeas a group at a single point in time.Draw a table indicating whether the data sharing systems we have studied have each of these four properties.Consider the following systems: NFS, Porcupine, FAB, SSM. Feel free to add additional notes or qualifiersif the answer depends on other conditions, e.g., the presence of certain kinds of failures.2. Leases. Answer the following questions about leased locks, e.g., as in NQ-NFS or Frangipani (or Lab 1).• What are the tradeoffs in the choice of a lease interval?• In NQ-NFS each file has a separate leased lock, and Frangipani also uses leased locks to protectvarious other metadata structures. What are the tradeoffs in the granularity or scope of the locks, i.e.,the choice of how much data to protect with each lock?• How does a leased lock function in a network partition? (For example, if the lease holder is not ableto contact the server, but both are functioning). How should the system handle writes made under thescope of a leased lock? What impact does this have on the consistency model?3. Stuff happens. “The enormous success of NFS should not be take as an indication that reliable applica-tions can in fact be built over it, but rather as a sign that failures are really not all that frequent in moderncomputing systems and that most applications are not particularly critical.” – Ken Birman. Do you agree?Discuss with reference to the failure and consistency model of NFS and its alternatives. (NFSv3 is thestandard but any version will do.)4. Sharingresources. The Quorum system (as described in the UCSB NSDI-05 paper) and SoftUDC/Hippodromerepresent two distinct approaches to provisioning multiple hosted services on a shared cluster. In this con-text, “provisioning” means controlling how much cluster resource (e.g., CPU time) is available for use byeach guest application service.• Briefly discuss how we might specify the goals of such a system, e.g., as Service Level Objectives forthe application, and how the system can determine if it is meeting its goals.• Briefly discuss the relative merits of these approaches and the conditions under which each might bepreferable to the other.1• At least one of the Hippodrome authors believes that “Quorum won’t work for storage services orother I/O-intensive services”. Do you agree? Say why or why not. It may be useful to refer to specificstorage service architectures in your answer (e.g., Frangipani and/or FAB).5. Log locally, commit globally. Consider the behavior of the classical two-phase commit protocol over anetwork with unbounded message delays. Suppose further that the log disks are accessed over the network,so that log log reads and writes are also subject to delays. What could go wrong? How would the problemmanifest to a transactional application? Feel free to propose solutions (extra
View Full Document
Unlocking...