Max:95 Median:81 Average:77

I.
A: 2,3,4
B. 1,4
C. 1 
D. 2, 3 
E. 3

II
1.  Let T1 represent BidItem(120), T2 represent BidItem(200). There are two potential outcomes:
(a) T1: success, highest = 120
    T2: success, highest = 200
	
	highest_bid = 200

(b) T2: success, highest = 200
    T1: failure, highest = 200

	highest_bid = 200

2. There are three outcomes. In addition to (a), (b) in 1.  we also have:
(c) T1: success, highest = 120
    T2: success, highest = 200

	highest_bid = 120

This is a non-serializable interleaving, which causes the shared variable highest_bid = 120 instead of 200 after both operations finish.

3. Let T1 represent BidItem(110), T2 represent EndAuction(). There are three outcomes:
(a) T1: success, highest = 110
    T2: Item sold for 110

	sold = true, highest = 110

(b) T2: Item sold for 100
    T1: failure, item already sold

	sold = true, highest = 100

(c) T1: success, highest = 110
    T2: item sold for 100

	sold = true, highest = 110

III. 
4. Ben's modification is not correct.
   Here's a counter example in the lecture note's notation (where p1 denotes a node has successfully prepared proposal #1 and a1foo denotes a node has successfully accepted proposal #1 with value=foo.)
   S1: p1  a1foo
   S2: p1        p2  a2bar
   S3: p1        p2  a2bar

   According to Ben's modification, upon "a1foo", S1 would have decided "foo" which is incorrect since 
   S2 and S3 have later decided on "bar".

5. 1,2,3

6. Yes. Ben is correct.
   Note that if a node has changed its identifier, it cannot participate in the current Paxos instance.  Based on our implementation of Lab2, there will be a view change (where a majority of nodes in the previous view need to agree) to include the new node  in the new view.

   In practice, one might not adopt this approach because the system cannot be recovered whenever there's a majority of node failures within a short period of time in a single view.  

//Grading note: the "yes" or "no" answer does not affect your score. But if you give a counterexample that does not involve view change and just have the recovered node participate in the old view's Paxos, it would be marked as incorrect.
  
IV.

7. 3. The get request (G_req) occurs after put completes (P_ok), so get should read the effect of the put.
   4. G_ok(x=1) indicates that in the equivalent serial order, put > first_get operation.
      G_ok(x=1) precedes the second get request, so first_get > second_get 
	  therefore, put > second_get, second_get must return 1 instead of 0.

8. No. 
   Suppose the primary node has failed before replicating a put(x=1) request to N1 and N2, the recovered RSM would see x=0 (the old value before the put). However, the primary may have already returned x=1 in response to some get requests. So something like history 4 can happen.

9. No.
   History 4 is possible.
   While a put=1 is being propagated along the chain,
   the first get request is issued to N2 and N2 has just processed put(x=1)
   the second get request is issued to N3 and N3 has not yet processed put(x=1)