Homework 4 (Distributed File Systems, Self‐Stabilization, Transactions and Concurrency Control, Replication) ‐ 100 Points CS425/ECE 428 Distributed Systems, Fall 2009, Instructor: Klara Nahrstedt Out: Tuesday, November 10, Due Date: Tuesday, December 1 Instructions: (1) Please, hand in hardcopy solutions that are typed (you may use your favorite word processor). We will not accept handwritten solutions. Figures and equations (if any) may be drawn by hand. (2) Please, start each problem on a fresh sheet and type your name at the top of each sheet. (3) Homework will be due at the beginning of class on the day of the deadline. Problem 1 (15 Points) : Consider a Calendar composed of “week”, “days” and “hourly time slots”. Indicate what actions (block , grant lock, release lock) is taken and what type of locks are set for each of the following actions in the following sequence: (i) – Process A wants to insert an appointment for slot 11:00 am of Monday of week‐10. (ii) – Before Process A completes, process B requires to read entries in week‐10; (iii) – Process A finishes and commits. (iv) ‐‐ Process C wants to block off Monday of week‐10 for a conference. Problem 2 (25 Points): A server manages the objects a1; a2; : : : ; an. The server provides two operations for its clients: (1) read(i) returns the value of ai; and (2) write(i; value) assigns “value” to ai. Consider the following interleaving of transactions T, U, and V: Time T U V 1 openTransaction openTransaction openTransaction 2 y=read(k); 3 x=read(k); 4 write(i,55); 5 write(j,66); write(i,77); 6 commit; 7 8 x=read(i); 9 write(k,44); 10 write(k,88); (a) (strict 2‐phase locking) Suppose the strict 2‐phase locking mechanism is used for concurrency control. Answer the following questions: (i) Does U have to wait to acquire the lock for x =read(k)? (ii) Does V have to wait to acquire the lock for write(k,88)? (iii) Does T have to wait for acquire the lock for x =read(i)? If the answer to any of the questions is yes, specify at what time the transaction can acquire the lock. (iv) Do transactions T and V eventually commit? If the answer is yes, in what order? (b) ‐ Describe the information written to the recovery file on behalf of these transactions if strict 2‐phase locking is used. Problem 3 (20 Points): (a) A number of processes are collaborating in a group communication. Initially, P joins the group and knows nothing about other members in the group. Then, it learns that Q and R and W have joined the group. Then it learns that X joins the group. A while later it learns that R leaves and then learns that X cr as hes. Show different views of the process P from the initial to the final stages of the above scenario. (b) Given 9 replicas, if updates are reflected on 5 replicas and include timestamps, what is the minimum number of replicas we must read to ensure that we have at least one up‐to‐date data. (c) Suppose we have 6 replicas with write-all, read-all policy in which view-based quorum is used with a write threshold of 4, in case of partition. If the system is partitioned into two parts of 3 nodes each, can we read and write in any of these partitions? Explain your answer. Problem 4 (15 Points): Consider the following three transactions: T: U: W: getbalance (A) getbalance(B) getbalance(B) Getbalance (C) deposit(A, v1) getbalance (A) Deposit(B, v2) deposit(C, v3) Object A is replicated at servers X, Y and Z. Object B is available at M, N and P. Object C is replicated at X, M and Z. T reads from X for A and C. Later, X fails. U reads from N for B. Later, N fails. W reads from M for B and from Z for A. If “Available Copies” policy is used for replication control, show what failure timelines must be met for each transaction to be able to commit. Problem 5 (10 Points) : Give three reasons why fetching entire files at clients is more preferable to fetching file blocks as they are accessed (hint: AFS)? Problem 6 (15 Points): Consider Problem 14.1 in Textbook
View Full Document
Unlocking...