+-------------------+
| Problem Set 6 (a) |
+-------------------+


Problem 1
=========

(a) 2 pts for trying
 1 pt for correctly stating it's possible
 2 pts for correct algorithm
(b) 2 pts for trying
1 pt for correctly stating it's possible
2 pts for correct algorithm
(These are identical because most people for part (b) just said see part (a))


Problem 2
=========

6 points for part (a):
    3 points for proving consensus number at least 2:
         2 point for describing 2-thread protocol
         1 point for indicating it's correctness

    3 points for proving consensus number exactly 2

4 points for part (b) (proving infinite consensus number):
    3 points for protocol,
    1 point for indicating correctness

In general I took off a point for no indication of correctness for the
protocol in part a or b, and I took of a point for inaccuracies in the
proof of a case in the consensus less than 3 part of part a (for those
who used the cases approach).


Problem 3
=========

3 pts for trying
2 pts for correctly stating it's impossible
(Case analysis method)
2 pts for saying it reaches a critical state
3 pts for a complete and correct case analysis
(Consensus number method)
2 pts for a correct consensus number argument (i.e. can't have consensus number
greater than
it's implementing objects)
2 pts for correctly showing the RMW registers have consensus number = 2
1 pt for mentioning the MRSW registers have consensus number = 1


Problem 4
=========

There were basically 3 approaches taken:
1) Show that you can implement SetAgree(k) for 2 threads using atomic registers
2) Say that for k=2, we have to solve binary consensus which can't be solved by
atomic registers 
3) Give some kind of valency argument

All 3 explanations received full credit, although the first approach was the
easiest.  I took off one point
where I felt that there was an error in the logic.  


Problem 5
=========

a) +3: say that different threads will compute after.response differently
   +3: give an example that shows the problem
   
b) +4: for replacing response with a consensus object




+-------------------+
| Problem Set 6 (b) |
+-------------------+


Problem 1
=========

Proper counter-example: +10
Otherwise:
  Demonstration of understanding algorithm: up to +4
  Wait-free argument: up to +3
                            usually +2, extra +1 for careful attention
                            to proof structure in book.



Problem 2
=========

By and large, everyone got this right.  There are three ways people lost
points:
  -2: Gave an 'initial configuration' of processes that is really only
possible midway through a write, but didn't say so.
  -1: Spoke of the writing process as 'failing' - not part of model
  -1: General lack of clarity in writeup.


Problem 3
=========

+2 Identifies/Realizes why the trivial extension doesn't work (simply
duplicating writers)
+2 Realizes that tie breaker must be implemented for tags
+2 Waits to see a majority of the tags to write/writes correctly
+2 Propagates information after a write
+2 Demonstrates how the object can be used to simulate a shared memory
model


Problem 4
=========

2pts:
For saying that the min property of the quorums is that they intersect by 
at least 1

2pts:
For saying use read quorum for proposals (prepare requests) and write 
quorum for acceptors.

1pt:
For saying that P1 is not related to majorities, therefore unchanged

5pts:
For saying that P2c still holds because
- a value is chosen only is write-quorum of acceptors accept it.
- then if a proposer gets a read-quorum claiming that it is ok for the 
proposer to write, it must be ok since the read and write quorum overlap by 
one, so a read quorum claiming that no write quorum had been obtained by a 
previous proposer.
- (then, same arg that P2c => P2b => P2a as made in "Paxos Made Simple") - 
no points deducted for not stating this last point