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.

   I show that if the domain of variables is restricted to nonnegative integers, then we only need MRSW safe semantics. This proof also suffices for MRSW regular registers over the integer domain since such reads will return only nonnegative values.

   First, an aside: I had thought I had given you the two-process version of the Bakery algorithm, but I didn't. Instead of in1 = in2 + 1, it should have been in1 = max(in1, in2) + 1. This statement would ensure that in1 would be given a positive value, and thus requires only safe registers when the variables are integers.

   Another aside: One of you wondered why the logic with try1 and try2 was included. Consider the following protocol that doesn't have these variables:

   int in1 = 0, in2 = 0;
   
   while (true) {
     in1 = in2 + 1;
     while (in2 ≠ 0 && in1 > in2) ;
     critical section;
     in1 = 0;
     noncritical section;
     }
   
   while (true) {
     in2 = in1 + 1;
     while (in1 ≠ 0 && in2 ≥ in1) ;
     critical section;
     in2 = 0;
     noncritical section;
     }
   

   Here's the execution with integer domain and MRSW atomic registers that leads to violation of mutual exclusion:

   1. Process 2 reads in1 and gets 0.
   2. Process 1 reads in2 and gets 0.
   3. Process 2 continues. It writes 1 to in2 and enters the critical section because in1 is 0.
   4. Process 1 continues. It writes 1 to in1 and enters the critical section because in2 = in1.

   Going back to the algorithm given in the homework, here's the execution with integer domain and MRSW safe registers that leads to violation of mutual exclusion:

   1. Process 2 reads in1 and gets 0. It starts to write 1 to in2.
   2. Process 1 reads in2 and gets -1 (the read overlaps a write). It writes 0 to in1.
   3. Process 2 completes the write and writes 0 to try2.
   4. Process 1 writes 0 to try1.
   5. Process 2 enters the critical section because in1 is 0.
   6. Process 1 enters the critical section because in2 > in1.

   I'll now assume that the variables are nonnegative integers.

   • Let w1 be the event try1 = 1, w0 be the event try1 = 0, and r be the read event in while (try1 == 1).

     • If e1 overlaps with r then process 2 can retrieve any value. If the value it retrieves is 1, then the execution is equivalent to e1; r. If it returns a non-one value, then the execution is equivalent to r; e1. Hence, r and e1 can overlap with safe semantics.

     • If e0 overlaps with r then process 2 can retrieve any value. If the value it retrieves is 1, then the execution is equivalent to r; e0. If it returns a non-one value, then the execution is equivalent to e0; r. Hence, r and e0 can overlap with safe semantics.

     A symmetric argument holds for try2.

   • Let r1 be the read of in2 in in1 = in2 + 1, and r2 be the read of in2 in while (in2 ≠ 0 && in1 > in2) (assuming a single read into a local register. A similar argument can be made if the value of in2 is read twice in this statement). Let w be the write of in2 in in2 = in1 + 1.

     • Suppose r1 overlaps with w. Then, in2 can be any nonnegative value and in2 will be set to an arbitrary positive value. This poses no problem.

     • Suppose r2 overlaps with w, and so in2 returns an arbitrary value. If it returns 0 and process 2 computes a value of in2 less than in1 then we can violate mutual exclusion. This could happen only if process 2 read in1 before or during the time Process 1 was writing in1. If so, then Process 1 would have held at the first while loop, and so this interference would not have happened.

   ---

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.

   The original protocol required the client to have a quorum all vote "yes". The problem we have now is that insane processes may vote "yes" to one client and "yes" to another. For example, suppose we have three servers S1, S2, S3 where S1 is insane. Servers S1 and S2 both vote "yes" to one client, and servers S1 and S3 vote "yes" to another client, violating mutual exclusion.

   We required quorums to intersect. With insane servers, we would instead require the intersection of any two quorums to contain a non-insane server. If up to t servers can be insane, then the intersection of any two quorums would need to contain at least t + 1 servers. This implies that a quorum contains 2t + 1 servers with n > 3t. For example, if t=1, then there would need to be 4 servers, and each quorum would contain 3 servers.

   ---

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.

      
      Here's an example. Let the dashed arrow be the take snapshot message. The recorded states are the colored boxes over the processes. Note that the take snapshot message was delivered after a later-sent application message. Because of this reordering, the recorded global state is inconsistent.
      
      
      

   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).

   By recording the messages in the process states, we can ignore flushing channels. In this model, the original CL algorithm is:

   p0: send "SS" to self
   
   pi: when receive "SS" for first time (from pj) {
         record state
         send "SS" to all neighbors
         for each neighbor except pj wait for "SS"
         }
   

   This assumes FIFO channels. To accommodate non-FIFO channels, we just have to ensure that the delivery of the snapshot message does not get moved after the delivery of subsequent messages. The easiest way to do this is to block sending application messages until the snapshot is complete. We define a set BLOCK for each process p. For each process q in BLOCK, p will block all sends to q until q is no longer in BLOCK.

   p0: send "SS" to self
   
   pi: when receive "SS" for first time (from pj) {
         record state
         BLOCK = all neighbors - { pj }
         send "SS" to all neighbors
         while (BLOCK ≠ ∅) {
           when receive "SS" (from pk)
             BLOCK = BLOCK - { pk }
           }
         }
   

29 January 2009 by kam