Distributed Systems 
Fall 2008
Exercise 4

Topic: Mutual exclusion, replication, transactions, serializability
   
1. This assignment handles the mutual exclusion problem.
   a) "Prove" that the Ricart-Agrawala algorithm works correctly:
      M1 at most one process may execute in the critical section at a time
      M2 requests to enter the critical section eventually succeed
         (starvation not possible)
      M3 if the relation Ra -> Rb exists between the requests Ra and Rb
         then Ra is served first.
      What can you say about the fault tolerance of the algorithm?
   b) Look at the slide 40 of Chapter 4 (CoDoKi, 2nd ed.: Fig.11.5).
      Assume that while P2 is using the resource the process P3 (with
      the timestamp 35) makes a request for the resource. Does the 
      algorithm really work correctly? In all cases?
   c) Give an example to show that the central server model does not
      necessarily satisfy the requirement M3.
   d) How could you make the central server model fault tolerant?
      (What is "fault tolerance" supposed to mean here?)

2. Discuss the merits of push and pull replication in web content
   distribution. In which situations is one better than the other?


3. a) Assume that serializability is implemented using two-phase locking
      (2PL).
      Which different orderings of events (in real time) are possible, when
      the following transactions are started at the same time:
      
        T: x:=Read(i); Write(j,44)
        U: Write(i,55); Write(j,66) ?
        
   b) Explain why serial equivalence requires that once a transaction has
      released a lock on a data item, it is not allowed to obtain any more 
      locks. Give an example.
      
   c) Consider a relaxation of two-phase locks in which a read lock can be
      released after the transaction has finished using the corresponding 
      data item. Is it feasible?

   d) Who is responsible for granting and releasing the locks in distributed
      transactions?
      

4. Use the transactions of the previous question to visualize the
   principles of 
     a) (pessimistic) timestamp-based method
     b) optimistic (timestamp-) based method.
   Explain each decision using arguments based on the serializability 
   requirement. 
   
   All the three methods we have presented assume a certain hypothetical serial
   order of the transactions.  Which events specify this order in each case?
   
   In distributed transactions, who makes the consistency checks?