-------------------------------------- PROBLEM 1 1. Grading Policy: 5 pts for the algorithm 3 pts for using snapshots 2 pts for eliminating the choosing variable 5 pts for the proof 4 pts for mutual exclusion 1 pt for recognizing there were other parts (well-formedness, progress,...) to the proof, even though the proofs are the same as ones in the book 2. General Comments: Several people recognized that the choosing variable could be eliminated, but then did not replace it with a way to distinguish between a process in the remainder region from one in the middle of selecting a new number. Other problems included not noticing that it was possible to replace the choosing variable with setting number := 1. Finally, even though the problem only required a proof sketch, several people only stated that Lemma 10.24 and Lemma 10.25 still held without saying anything or very little about why they still held. Those who did this but also described how setting number := 1 is like using the choosing variable received more credit. 3. AVERAGE 8.2 -------------------------------------- PROBLEM 2 Everyone did well on this problem. I took off 2 points if the complexity analysis was completely omitted, and 1 point if there was something missing or it was incorrect. For the proof, it was quite similar to the one in the book, so I was fairly lenient. If the person didn't mention the 2 claims, but worked on the 4 conditions, then I took off 1 point. If the person worked on the 2 claims, but not the 4 conditions, I took off one point. The read propagation was worth one point. If you said you require all n registers, instead of m, then I also took off one point. For those who required the read propagation but still had a vector of length n, then I only penalized you once for that error. All errors should be noted on the paper. -------------------------------------- PROBLEM 3 1. Grading Policy: Almost everybody gave an acceptable answer so there was not much to grade. The question only asked to give an execution which resulted in the required state, almost all the people did this clearly and correctly, so I gave them 10's. Even the people who made errors gave a correct execution: 1 point off for a person who failed to mention that the writes needed to execute on alternating ports in his execution, but tag values implied it. 2 points off for 1 person who was unclear on the algorithm and incremented the tags based on READi's local variables t1 and t2. 2 points off for a person who started his execution at x(1).tag = 0 x(2).tag = 0. By algo. should be x(1).tag = 0, x(2).tag = 1. 1 point off for bad wording/notation, though execution was correct. 2. General Comments: All solutions pretty much the same. One variation to note is that the WRITE1(v) read of x(2).tag can occur before the READi message, as long as WRITE1(v) doesn't write to any tags before READi reads x(1).tag. Similarly, WRITE2's ACK2 message need not be sent before READi finishes, as long as READi reads x(2).tag after WRITE2 writes it. 3. AVERAGE: (34*10+2*8+2*9)/38 = 9.84 -------------------------------------- PROBLEM 4 1. Grading Scheme: No mention of index: -1 No mention of waiting for majority: -1 Wrong or no logic about write or read: -2 No/wrong correctness proof: -1 No/wrong simulation comments (for part b): -2 2. Typical mistakes: Used only an index, instead of a lexicographically ordered pair. Did not wait for a majority of ack's for read or write Gave no comments about correctness. Didn't say "how" to do part b, just said that it is true. Only did embedded read to the writers -- not to all processes 3. Average: 8.82. -------------------------------------- PROBLEM 6 1. Grading Policy: Algorithm: 5 points, -3 points for major problem -2 for an incorrect algorithm, with the right idea -1/2 for minor things such as assuming that the values in V can be ordered Correctness: 5 points, -2 incorrect/unclear termination -2 incorrect/unclear k-agreement -1 validity/well-formedness is not mentioned 2. General Comments: The two most common solutions actually followed the hint given in Ex. 21.13 and removed the stopped vector from the state. The first solution did not use (ignored) the failure detector completely while the second one used the failure detector input action in the same way the PerfectFDAgreement uses it to reset ratified. Some people just used the TrivialKAlgorithm or the PerfectFDAgreement itself. A common mistake was the assumption that the values in V could be ordered, and many algorithms relied on that. Even though it is a reasonable assumption, the general solution should not rely on such an assumption. Most people just lost 1/2 of a point for that. 3. Average: 8.575