1. Here is an algorithm for two-process mutual exclusion.
   
   int try1 = 0, try2 = 0, in1 = 0, in2 = 0;
   
   while (true) {
     try1 = 1;
     in1 = in2 + 1;
     try1 = 0;
     while (try2 == 1) ;
     while (in2 ≠ 0 && in1 > in2) ;
     critical section;
     in1 = 0;
     noncritical section;
     }
   
   while (true) {
     try2 = 1;
     in2 = in1 + 1;
     try2 = 0;
     while (try1 == 1) ;
     while (in1 ≠ 0 && in2 ≥ in1) ;
     critical section;
     in2 = 0;
     noncritical section;
     }
   

   What semantics (regular, safe, or atomic) are needed for the shared variables try1, try2, in1 and in2 for this algorithm to correctly implement mutual exclusion? Explain the reasoning behind your answer.

   ---

2. In lecture, we described a distributed mutual exclusion algorithm that could tolerate crash failures. Recall that for this situation, we had n processes that voted to allow a client to have mutex or not. If up to t processes could crash, then we need n > 2t processes.

   Consider another kind of faulty behavior: a process can be insane. Insane processes can vote any way they wish — for example, an insane process may never vote to allow a process to enter mutual exclusion, or it might vote for multiple processes. Insane processes can also just stop executing — which is equivalent to crashing.

   Modify the mutual exclusion protocol so that it can tolerate up to t insane processes. You will need to consider using more than 2t replication.

   ---

3. The Chandy-Lamport (CL) Snapshot protocol assumes reliable FIFO channels.
   
   
   1. Show that if messages are not FIFO, then the cut that CL records may not be consistent. For simplicity, consider a system of only two processes when constructing your answer.
      
      
   2. Modify CL so that it is correct for non-FIFO channels. Do this using the following two ideas:
      
      
      1. For the channel state from, say, process i to process j, have i keep in its state the set of messages it has sent to j. (This can be done more elegantly, of course, but it works.)
         
         
      2. Avoid problems like the one you showed in part a by having processes temporarily stop sending messages.

      This should be for n processes, and not just 2 (unlike part a).

19 January 2009 by kam