Solutions for Sample Exam 2


1  Consistency for complex objects like test-and-set is out of scope this semester.

   The scope this semester DOES include consistency of read/write shared memory variables.


2(i)  NO. Delete a=read(x) performed by Transaction T.
2(ii) NO. Replace write(z,1) performed by Transaction U by b = read(z).

3. Distance-vector routing NOT included in the scope of Exam II this semester.

   Yes. For instance, consider a cyclic topology consisting of 8 nodes
   named 0 through 7, in which each node i has links to nodes i-1 mod 8
   and i+1 mod 8.

   In this case, once the distance vector algorithm stabilizes (i.e., finds
   optimal routes), the next hop at node 0 for destination 2 will be node 1,
   and next hop for destination 2 at node 1 will be node 2.

   Now suppose that the link 1-2 breaks. Then, node 1 will update its
   table to show node 0 as the next hop for destination 2 (since node 1 has
   no other route to node 2). However, the table at node 0 may still be 
   unchanged, showing the next hop for destination 2 as node 1.

   Thus, if node 0 has a packet for node 2, node 0 will send it node 1, which
   will send it back to node 0. This is a routing loop.

   Eventually, when node 0 receives a new distance vector from node 1,
   node 0 will update its table to make node 7 as the next hop
   for destination 2, breaking the above loop.

4(a) Transaction V performs validation first, followed by transaction U, and
     the transaction W.

   Transaction V will abort, because its write set has a non-empty intersection
   with active transaction U (because of their accesses to variable w).

   Transaction U does not abort, since the write set of active transaction U
   does not intersect with the read set of T at the time U performs validation.

   Transaction T does not abort, because there are no active transactions
   when T performs validation.

4(b) The timestamp ordering NOT in scope this semester.


5.  Initial value of shared variable V = 0

    Entry code:

      repeat
          a = compare&swap(V, oldvalue = 0, newvalue = 1)
      until a = 0
    


    Exit code:

	compare&swap(V, oldvalue = 1, newvalue = 0)


   Shared variable V is not accessed by any process outside of the
   above entry and exit code.


6(a)  Key 8 - node 8
      Key 14 - node 15

6(b) No fingers at node 4 are changed.

          before adding node 10  `		after adding node 10
	4+1=5 ==> point to 8			unchanged
	4+2=6 ==> point to 8			unchanged
	4+4=8 ==> point to 8			unchanged
 	4+8=12 ==> point to 15			unchanged


     Two fingers at node 8 are changed
      
          before adding node 10  `		after adding node 10
	8+1=0 ==> point to 11			point to 10
	8+2=10 ==> point to 11			point to 10
	8+4=12 ==> point to 15			unchanged
 	8+8=16=0 ==> point to 4			unchanged

6(c) Keys 9 and 10 moved from node 11 to node 10

7(a) See required reading for hypercubes

7(b) Four disjoint routes. 

8. Suppose that proposer 1 sends value 0 to acceptors 1, 2 and 3,
   and proposer 2 sends value 1 to acceptors 3, 4 and 5.
   Acceptors 1 and 2 accept 0, and acceptors 3 and 4 accept 1
   Learner 1 learns value 0 from acceptors 1 and 2.
   Learner 2 learns value 0 from acceptors 4 and 5.

   Suppose that acceptor 3 is Byzantine faulty, and sends
   mismatching messages to learners 1 and 2 (specifically,
   with values 0 and 1, respectively).
   Thus, learner 1 learns value 0 from acceptors 1, 2 and 3.
   Thus, learner 2 learns value 0 from acceptors 3, 4 and 5.
   Since three acceptors are a majority of acceptors, learners
   1 and 2 learn mismatching values 0 and 1, respectively.

9 Not in scope this semester

10. Process p0 is special, as per specifications in the question.

    Select p0 as the coordinator, who initially possesses a TOKEN.

    If process p0 wants to enter critical section, and possesses the token,
    it enters critical section immediately; otherwise, p0 enters the 
    critical section, when it next receives the TOKEN from another process.

    Any process p other than p0, in its entry section, sends a REQUEST to
    p0, and waits until it receives TOKEN. On receiving token, p enters
    critical section. On exit, p sends TOKEN back to p0.

    When p0 receives a REQUEST, it queues it up in a FIFO request-queue.

    Whenever p0 has the TOKEN, but does not want to enter critical section
    itself, p0 sends the TOKEN to the first process whose request is queued
    up in the request-queue (and removes that request from the queue) if
    the queue is non-empty.