Homework 12

Due 11/16/2011 3:59PM

Problem 1

Consider a distributed system where there is a file server and a number of client machines. To provide concurrency control, the file system includes a lock manager that issues locks to client machines upon requests. Locks can be either shared or exclusive. Shared locks are useful only for file reads, while exclusive locks are needed for file updates. The file server issues lock to a given client with a timed leases, such that when the lease expires, the lock is revoked and the client machine must re-apply to reacquire the lock. Answer the following questions:
  1. Why are leases useful?

  2. Consider the following scenario in accessing a file F.
    MachineRequest time:Request type: Duration until release
    A00:00Shared05
    B00:05Shared10
    C00:08Exclusive02
    D00:10Shared05
    B00:14Exclusive05
    A00:20Shared05
    Assuming that a lease is given for 10 time units, that clients cache the files for performance, that coherence is maintained by an update protocol, and figures showing the four machines and the file server as blocks (see example below), and identifying at each state transition which client machine holds which lock, and the state of the cache at each client. A state transition occurs when the state of the cache changes at one client, when a request is received, when a lock is acquired or when a lock is released.

    Time: 00:00
    Machine A
    Lock: Shared
    Cache: File F    		 Machine B
    Lock: None
    Cache: Empty    		 Machine C
    Lock: None
    Cache: Empty    		 Machine D
    Lock: None
    Cache: Empty

  3. If an "invalidate'' protocol is used for coherence, would the efficiency of the system increase or decrease? Why?

  4. Same as (b), but assume that machine C fails 1 time unit after it acquires the lock. Show the state transition diagrams as instructed in part (b). State clearly and precisely what precautions should be taken in writing the code that updates the file at machine C.

Problem 2

Suppose we run the following program, with the code in the first column running on one machine in a distributed system and the code on the right running on another machine. The distributed system provides a set of shared files with some consistency model. Initially A and B are both 0.
write(A, 1); // Write the value ``1'' to file A write(B, 1); // Write the value ``1'' to file B
if(read(B) == 0) // read the value from file B if(read(A) == 0) // read the value from file A
print ``A wins''; print ``B wins'';

(a) What are the possible outputs assuming the system enforces {\em linearizability}?

(b) For the program described in the previous question, what are the possible outputs assuming the system enforces {\em causal consistency}?

(c) What are the possible outputs for the above program assuming the system enforces {\em sequential consistency}?

Problem 3

Suppose a distributed file system implements linearizable consistency using callbacks and does not use leases. Suppose that a client $c1$ that is caching file $F$ becomes disconnected from the network. Which of the following is true

Problem 4

Suppose programs on three machines are reading and writing files using a file system that enforces causal consistency. Machine 1 runs the following code 
i1 = 0;
while(true){
  overwriteFile("/foo", i1);
  i1++;
}

The function overwriteFile() replaces previous contents of the file with the specified value.

Machine 2 runs the following code

while(true){
  int i2 = readValueFromFile("/foo");
  overwriteFile("/bar", i2);
}

Machine 3 runs the following code

  int i2 = readValueFromFile("/bar");
  int i1 = readValueFromFile("/foo");

Suppose that machine 3 reads the value ``10'' on the first read (of i2). Which of the following is true of the value that machine 3 reads on the second read (of i1)? (If multiple items are true, choose the most precise/restrictive of the options. I.e., i1 < 10 is more precise/restrictive than i1 ≤ 10.)